chained signed arithmetic

Starting from the very early plans in the mid 1830s, Babbage realized that if each individual operation needed to bring operands in from the Store and return the result to the Store, sequential operations on many operands would be very slow. So he allowed any number of additions and subtractions to be chained together in an arbitrary sequence, with intermediate results retained in the Mill and only written back at the end. 

The numbers were, of course, signed integers. In all his mature Plans, the Store holds them in sign-magnitude representation: one decimal wheel on top indicates, by being odd or even, whether the number is positive or negative. The rest of the wheels represent the absolute value of the number. This makes the numbers easy for a human to read on the column, and also simplifies multiplication and division. 

For addition and subtraction in the Mill, he uses 10's complement representation: a negative d-digit number N is stored as 10d-N. For example, a four-digit value of -2 is stored as 9998. That makes addition (or subtraction) work regardless of sign. 

Babbage had various schemes for how the signs would be handled in the Mill, most of which involved transmitting them as the top digit through the trains of pinions to the carriage so that a "running up" (overflow) into the sign wheel (for example, when computing a-b if b is larger than a) will change the sign. 

I'm experimenting with a different scheme that doesn't keep the sign information on wheels throughout the Mill, but instead holds it as a single bit of state information in the microcode. I think this results in a simplification of the hardware, at the expense of doubling the number of lines ("verticals" on the barrel) of microcode. But addition and subtraction doesn't take much microcode -- certainly not compared to multiplication and division -- so it shouldn't be a big deal.

My testbed, which I illustrated in the January 26th post but have further annotated here, consists of:

  • a Store with two dual-number 4-digit stacks with signs, and rack-restoring pinions
  • a one-place SIGN wheel for reading or writing the sign wheel of any Store number
  • a dual-number A register in the Mill
  • movable and fixed long pinions for shifting to/from the A register
  • an anticipating carriage that can add or subtract from the A register

the SIGN wheel in the Mill

Here is a video of the prototype in operation, computing (-7) - (-5) to produce (-2). That demonstrates conversions in both directions between sign-magnitude format in the Store and 10's complement format in the Mill.


Here is the pseudo-code that implements chained addition, chained subtraction, and writing back of the final results. Remember that readout in both the Mill and the Store is destructive and leaves the source set to zero.

boolean carriage_positive = TRUE

chain add
  read store to A and SIGN
  if carriage_positive
     if SIGN is positive
        add A to carriage
     else
        subtract A from carriage
        if RUNUP then carriage_positive = FALSE
   else
      if SIGN is positive
         add A to carriage
         if RUNUP then carriage_positive = TRUE
      else
         subtract A from carriage
         
chain subtract
   read store to A and SIGN
   if carriage_positive
      if SIGN is negative
         add A to carriage
      else
         subtract A from carriage
         if RUNUP carriage_positive = FALSE
   else
      if SIGN is negative
          add A to carriage
          if RUNUP carriage_positive = TRUE
      else
          subtract A from carriage

writeback
    load A from carriage
    if carriage_positive is FALSE
        subtract A from carriage; set SIGN negative
        load A from carriage
    write A to store
In all cases, restoring the rack after the "read store" happens in parallel with the first operation on the carriage, so it takes no time. Only the rack restoral after the final write of the result to the Store is not overlapped and adds to the total time.

Comments

Post a Comment