Bit Computer Addition

Today, an addition algorithm for the bit-based computer. I thought up this algorithm without consulting a reference, but I have since discovered that it is listed in the famous MIT A.I. Laboratory "HAKMEM" as Item 23.

We can implement addition by dividing the 32-bit string into sub-strings representing numbers. These numbers could then be added and the result placed elsewhere in the string or written over the original numbers.

But what algorithm to use? It turns out there’s one that’s perfect, and an F# implementation is shown in the following recursive function:

let rec plus lhs rhs = 
  match rhs with 
  | 0 -> lhs
  | _ -> plus (lhs^^^rhs) ((lhs&&&rhs)*2)

That is, if rhs is zero, the answer is just lhs. If rhs is not zero, call the function recursively with the half-add (XOR) of the two numbers as the new lhs and the carry as the new rhs. To find the carry, do a bitwise AND left shift the result by one. (Note that the designation of lhs and rhs is arbitrary; the items in each of the two computations for the new parameters are commutative.)

Why is this perfect? For one thing, both the XOR and the AND are able to operate on pairs of bits asynchronously. This is nice, because the input value is (in effect) tested against the production rules asynchronously. The shift is synchronous, but if we have some way of latching the original bits this limitation can be ignored. And as it turns out, the fact that the input is tested first and asynchronously makes it work as a latch. Furthermore, since the input value is latched, and both lhs and rhs are discarded at each step, we can write the new result right back into the original bit registers!

The rules are fairly simple; the need to split the data between sections of the 32-bit word and the simultaneously updates and shifts presenting only minor problems. The first problem we will solve by limiting the initial test to 3-bit addends and use the nibble separator to keep them registered. Here is the template for the four rules that will be required at each bit position:

  0--:0--  ->  0---:---
  1--:0--  ->  0---:1--
  0--:1--  ->  0---:---
  1--:1--  ->  1---:0—

Some advantage can be gained by modifying the rules for the first bit position and for the final carry. The update of the first bit position is the appropriate place to shift the zero into the carry array. Since there is never an addend, only a carry in the last bit position, only one rule is required. Furthermore, since the state never changes after the carry addend becomes zero, there is no need for a special halt test.

Test code implementing the addition algorithm is shown below; the BC32 library is the same as that listed in an earlier post.

(As always, presented “as-is” and without warranty or implied fitness; use at your own risk. This technique does not, to my knowledge, infringe on any patents, however, the reader is responsible for making sure that such non-infringement is indeed the case for their particular uses.)

open System
open BC32


// This program adds the two three-bit numbers
// in the first two nibbles.  
// The technique is easily extended.
let Add3 =
  [
  // First bit is a special case.
  // Must zero out bit L.0.
  (ins "0:0" "0-:-" )
  (ins "1:0" "00:1" )
  (ins "0:1" "0-:-" )
  (ins "1:1" "10:0" )
  
  // Interior bits follow a pattern.
  
  (ins "0-:0-" "0--:--" )
  (ins "1-:0-" "0--:1-" )
  (ins "0-:1-" "0--:--" )
  (ins "1-:1-" "1--:0-" )
  
  (ins "0--:0--" "0---:---" )
  (ins "1--:0--" "0---:1--" )
  (ins "0--:1--" "0---:---" )
  (ins "1--:1--" "1---:0--" )
  
  // Last bit is a special case.
  // No high bit to test in R.
  // Must zero L high bit.
  (ins "1---:0---" "0---:1---" )
  
  // No need for a halt function.
  ]

// A little syntax helper function.
let runAdd3 l r = (snd (run 100 Add3 (((l&&&0x7)*16)+(r&&&0x7))))

// A few spot examples.
let x00_00 = runAdd3 0 0
let x01_01 = runAdd3 0 1
let x11_02 = runAdd3 1 1
let x22_04 = runAdd3 2 2
let x23_05 = runAdd3 2 3
let x50_05 = runAdd3 5 0
let x57_12 = runAdd3 5 7
let x66_12 = runAdd3 6 6
let x77_14 = runAdd3 7 7

// An exhaustive test.
for l in [0..7] do
  for r in [0..7] do
    if (runAdd3 l r)<>(l+r) then
      failwith "Some kind of error!"
printfn "No errors!"

printfn ""
printfn "Press any key to continue..."
Console.ReadLine() |> ignore