Programming Praxis

Today’s exercise examines three binary algorithms, for basic arithmetic: multiplication, division, and greatest common divisor.

Four millenia ago, when the ancient Egyptians were building the pyramids, they invented a method for multiplying positive integers that works like this: They start by writing the two numbers to be multiplied at the head of two columns. Then they repeatedly divide the number in the left column by two (right-shift), dropping any remainder, and double the number in the right column (left-shift), writing the two new numbers immediately below their predecessors, until the number in the left column is one. Then they cross out all rows where the number in the left column is even, and add the remaining numbers in the right column, which is the desired product. For instance, the product fourteen times twelve is found like this:

14  12
 7  24
 3  48
 1  96
   168

It is easy to see why this method works if you use the grade-school method of multiplication, but with binary numbers instead of decimal numbers:

        1 1 0 0                     1 2
        1 1 1 0                     1 4
        - - - -                     - -
        0 0 0 0       0 x 1 2         0
      1 1 0 0         2 x 1 2       2 4
    1 1 0 0           4 x 1 2       4 8
  1 1 0 0             8 x 1 2       9 6
  - - - - - - -     - -   - -     - - -
1 0 1 0 1 0 0 0     1 4 x 1 2     1 6 8

In binary, 14 is 1 · 2³ + 1 · 2² + 1 · 2¹ + 0 · 2⁰. The odd numbers in the left column correspond to the 1 bits in the binary representation of the multiplicand.

Binary division is the inverse operation to binary multiplication, and is also done by a series of doubling and halving operations. We’ll begin with the grade-school algorithm, in binary:

                        1 0 0 1 1
            - - - - - - - - - - -
1 0 1 0 1 1 ) 1 1 0 1 0 0 0 1 0 1           8 3 7
              1 0 1 0 1 1                   6 8 8 / 4 3 = 1 6
              - - - - - -                   - - -
                  1 0 0 1 0 1 0             1 4 9
                    1 0 1 0 1 1               8 6 / 4 3 =   2
                  - - - - - - -             - - -
                      1 1 1 1 1 1             6 3
                      1 0 1 0 1 1             4 3 / 4 3 =   1
                      - - - - - -             - -
                        1 0 1 0 0             2 0

The quotient has a 1 wherever the divisor is less than the current portion of the dividend, and a 0 where the next digit is “brought down” from the dividend. The algorithmic version of n ÷ d is based on a quantity d · 2^k, which we call t, which is initialized with the largest k that leaves t less than n; this can be done by repeated left shifts. Then the quotient q is initialized to zero, the remainder r is initialized to n, and an iteration continues halving t until t is less than the original d; at each stage of the iteration, the quotient is doubled (left-shift) if the current remainder is less than t, otherwise the quotient is doubled (left-shift), then one is added, and the current remainder is reduced by the current value of t. An example is shown below:

t    q  r
43
86
172
344
688
1376
688  0  837
344  1  149
172  2  149
86   4  149
43   9  63
43/2 19 20

Josef Stein described a binary algorithm for greatest common divisor in 1967 that was devised by Chinese mathematicians in the first century. The greatest common divisor of two numbers is calculated by a recursive algorithm with four rules:

• If either number is zero, their greatest common divisor is the other number.
• If both numbers are even, the two numbers share a factor of two, so their greatest common divisor is double (left-shift) the greatest common divisor of the halves (right-shift) of the two numbers.
• If one number is even and the other is odd, they have no factor of two in common, so their greatest common divisor is the greatest common divisor of the odd number and half (right-shift) the even number.
• Otherwise, both numbers are odd, and a normal Euclidean step is performed, replacing the larger of the two numbers with their difference.

Binary algorithms such as these are quite common; see for instance the ipow and expm functions in the Standard Prelude. They are especially useful for hardware implementations in the microcode of the processor, since bit-shifting operations are extremely fast.

Your task is to write functions that perform the three operations given above, simulating how they are performed in hardware. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2