The following article was printed in June 1983 of the magazine „BYTE".
This article describes 16 bit integer multiplication and division.

Novel Methods of Integer Multiplication and Division


G. Reichborn-Kjennerud
Tandberg Data A/S
POB 9, Korsvoll, Oslo 8
Norway

You may be familiar with the method of multiplication, variously alleged to be of Kenyan, Russian, or even Himalayan origin, in which you repeatedly halve the multiplicand and double the multiplier until the multiplicand becomes 1. Then the sum of those multipliers that have a multiplicand counterpart of odd value becomes the product. This sounds complicated, but it's really not; table 1 shows an example.
Procedure: Repeatedly halve the multiplicand (discarding remainders) and double the multiplier until the former is 1. For each odd multiplicand, add the respective multiplier.
Example: 44 x 51
                                    Column (c)
                                    Expressed    Remainder
                                    in Terms of  of Division
                          Partial   Original     of Column
Multiplicand  Multiplier    Sum     Multiplier   (a)bit
    (a)          (b)        (c)       (d)          (e)

    44           51          -         -            0
    22          102          -         -            0
    11          204         204       4x51          1
     5          408         408       8x51          1
     2          816          -         -            0
     1         1632        1632      32x51          1
                           ----      -----          ^
                  Total    2244      44x51          |
              44 x 51 =    2244                     |
                101100 is binary for 44 <-----------+
Table 1: An example of the Kenyan double-and-halve algorithm for integer multiplication.

This algorithm readily lends itself to coding, as exemplified by the sequence in 8080 code shown in listing 1.
Listing 1: An implementation of the Kenyan algorithm for integer multiplication for the 8080 microprocessor.
[8080 source and optimized Z80 source]

Halving is done by shifting to the right, and the odd/even test is performed by checking the carry. Doubling is done by adding to itself using the DAD instruction, which is also used for summing up the output terms.
Repeated halving of a number and then noting the odd/even results is a nice way of finding the binary form of the number (the last bit found being the most significant one). It also tells something of the binary nature of the Kenyan method.
Some time ago I became intrigued by the possibility of finding a procedure for division that was similar to the Kenyan method of multiplication. I came up with the following scheme: The divisor is repeatedly doubled until just less than the dividend, then successively subtracted from the dividend. Every time the subtraction operation gives a positive result, a 1 is noted; otherwise a 0 is recorded. Remarkably enough, the resultant sequence of 0s and 1s constitutes the quotient directly in binary form, as shown in table 2.
Procedure: Double the divisor until it is just less than the dividend. Then try to subtract the doubled divisors, starting with the largest, from the dividend. Note a 1 if the subtraction is possible; otherwise, note a zero and do not perform the subtraction.
The 1s and 0s constitute the binary form of the quotient. To obtain the decimal form, multiply the latter digits with the corresponding terms in a power of 2 series, arranged in reverse order. The quotient is the sum of the resultant terms.
To obtain decimal accuracy, multiply the dividend initially by an Nth power of 10. Then, after the division is complete, divide the quotient by the same power of 10 (moving the decimal point N places).
Example: 2246/51
                                            Counter
Double:         51                            0
               102                            1
               204                            2
               408                            3
               816                            4
              1632                            5

Subtract:     2246
            - 1632
            ------
               614      1       x 32 = 32     5
            -  816
            ------
                        0       x 16 = 0      4
               614
            -  408
            ------
               206      1        x 8 = 8      3
            -  204
            ------
                 2      1        x 4 = 4      2
            -  102
            ------
                        0        x 2 = 0      1
                 2
            -   51
            ------
                        0        x 1 = 0      0
----------------------------------------------------------------------------------
Remainder:       2
Quotient:                                   = 44
                                     101100 = 44
                                   (binary)   (decimal)
Table 2: An example of a new method of integer division suitable for implementation on microprocessors without a divide instruction.

Notice that the procedure is quite mechanical, with none of the trial-and-error search for the next correct quotient digit that is characteristic of the conventional method. Furthermore, it lends itself beautifully to coding (see listing 2).
Listing 2: An implementation of the author's integer-division algorithm for the 8080 microprocessor.
[8080 source and optimized Z80 source]

