Our last example involves an important task -- multiplying two integers. There are many subtleties involved, which we will try to steer clear of in this discussion.
Multiplication by 2 or powers of 2 can be accomplished easily by shifting to the left, i.e. towards the MSB (most significant bit). Multiplication by other numbers is harder, although it can be done by some interesting tricks. (See Section 16.4 for some of these tricks).
But multiplying 3783×18926 requires a general multiplication algorithm. An obvious algorithm involves picking the smaller of the two numbers and using it as a counter, repeatedly adding the other number to an ongoing sum. In the case of 3783×18926, this would mean 3783 additions: 0 + 18926 + 18926 + 18926 + ...
Computers are fast, but this is ridiculous, especially if millions of multiplications must be done every second. Therefore, a trick from the 3rd grade is used: multiply one number by just one digit of the second number, and then shift this product over by one place and add that to an ongoing sum:
18926
× 3783
--------
56778 (18926 × 3)
151408 (18926 × 8, shifted left 1 place)
132482 (18926 × 7, shifted left 2 places)
56778 (18926 × 3, shifted left 3 places)
---------
71597058
Things are actually much simpler in the world of binary multiplication since multiplying by a single digit is as simple as copying the number or inserting 0. The algorithm we will use multiplies only unsigned binary numbers, and in fact only multiplies two 8-bit numbers to form a 16-bit product. Thus, the upper 8 bits of the two numbers we multiply must be 0.
These numbers are traditionally called the multiplier and the multiplicand. They form a product, which can be at most 16 bits long. This is true of any number system: the number of digits in the product can be at most twice the number of digits in the multiplier or multiplicand, if they are the same length.
The algorithm proceeds as follows: Assign one value to the multiplier slot, the other to the multiplicand slot. Set the product to 0 initially and have a counter that is initially set to 8. Then do the following algorithm:
while the counter0 if the msb of multiplier is 1 then add the multiplicand to the product else add 0 to the product shift the multiplier one bit left subtract 1 from the counter if the counter > 0 then shift the product one bit to the left
Though it might not seem like it, this is almost the same algorithm as we learned in 3rd grade to multiply two large numbers.
Below is a complete example of 205×43 = 8815, or in binary
11001101 × 00101011 = 0010001001101111
The multiplier is 205 and the multiplicand is 43. There is no particular reason to prefer one assignment over the other, unlike the stupid multiplication algorithm above which did too many additions.
Each cycle of the multiplication process, as given by the while loop above, is separated graphically from the next by a dashed line.
counter partial product multiplier
---------------------------------------------------------------------------
00001000 00000000 00000000 11001101
+ 00101011 add 43-------- ^
------------------
00000000 00101011
00000111 (decr) 10011010
(lshift)
not zero 00000000 01010110 (lshift)
---------------------------------------------------------------------------
00000111 00000000 01010110 10011010
+ 00101011 add 43-------- ^
------------------
00000000 10000001
00000110 (decr) 00110100
(lshift)
not zero 00000001 00000010 (lshift)
---------------------------------------------------------------------------
00000110 00000001 00000010 00110100
+ 00000000 add 0--------- ^
------------------
00000001 00000010
00000101 (decr) 01101000
(lshift)
not zero 00000010 00000100 (lshift)
---------------------------------------------------------------------------
00000101 00000010 00000100 01101000
+ 00000000 add 0--------- ^
------------------
00000010 00000100
00000100 (decr) 11010000
(lshift)
not zero 00000100 00001000 (lshift)
---------------------------------------------------------------------------
00000100 00000100 00001000 11010000
+ 00101011 add 43-------- ^
------------------
00000100 00110011
00000011 (decr) 10100000
(lshift)
not zero 00001000 01100110 (lshift)
---------------------------------------------------------------------------
00000011 00001000 01100110 10100000
+ 00101011 add 43-------- ^
------------------
00001000 10010001
00000010 (decr) 01000000
(lshift)
not zero 00010001 00100010 (lshift)
---------------------------------------------------------------------------
00000010 00010001 00100010 01000000
+ 00000000 add 0--------- ^
------------------
00010001 00100010
00000001 (decr) 10000000
(lshift)
not zero 00100010 01000100 (lshift)
---------------------------------------------------------------------------
00000001 00100010 01000100 10000000
+ 00101011 add 43-------- ^
------------------
00100010 01101111
00000000 (decr) 00000000
(lshift)
zero do not shift
---------------------------------------------------------------------------
The underlined MSB of the multiplier is what is examined to see if we should add the multiplicand or not. If it is 1, we add the multiplicand, if 0 then don't. This bit is actually the N condition bit.
This algorithm may look tedious and complicated but it is a marvelously compact and efficient way of doing general multiplication. Real computers use algorithms that are very much like this, only they must deal with negative numbers as well as positives.
The following CSC-1 program implements the above multiplication algorithm.
0: LOD C ; This first section shifts the 1: SHL ; multiplier over 8 bits so that 2: SHL ; we can use the N bit to see if 3: SHL ; we must add or not. 4: SHL 5: SHL 6: SHL 7: SHL 8: SHL 9: STD CTEMP 10: LOOP: LOD CTEMP ; Load the shifted multiplier 11: JP NOADD ; If MSB>=0, then don't add 12: JZ NOADD ; 13: LOD A ; If MSB=1, add multiplicand in B 14: ADD B ; to the product in A. 15: STD A 16: NOADD: LOD CTEMP ; Load and shift multiplier left 17: SHL ; by one bit. 18: STD CTEMP 19: LOD CTR ; Subtract 1 from counter. 20: SUB ONE 21: JZ ENDLOOP ; If counter is 0, we're done! 22: STD CTR ; 23: LOD A ; Else shift product left one bit 24: SHL 25: STD A 26: JMP LOOP ; Go back to top of loop 27: ENDLOOP: HLT 27: 28: A: NUM 0 ; Product (16 bits) 29: B: NUM 13 ; Multiplicand (8 bits) 30: C: NUM 26 ; Multiplier 31: CTR: NUM 8 ; Used to count down 32: CTEMP: NUM 0 ; Holds copy of C which gets 32: ; destroyed 33: ONE: NUM 1 ; Constant +
There are some tricky things about the assembler version of this program. One is that the multiplier is repeatedly shifted until nothing (all 0s) is left. This might not be good during debugging so a copy is made in CTEMP to preserve its original value.
Another subtle feature is that the multiplier's MSB must be in bit 15, but the multiplier is only an 8-bit number. Thus, 8 left shifts are done before the main loop starts in order to bring its MSB into position so we can examine it via the N bit.