13

While early microcomputers were often 4- or 8-bit designs, with larger word sizes coming later, that pattern did not hold for their predecessors. None of the earliest computers used a word size that was anywhere near that small. Even computers which performed addition one bit at a time (e.g. Anastov's engine) still grouped bits into rather large words.

I suspect part of the reason machines used to use such large words was that the word size used to impose an upper limit on the largest number a machine could process without a huge (greater than 4x) loss in efficiency. On a machine with a 16-bit word size, adding together 1000 numbers which could each be anywhere from -32767 to +32767 would require a huge amount of work for each number. If the machine didn't have an efficient right-shift operator, the computation would likely require 2-3 conditional branches for each value to be added. Hugely expensive.

On microcomputers, however, there is usually a "carry" flag, and in many cases there will also be "add-with-carry" instructions which are no more expensive than "ordinary" add instructions [in some cases, including the 4004, addition without carry is more expensive than addition with]. Thus, while a 32-bit computer would have been limited to performing 32-bit math efficiently, an 8-bit microprocessor could perform math efficiently on 8, 16, 24, 32 40, 48, etc. bit quantities with a cost proportional to the integer width (for addition or subtraction) or the product of the source operands' widths (for multiplication). Since most operations won't need 32-bit quantities, using a smaller word size reduces hardware requirements without impacting efficiency of the dominant use cases, while still keeping the ability to perform longer operations when needed.

When did the carry flag originate? The Wiki page on the carry flag indicates it was present on the 4004 (apparent from its instruction set), but that hardly implies it was the first machine to use one. Did other kinds of computers start supporting multi-word arithmetic before the 4004?

Improve this question
13
  • Should I assume your 32-bit computer uses one's compliment? Otherwise it would probably be -32768.
    – wizzwizz4 ♦
    Nov 14 '16 at 17:36
  • 1
    @wizzwizz4: The stated requirement is that the program work correctly with values in the indicated range. If it also happens to work correctly with -32768, that would be fine too.
    – supercat
    Nov 14 '16 at 17:56
  • Even mechanical calculators like an abacus use a mechanical carry. It is one of the fundamental concepts of machine arithmetics. You could even say an abacus thus uses "multi-word arithmetics"
    – tofro
    Mar 8 '17 at 12:06
  • @tofro: Mechanical computing devices have nearly always included a mechanical carry mechanism, but it generally operates over a finite range. A typical abacus, for example, won't have anyplace to put carries which flow out of the top digit. Efficient carry propagation requires the ability to add three numbers (one of which will be zero or one) and produce two results (one of which will be a zero or one), and that can make things rather tricky.
    – supercat
    Mar 8 '17 at 15:15
  • 1
    @lvd: From what I understand of MIPS, two-word math is more than twice as expensive as one-word math, and four-word math would be more than twice as expensive as two-word math.
    – supercat
    May 10 '17 at 20:39
14

Babbage's analytic engine was designed to do arbitrary-precision aritmetic.

For multiplication, two 50-digit inputs produced a 100-digit output, with the lower 50 digits on the Egress Axis and the upper 50 on the Primed Egress Axis (this is comparable to how integer multiplication is handled in modern computers). Division, conversely, uses a 100-digit input on the Input Axis and Primed Input Axis to produce a quotient on the Primed Egress Axis and the remainder on the Egress Axis. Addition and subtraction set the "run-up lever", comparable to a combined carry and sign flag on modern computers, which could be used to control the conditional-branch instructions. Babbage outlined how this functionality could be used to perform arbitrary-precision arithmetic.

Improve this answer
4
  • Interesting, though I wonder why registers were so long if extended precision was practical? Did the machine use ten's-complement arithmetic for subtraction?
    – supercat
    Nov 14 '16 at 15:15
  • As Babbage noted, extended-precision is much slower than native precision (to translate his wording into modern terms, O(n^2)), and the 50-digit word length was intended to be sufficient for the near future. Keep in mind that the Analytic Engine's native number format was fixed-point, not floating-point, so the fast way to do computations on a number like 10^25 involves writing it out in full.
    – Mark
    Nov 14 '16 at 19:33
  • How much more hardware is required to perform a 50x50 multiply than would be required for 25x25 at the same speed? If half of the multiplies a program performs would fit in 25x25, a quarter are 25x50, and the rest 50x50, then each group of four multiplies with the above mix would require a total of eight 25x25 multiplies. If two 25x25 multiplies cost less than one 50x50 (I'd think even three 25x25 multiplies would cost less than one 50x50), using smaller operations would yield a performance win.
    – supercat
    Nov 14 '16 at 20:49
  • @supercat Yes, probably so. The sweet spot is likely 5, 10 and 20 digits actually, for the same reason that 16, 32 and 64 bit numbers are nice for general purpose use. This took a fair bit of time to realize, though -- and if you systematically apply the modern CS design perspective to the analytical engine, you'll end up with something like a cog-based RISC machine, rather than anything Babbage would recognize.
    – RETRAC
    Dec 16 '20 at 18:16
7

Did other kinds of computers start supporting multi-word arithmetic before the 4004?

The answer is a clear yes. For example, the IBM system/360 had a word size of 32 bits and add and subtract operations would set the "condition code" in the program status word.

http://bitsavers.informatik.uni-stuttgart.de/pdf/ibm/360/princOps/A22-6821-0_360PrincOps.pdf (page 24)

I think, if you investigate ancient computer architectures, a carry flag or equivalent would be the norm rather than the exception. After all, it's a pretty obvious idea to have - humans usually get introduced to the concept as children.

Early computers had large word sizes because why not? Carry flag or no carry flag, having a large word size is advantageous and the constraints were not as tight as with early microprocessors. Having a 48 bit word size (Manchester Atlas, Burroughs B5000) means more circuitry which means more power and more floor space but these are things that can easily be acquired for money. The early microprocessors were constrained by how many transistors you could squeeze on a piece of silicon with a reasonably high yield (of working chips) and also how many pins you could reasonably put on a dual inline package.

NB The 6502 didn't have arithmetic operations without carry. One of the gotchas for newbie programmers was that you had to clear the carry before doing an 8 bit addition and set the carry before doing an 8 bit subtraction.

Improve this answer
2
  • 6502 still has arithmetic operation without carry input -- it is compare instructions (CMP, CPX and CPY). It doesn't have additions and subtractions without carry, yes.
    – lvd
    May 10 '17 at 20:17
  • 1
    Compare operations are relational operations. That they work by doing a subtraction is an implementation detail. You could argue that that a > b is arithmetic if you like, in which case you'd be right but I don't think of them as arithmetic.
    – JeremyP
    May 11 '17 at 8:43
5

The IBM 1620. Not as early as the 702 mentioned in a different answer - but the earliest computer I've had direct use of (so this answer is based on hard-won knowledge).

The machine's memory stored decimal digits with a separate "flag" bit. There was no fixed "word length". Every arithmetic instruction (and most others, maybe all, I don't remember) operated on variable length fields delimited at the low order digit by a digit having the flag bit on. You addressed the lowest addressed digit: the high order digit. (We'd call that big-endian today but that term wasn't available then.) (The other use of the flag bit was at the high order digits: if it was on that was a negative number.)

So you could do arithmetic on numbers of any length whatsoever: true multi-precision arithmetic at the hardware level!

With only one minor caveat: The maximum memory available on an IBM 1620 was 60,000 decimal digits, and both operands (as well as your program!) had to fit in that space.

On a related note: The cheaper models of the 1620 didn't even have true arithmetic circuits. What they had was a lookup table at a specific location in lower memory. That table had to be loaded with values for proper base-10 arithmetic. And if you pervertedly changed that table you could do arithmetic in other bases, e.g., base 8 (octal). (The linked wikipedia article talks about this.) But it wasn't really practical.

The 1620 I used was a Model I with the full 60,000 digit memory. It also had a console typewriter, card reader/punch, a line printer, and a massive disk drive. (I mean the drive was massive: It was like a heavy washing machine. It would walk around the floor to the length of its cables if you ran a funny program that just did a seek to the inner cylinder, then a seek to the outer cylinder, and then repeat forever.) It's capacity was around 2 megadigits - and I guess that was pretty massive too, for its time.)

(Personal note: This was one of the first two computers I ever programmed. The local community college had one and they let me hang out in the "computer lab" when I was in high school. It was already totally obsolete, but it's what was available to them - and me. I programmed it in assembly and Fortran II. Lot's of fun! They also had several terminals connected to the school district's 360 mainframe which were hard-wired to APL. So that was the other first computer I ever programmed: An APL machine.)

(Bonus: Here's an old IBM 1620 front panel appearing in the movie Colossus: The Forbin Project as the control panel of the computer which took over the world! Look at the blinkin' lights!)

Improve this answer
11
  • Were the typewriter and card reader/punch the only forms of data interchange with the outside world? I would think tape drives would generally be desirable so as to allow "Simultaneous Peripheral Operation Off-Line"-ing, since tape I/O should be much faster than card-based or typewriter-based I/O.
    – supercat
    Mar 6 '19 at 16:23
  • AFAIK there were no tape drives available for the 1620. You could do bulk data transfer using the removable hard disk packs - it would work better if you had more than one disk drive of course (the computer I used had only one). And now I think of it we had a line printer - don't know how I could forget as that thing was noisy when running. Like one of those movies where everyone is shooting at each other for 10 minutes with fully automatic weapons that each have infinite bullets.
    – davidbak
    Mar 6 '19 at 16:27
  • Could the system process one job while feeding the stored results of the previous job from the disk to the printer, and loading the data for the next job from the card reader to the disk? It would seem like that would require a non-trivial but manageable amount of memory to support while a different program was running.
    – supercat
    Mar 6 '19 at 16:39
  • Job? Job? What is this "job" you speak of? Let me assure you that this small business-oriented computer did not have a multitasking O/S! In fact - at the hardware level it had neither asynchronous I/O nor interrupts! When you did an I/O operation that single instruction waited until the I/O was complete before moving on. For example: When the thing was typing to the console typewriter: One instruction = one character typed (or read) and while the "type bar" (the thing that hit the paper to make a letter mark) was moving that was the only thing the computer was doing. Slow!
    – davidbak
    Mar 6 '19 at 16:46
  • I had thought that one of the imperatives of early computer system designs was keeping the CPU busy. I wasn't expecting the system to have a multi-tasking OS, but it would seem that adding DMA, interrupts, or spooling hardware (e.g. feed up to X amount of data from the drive to the printer unless/until told to suspend such operations). If a many jobs would each require 30 seconds to load from cards, 30 seconds to "think", and 30 seconds to print, doing those operations separately would tie up the CPU for 90 seconds. Spooling could probably cut that time by 30% or more.
    – supercat
    Mar 6 '19 at 17:12
3

The carry is much older than the computer and a fundamental concept of arithmetics.

When we're going 5000 years back to ancient Sumerian mathematics and the invention of the abacus, the carry as a technical implement is already present - overflow in lower digits increases higher digits by one and resets the lower one. (hyper-retro-computing at its best, here...)

Most probably, the concept of a carry is even older than that - when you calculate using your fingers, you normally start using a carry quite intuitively once you get beyond 10.

The fact that the carry is only a carry flag in binary computers rather than a digit is only specific because computers are using binary arithmetics and thus only need one flag for one binary digit.

You could thus say it was the Neanderthal ten-finger computer that might have had it first. If you'd want a machine, it was definitely the abacus.

Improve this answer
1
  • 1
    Certainly the use of carry in hand computations predates computers, and is also used for mechanical or electronic computations within a register-sized quantity. In many early computing-machine designs, however the carry could only propagate for a fixed distance; my question is what early computers could propagate carry over arbitrary-sized quantities.
    – supercat
    Mar 8 '17 at 14:48
3

For the variable word-length computers, multi-precision arithmetic was the only mode of operation. The first computer among the listed in the wiki article, IBM 702, was announced in 1953.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.