BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-89-1268
       ENTRY:: January 05, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Addition machines
        TYPE:: Technical Report
      AUTHOR:: Floyd, Robert W.
      AUTHOR:: Knuth, Donald E.
        DATE:: July 1989
       PAGES:: 17
    ABSTRACT:: An addition machine is a computing device with a finite
               number of registers, limited to the following six types of
               operations:

                   read x          {input to register x}
                   x <-- y         {copy register y to register x}
                   x <-- x + y     {add register y to register x}
                   x <-- x - y     {subtract register y from register x}
                   if x >= y       {compare register x to register y}
                   write x         {output from register x}

               The register contents are assumed to belong to a given set A,
               which is an additive subgroup of the real numbers. If A is
               the set of all integers, we say the device is an integer
               addition machine; if A is the set of all real numbers, we
               say the device is a real addition machine.

               We will consider how efficiently an integer addition machine
               can do operations such multiplication, division, greatest
               common divisor, exponentiation, and sorting. We will also
               show that any addition machine with at least six registers
               can compute the ternary operation x[y/z] with reasonable
               efficiency, given x, y, z in A with z not equal to 0.
       NOTES:: [Adminitrivia V1/RAM/19950105]
         END:: STAN//CS-TR-89-1268