Unit 12.1 -- Does Fast Multiplication (using shifts)
Prog
Multiply integers together quickly
Standard approach to doing this in software
PED
Learn above algorithm
Concept
To do multiplicand
* multiplier
______________
result
DECIMAL
result = 0
while more digits in multiplier
result=result + (rightmost digit of multiplier)*
multiplicand
multiply mutiplicand by ten
shift multiplier one place to the right
BOOLEAN
result = 0
while more bits in multiplier
if rightmost bit of multiplier is one
result=result + multiplicand
shift multiplier one position to the right
shift multiplicand one position to the left
SF
none
41.LIS
Unit 12.1
Fast Multiplication Using Shfits
How do we multiply two numbers?
When we do multiplication of multiple-digit numbers, it
looks something like this:
123 first number
X123 second number
____
369
246
123
_____
15129 result
Note there are two fundamental operations:
1 multiplication of first number by each successive digit of the
result
2 addition of these numbers. (The numbers get shifted).
thus step one computes "369" when we multiply 123 by the 3 in the
right hand position,
"246" when we multiply "123" by the 2 in the middle digit
"123" when we multiply "123" by the 1 in the leftmost digit.
Step 2 adds them altogether. Then when we had the "369" it would
be added to the sum. Then we would compute "246" from "2" times
"123" and this would be added to the sum to get 369. Remember
that we shifted the second sum one digit to the right before
adding it.
Now, let's say we wanted to do this in binary.
Our digits are 0 and 1. It is real easy to multiply by a binary
digit. If the digit is one, the result is the number; otherwise,
it is zero.
We need to shift these before adding. No problem; we just learned
how to use the shift instruction. Each shift corresponds to
multiplying the item by 2.
Then we just add the shifted results; only if the corresponding
bit in the second number is on.
To illustrate these ideas before looking at the ASSEMBLER,
We look at a PASCAL program. Remember that shifting left gives
the same result as multiplying by two. Shifting right is done
using the div 2 operation.
For example if we have the bit pattern 0011 and we shift it left
one position that gives us the binary pattern 0110. Converting
these to decimal gives us 3 and 6. Notice that 0110 is the same
result.
If we have the bit pattern 0100 and we we shift it right one
position that gives us the bit pattern 0010. Converting these to
decimal gives us four and two. This is dividing by two.
(When doing multiplication, the top item is referred to as the
"multiplicand." The bottom item is the "multiplier.")
The loop proceeds for 31 bits. If the bit is on--"m2 mod 2 = 1",
we add the value of m1, the multiplicand shifted by the
appropriate power of two. We then shift m2, the multiplier, one
to the right. That way, the next time through the loop, when we
examine "m2 mod 2," we will look at the bit that was just to the
left in the original value of m2. We also shift m1, the
multiplicand, one to the right.
Now let's match the PASCAL program against the assembler code.
Lines 13 and 14, load up register 0 and register 1 with the
multiplicand and multiplier. Note the table of registers.
We also initialize register four, corresponding to sum, to zero.
In this program, the counter in register two goes down from 31 to
zero. (This corresponds to the number of the bits in IBM
mainframe.)
Line 17 begins the loop and line 18 through 19 does the
comparison of i with the value 31.
Line 21 and 22 does the "m2 mod 2." If the rightmost bit of a
number is on, then it is odd. A zero in the rightmost bit
signifies that hte result is even. We do the comparison in line
22. If the bit was on, then the and would produce a one in
register three. Otherwise, register three would be zero.
(Remember our discussion in the previous unit about how to check
if a given bit is on.)
If the bit is zero, we branch around the "AR 4,0" This
corresponds to the "sum := sum+ m1" statement. The "SRL 1,1,"
does the shifting of m2 right one position and "SLL 0,1" does the
shifting of m1 left one position. We increment "I" in line 28.
We store the final result in line 44.
{multiply two numbers, M1, and M2, the way the ASSEMBLER program
does it with shifts}
program main(input,output);
var sum,i,m1,m2:integer;
begin
read(m1);
read(m2);
sum:=0;
for i:=0 to 31 do begin
if m2 mod 2 = 1 then begin {if digit is one}
sum := sum+m1; {add shifted value}
end;
m2 := m2 div 2; {shift m2 right one position}
m1 : = m1 * 2; {shift m1 left one position}
end;
write(sum);
end.
Another way of looking at this program as an example of the
templates that go through each bit of a word. In this case we go
through each bit of the multiplier, regB. We go through each bit
from right to left. That corresponds to the template on page
101. regA is the counter going from 31 to 0 which as you can see
is register two in this example.
The code to do if the bit is on would be to add the current value
of the multiplicand to register four. We see that on line 24.
Note we don't do anything if the bit is off.