There need be no 8-bit restrictions on any of the numbers; the dividend, divisor, quotient, and remainder can all be entered as 16-bit numbers.
To handle 16-bit numbers, the add-to-itself DAD H instruction is used for doubling the divisor, and the necessary comparison with the dividend is accomplished by reverse-polarity addition, using the negative value of the dividend (in the DE register pair) and testing on the carry. Care is taken to restore the divisor before the next doubling by adding back the positive value (in the BC register pair). The doubled divisors are put in temporary storage by pushing them to the stack.
For the necessary subtraction of the doubled divisors from the dividend, reverse-polarity addition is used again. Luckily, the dividend is already present in negative form (in the DE register pair), and the divisors can be used in their existing positive form as they are popped from the stack for subtraction. The carry is then indicative of a positive or negative result, and for every subtraction, it is shifted into a register pair to form the final quotient. A counter sees to it that there are no more subtractions than there were doubling operations. The contents of the DE register pair constitute the remainder (in complemented form).
As we have seen, odd ways of multiplying and dividing can lead to useful code algorithms. But the reverse can also be true. Machine-code algorithms can lead to odd bit perhaps not so useful manual methods.
First, consider a table used for multiplying by a fixed number K, based on using the 8080 DAD instruction (see table 3).
Procedure: Input multiplicand in both HL and DE register pairs. Constant K is the multiplier. Then perform a series of DAD D and DAD H instructions in the order given by the sequence of Ds and Hs under the given value of K. The final product will be in the HL register pair. If every DAD instruction is followed by a test of carry (JC or RC), carry will be set in case of overflow.
K =  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
DAD  H  H  H  H  H  H  H  H  H  H  H  H  H  H  H  H  H  H  H  H  H  H  H  H  H  H  H  H  H  H  H
DAD     D  H  H  D  D  H  H  H  H  D  D  D  D  H  H  H  H  H  H  H  D  D  D  D  D  D  D  D  H  H
DAD           D  H  H  H  H  D  D  H  H  H  H  H  H  H  H  D  D  D  D  H  H  H  H  H  H  H  H  H
DAD                 D     D  H  H  H  H  D  D  H  H  D  D  H  H  H  H  H  H  H  H  D  D  D  D  H
DAD                             D     D  H  H     D  H  H  H  H  D  D  H  H  D  D  H  H  H  H  H
DAD                                         D           D     D  H  H     D  H  H  H  H  D  D
DAD                                                                 D           D     D  H  H
DAD                                                                                         D
Table 3: An algorithm for integer multiplication for 8080 microprocessors.

The multiplicand is loaded into two register pairs (HL and DE), and the product is obtained by executing a sequence of DAD H and DAD D commands in the order given beneath each value of K (operand sequences for K = 2 to K = 32 have been included). DAD H doubles the accumulated multiplicand in the HL pair, and DAD D adds the original multiplicand to the HL pair.
It seems natural to look for a general algorithm based on DAD Hs and DAD Ds. If you look hard at table 3, you'll see a familiar pattern emerge: the Hs and Ds actually represent K in binary form. The 0s are represented by H, whereas the 1s are represented by H and D as a group. True, the most significant bit is missing, but that will always be a 1 anyway. As an example, consider K = 19. The sequence is H H (H D) (H D), which translates into (1) 0 0 1 1.
Thus, we can multiply by shifting the multiplier and examining the carry. When carry is cleared, we perform a DAD H operation, and when it is set, we do both a DAD H and a DAD D. This gives us the code in listing 3.
Listing 3: An implementation in 8080 assembly language of the integer-multiplication algorithm given in tables 3 and 4.
[8080 source and optimized Z80 source]

Now for the manual method that can be derived from this: Repeatedly halve the multipler until it becomes 1 (in order to find the binary form). Reverse the sequence of halved multipliers and ignore the 1. Repeatedly double the multiplicand. Whenever the corresponding halved multiplier is odd, add also the original multiplicand to the accumulated doubled multiplicands; table 4 gives us an example of this method.
Procedure: Repeatedly halve the multiplier (discarding remainders) until you reach 1. Ignore the 1 and arrange the resultant halved multipliers vertically in reverse order. For each halved multiplier, double the multiplicand. Add also the initial multiplicand if the halved multiplier is an odd number.
Example: 44 x 51
Repeatedly halve the multiplier: 51  25  12   6   3   1

Resultant                     44    Double the multiplicand
  odd/even halved             44      by adding to itself
  multipliers:     3         +44    Add initial multiplicand
                            ----
                             132
                             132
                            ----
                   6       +   0    Don't add initial multiplicand
                            ----
                             264
                             264
                  12       +   0
                            ----
                             528
                             528
                  25       +  44
                            ----
                            1100
                            1100
                  51        + 44

Final product:              2244
Table 4: An example of manual implementation of the algorithm of table 3.

Oh well, not everything is progress. But then, progress isn't everything.

Scanned by Werner Cirsovius
January 2005
© BYTE Publications Inc.