G. ReichbornKjennerud
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 re mainders) and double the multiplier until the former is 1. For every odd multiplicand, add the respective multiplier. 

Example: 44 x 51  
Multiplicand  Multiplier  Partial Sum 
Column (c) Expressed in Terms of Original Multiplier 
Remainder of Division of Column (a) by 2 


(a) 
(b) 
(c) 
(d) 
(e) 

44 
51 


0 

22 
102 


0 

11 
204 
204 
4 x 51 
1 

5 
408 
408 
8x51 
1 

2 
816 


0 

1 
1632 
1632 
32 x 51 
1 

Total 
2244 = 
44 x 51 
101100 is binary for 44 




This algorithm readily lends itself to coding, as exemplified by the sequence in 8080 code shown in listing 1. 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.
Listing 1: An implementation of the Kenyan algorithm for integer multiplication for the 8080 microprocessor.
;multiplibation program MULT ;input multiplication factors in HL and DE, one of which must. ;necessarily be an 8bit number; if not, carry is set ;output product in DE, carry set if overflow. ;********************** Initial test to find 8bit factor MULT: xra a ;clear A ora d ;is D zero? jz found ;yes, DE number is 8bit fabtor xra a ;no, DE number was not 8bit factor ora h ;is H zero then? stc rnz ;no, return with carry set xchg ;yes, place 8bit factor in DE found: mov a,e ;transfer multiplicand to A ;********************** Multiplication starts in earnest lxi d,0 ;clear DE to receive output terms ana a ;8bit factor now in A; clear carry. next: rar ;halve the multiplicand; result odd? jnc even ;no, don't add multiplier term xchg ;yes, therefore, dad d ;add multiplier (now in DE) to output rb ;overflow, carry set on return xchg ;put multiplier back. in HL even: ana a ;already reached 1 by halving? rz ;Yes, retuPn with result, carry cleared dad h ;no, double the multip.lier and jnc next ;continue the process. ret ;overflow, carry set on return
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 O is recorded. Remarkably enough, the resultant sequence of 0's and 1's constitutes the quotient directly in binary form, as shown in table 2.
Procedure: Double the divisor until it is just less than the
divi dend. 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 Os constitute the binary form of the quotient. To ob
To obtain decimal accuracy, multiply the dividend initially by an 

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 = O  0  
Remainder:  2 

Quotient:  101100 = 44  
Notice that the procedure is quite mechanical, with none of the trialanderror search for the next correct quotient digit that is characteristic of the conventional method Furthermore, it lends itself beautifully to coding (see listing 2). There need be no 8bit restrictions on any of the numbers; the dividend, divisor, quotient, and remainder can all be entered as 16bit numbers.
Listing 2: An implementation of the author's integerdivision algorithm for the 8080 microprocessor.
;division program DIVIDE ;input dividend in BC and input divisor in HL. :output quotient in HL and output remainder in DE. ;carry set if division by zero ;********************** Test for division by zero and prepare DIVIDE: mov a,h ;for reverse polarity subtraction ora stc rz ;division by zero; abort operation; carry set mov a,b ;put 2's complement of BC +1 into DE for cma ;purposes of subtraction. (BC will be mov d,a ;incremented to enable subtraction when minuend mov a,c ;and subtrahend are having equal values). cma mov e,a ;dividend in negative form now in DE inx b ;BC +1; dividend incremented xra a ;reset counter A and sta quot ;clear the quotient buffer sta quot+1 ;(highorder part of quotient buffer) jmp double ;start the division in earnest ;*********************** First phase: Doubling the divisor restore:dad b ;add back double: inr a ;increment counter push h ;save divisor dad h ;double it, but go to second phase if jc change ;HL now is larger than dividend in B dad d ;comparison with dividend by subtraction jnc restore ;keep doubling unless HL now is larger than BC ;*********************** Second phase: Subtracting from the dividend ; and accumulating quotient bits. change: mov b,a ;transfer count to new counter subtrct:pop h ;Fetch halved divisor as positive subtrahend dad d ;subtract by using negative dividend as minuend jc shiftc ;the carry bit becomes the quotient bit xchg ;equivalent of adding back if subtraction fails shiftc: cmc ;invert quotient bit from reverse polarity lda quot ;shift quotient bits ral sta quot ;and place into temporary storage lda quot+l ral sta quot+1 dcr b ;countdown finished? jnz subtrct ;no, continue process lhld quot ;yes, place output quotient in HL. mov a,e ;change remainder in DE into proper polarity cma mov e,a mov a,d cma mov d,a ret ;division operation completed quot: d 2 ;buffer for evolving quotient
To handle 16bit numbers, the addtoitself DAD H instruction is used for doubling the divisor, and the necessary comparison with the dividend is accomplished by reversepolarity 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, reversepolarity 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. Machinecode algorithms can lead to odd but 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). 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.
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 microporcessors.
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 Os are represented by H, whereas the 1's 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 integermultiplication algorithm given in tables 3 and 4.
;multiplication program DADDY ;input multiplicand in DE and input multiplier in A ;output product in HL, carry set if overflow ;********************** Test for zero and leading zeroes, (8bit ; factor already determined and placed in A) DADDY: lxi h,0 ;clear output product register mvi b,8+1 ;set bit counter ana a ;is multiplier in A zero? (carry cleared) rz ;yes, skip multiplication operation; O in HL skip: dcr b ;check multiplier bit ral ;leading zero? jnc skip ;yes, ignore it and check next bit dad d ;no, load HL with multiplicand in DE; carry ; cleared ;********************** Multiplication starts in earnest next: dcr b ;more multiplier bits? rz ;no, return with result in HL dad h ;yes, do a DAD H, doubling the multiplicand rc ;overflow, carry set on return ral ;is the multiplier bit a l? jnc next ;no, check the next bit dad d ;yes, do a DAD D too, adding the initial jnc next ;check the next bit multiplicand ret ;overflow, carry set on return
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. Oh well, not everything is progress. But then, progress isn't everything.
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 

odd/even halved multipliers: 
Resultant 
Comment 

44 


44 
Double the multiplicand by adding to itself 
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 

file: /Techref/language/metal/math/muldiv.htm, 21KB, , updated: 1999/2/20 11:28, local time: 2024/10/9 02:14,
©2024 PLEASE DON'T RIP! THIS SITE CLOSES OCT 28, 2024 SO LONG AND THANKS FOR ALL THE FISH!

©2024 These pages are served without commercial sponsorship. (No popup ads, etc...).Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE. Questions? <A HREF="http://www.piclist.com/Techref/language/metal/math/muldiv.htm"> Novel Methods of Integer Multiplication and Division</A> 
Did you find what you needed? 
PICList 2024 contributors:
o List host: MIT, Site host massmind.org, Top posters @none found  Page Editors: James Newton, David Cary, and YOU! * Roman Black of Black Robotics donates from sales of Linistep stepper controller kits. * Ashley Roll of Digital Nemesis donates from sales of RCL1 RS232 to TTL converters. * Monthly Subscribers: Gregg Rew. ongoing support is MOST appreciated! * Contributors: Richard Seriani, Sr. 
Welcome to www.piclist.com! 
.