4 ms·

Today I learned about excess-3 encoding, from footnote 10 in the linked article. Its interesting to see how clearly the early computers were intended to work w

by aftbit 5y ago

Today I learned about excess-3 encoding, from footnote 10 in the linked article. Its interesting to see how clearly the early computers were intended to work with decimal while retaining the simplicity brought by using the two signal levels of binary. Footnote reproduced here: The computer uses excess-three encoding for digits, adding 3 to the value before converting to binary. For example, 6 is represented as binary 1001. The advantage of this encoding is that flipping the bits yields the 9's-complement decimal value, simplifying subtraction. For example, flipping the bits of 6 yields binary 0110, which is 3 in excess-3 notation. Excess-3 representation also handles carries correctly; if you add two numbers that sum to 10, the excess-3 values will sum to 16, causing a binary carry. To convert the sum to excess-3, The value 3 must be added (if a carry) or subtracted (if no carry). To see how addition works with excess-3, 2 + 4 in excess-3 is binary 0101 + 0111 = 1100. Subtracting 3 yields 1001, which is 6 in excess-3. But 2 + 9 is binary 0101 + 1100 = 10001, generating a carry out of the 4 bit value. Adding 3 yields 0100, which is 1 in excess-3. Considering the carry-out, this is the desired result of 11.

kragen 5y ago
Some early computers, as early as the 01940s, used binary; others used decimal, typically BCD but sometimes excess-3 BCD or one-hot encoding. Knuth's MIX was originally specified to be either binary or decimal, as you prefer, but by the later volumes of TAOCP he switched to requiring binary for things like tries. Typically an early (pre-01960) computer was either "scientific" or "business". A "scientific" computer was binary, had word-oriented memory of at least 16 bits width and sometimes as much as 60 or more, was measured by its calculation speed, and had floating point. (Some didn't even have separate integer arithmetic.) A "business" computer was decimal, had character-oriented memory of 6-9 bits, was measured by its I/O speed, and had only integer arithmetic, or not even that (as in the case of the IBM 1620). These categories were blurring a lot by the 01960s, and the IBM 360 largely put an end to the division: it had 8-bit-wide memory, 32-bit-wide CPU registers, floating point and binary integer and binary decimal arithmetic, and different binary-compatible models with varying degrees of speed at I/O and calculation. A few years later there were even models that supported paging and timesharing.
- kens 5y ago
  Yes, the IBM System/360 was designed to support the full 360° circle of applications (scientific and business), which was a rather revolutionary idea at the time.
  - kragen 5y ago
    Exactly! But in terms of design, there were earlier machines that spanned the gap like the astounding Burroughs B5000, which was marketed almost entirely to businesses (because that was the Burroughs customer base), but with a 48-bit word length and floating-point-only arithmetic, and including both "numerical" and "character" instruction set operating modes. The first delivery was, I think, to NASA. Also, as Robert points out in https://news.ycombinator.com/item?id=30900280 https://news.ycombinator.com/item?id=30900280, the earlier IBM 1620 was similarly ambiguously positioned.
    - Taniwha 5y ago
      To be fair the B5/6/7 Burroughs machines also had integers ... it's just that they'd chosen a floating point format such that mantissa-sized integers and a 0 exponent always worked and didn't get renormalised unless you overflowed
      - kragen 5y ago
        Interesting! That does agree with Organick's explanation, but he described it as them not having integers.
- tenken 5y ago
  Why do you reference a year via 01960 or 01940? ... Surely you don't mean Hexadecimal... You won't live past 20x0 so why the importance?
  - krallja 5y ago
    Y10K compliance. https://longnow.org/ideas/02013/12/31/long-now-years-five-digit-dates-and-10k-compliance-at-home/ https://longnow.org/ideas/02013/12/31/long-now-years-five-di...
allenrb 5y ago
Like aftbit, I also learned about excess-3. It's amazing to see what was done to save a few gates back when "a few gates" wasn't just a 74-series chip, but an entire handmade board. But before that, the unidisc blew my mind. I had to do some further research and then send to a half-dozen friends before finishing Ken's article. Halfway assumed it was a fake photo until digging a bit further. Couldn't have looked much more like a giant 3.5" floppy if it tried.

by aftbit 5y ago

kragen 5y ago

Some early computers, as early as the 01940s, used binary; others used decimal, typically BCD but sometimes excess-3 BCD or one-hot encoding. Knuth's MIX was originally specified to be either binary or decimal, as you prefer, but by the later volumes of TAOCP he switched to requiring binary for things like tries. Typically an early (pre-01960) computer was either "scientific" or "business". A "scientific" computer was binary, had word-oriented memory of at least 16 bits width and sometimes as much as 60 or more, was measured by its calculation speed, and had floating point. (Some didn't even have separate integer arithmetic.) A "business" computer was decimal, had character-oriented memory of 6-9 bits, was measured by its I/O speed, and had only integer arithmetic, or not even that (as in the case of the IBM 1620). These categories were blurring a lot by the 01960s, and the IBM 360 largely put an end to the division: it had 8-bit-wide memory, 32-bit-wide CPU registers, floating point and binary integer and binary decimal arithmetic, and different binary-compatible models with varying degrees of speed at I/O and calculation. A few years later there were even models that supported paging and timesharing.

kens 5y ago
Yes, the IBM System/360 was designed to support the full 360° circle of applications (scientific and business), which was a rather revolutionary idea at the time.
- kragen 5y ago
  Exactly! But in terms of design, there were earlier machines that spanned the gap like the astounding Burroughs B5000, which was marketed almost entirely to businesses (because that was the Burroughs customer base), but with a 48-bit word length and floating-point-only arithmetic, and including both "numerical" and "character" instruction set operating modes. The first delivery was, I think, to NASA. Also, as Robert points out in https://news.ycombinator.com/item?id=30900280 https://news.ycombinator.com/item?id=30900280, the earlier IBM 1620 was similarly ambiguously positioned.
  - Taniwha 5y ago
    To be fair the B5/6/7 Burroughs machines also had integers ... it's just that they'd chosen a floating point format such that mantissa-sized integers and a 0 exponent always worked and didn't get renormalised unless you overflowed
    - kragen 5y ago
      Interesting! That does agree with Organick's explanation, but he described it as them not having integers.
tenken 5y ago
Why do you reference a year via 01960 or 01940? ... Surely you don't mean Hexadecimal... You won't live past 20x0 so why the importance?
- krallja 5y ago
  Y10K compliance. https://longnow.org/ideas/02013/12/31/long-now-years-five-digit-dates-and-10k-compliance-at-home/ https://longnow.org/ideas/02013/12/31/long-now-years-five-di...

allenrb 5y ago

Like aftbit, I also learned about excess-3. It's amazing to see what was done to save a few gates back when "a few gates" wasn't just a 74-series chip, but an entire handmade board. But before that, the unidisc blew my mind. I had to do some further research and then send to a half-dozen friends before finishing Ken's article. Halfway assumed it was a fake photo until digging a bit further. Couldn't have looked much more like a giant 3.5" floppy if it tried.