Unit 12.2 -- Does Fast Division (using shifts)
Prog
Do Fast Division
PED
to learn how to do fast division
Concept
result
______________
divisor) dividend
R3 = one in appropriate position
shift divisor left by appropriate number of spaces
while more bits in divisor
if divisor<dividend
dividend=dividend-divisor
result=result+R3
shift divisor one space to right
shift R3 one space to right
42.html
Unit 12.2 Does Fast Division (using shifts)
How do we do division on paper? I.E., how did we learn to do
division in third or fourth grade?
Remember that we call the three numbers involved in a division,
the divisor, the dividend and the quotient. Remember that we
divide the dividend by the divisor yielding the quotient:
quotient
__________________
divisor ) dividend
A simple "long-division" would be:
123
_______
123 ) 15129
12300
_____
2829
2460
____
369
369
___
0
Note that in the case of "12300" what we did is shift the 123
left an appropriate number of places. We then determined that
12300*1 multiplied by 1 was the correct number. This was because
12300*2 was greater than 15129.
Thus we put the digit, 1, in the appropriate place in the
quotient. We then subtracted 1*12300 from the current quotient.
Now the new "current quotient" is 2829.
We now determine that we should see how many times the 1230 can
fit into 2829. The answer is two times. Thus we put the 2 in
the next place in the quotient. We subtract 2*1230 from the
current quotient to get "369"
And now we shift 1230 one digit to the right. We now get "123"
and we see how many times the "123" fits into 369. The answer is
three times. Thus, we put the 3 in the next place, the last
place, in the quotient. We subtract 3*123 from the current
quotient to get zero.
As we have shifted the 123 all the way to the right, we stop.
Of course, if there was anything left in the "current quotient,"
that would be the remainder.
Now, how do we divide in binary?
The first thing we have to do is shift the number to the left, an
appropriate number of times. For example, if are dividing a 32
bit number by a 32 bit number, then it would appear that we would
shift left 32 times. But, there is a problem with that.
When we shift to the left n times, n bits from the left hand side
go into the "bit bucket," i.e., they disappear. Thus, we cannot
shift left 32 times. In fact, we cannot reasonably divide one 32
bit number by another.
We have decided to divide a 32-bit fullword by a 16 bit number.
Thus, we shift left only 16 times, initially.
The next significant part of the division is figuring out for
each place in the quotient, what digit we put there. This is
done by taking the shifted number and compare it to the division
so far. Since, the only digits that are possible in the quotient
are zero and one, if the number is less than this quantity we put
a zero in the quotient. If it is greater than or equal, we
subtract the shifted divisor from the division so far and put a
one in the appropriate place.
Putting a one in the quotient is done by keeping a register
containing the "thingtoadd." This starts out as a one shifted to
the left, 16 places. Each time through the loop as we are
computing a digit, a little closer to the right of the number, we
shift this thingtoadd one space to the right.
These techniques are illustrated in the PASCAL program below. d1
represents the dividend and d2 represents the divisor. That is,
we are computing d1/d2. We will ignore the remainder in this
example. The first thing done is shifting the divisor, d2, to
the left 16 places. This could be done in one step by
multiplying by 216, but since PASCAL doesn't support the power
capability, a loop is provided. The IBM360 can do this in a
single SLL, shift left logical. Result, which will contain the
quotient, will be initialized to zero. (Note, so that the
program looks like the IBM 360, we use the phrase "longint" so we
get 32 bit words instead of the 16 bit words we would normally
get.)
Thingtoadd is initialized to a 1 followed by sixteen binary
zeros. TurboPascal supports hex constants, and we do an
initialization using that capability. The "$00010000" is Turbo
Pascal's syntax for the hex constant X'00010000'.
In our program, "r5" is a temporary variable corresponding to the
use of register 5 for the same purpose in the assembler program.
If d1 is greater than or equal to d2, we subtract and add a
number to the quotient. Otherwise, we do nothing. Note that we
divide "thingtoadd" by two so the next one added will end up in
the next place, and we also shift the divisor over by one.
Now let's see the equivalent ASSEMBLER to this PASCAL. Note the
register table in the documentation. Line 13 gets the divisor
into register 0 which then gets shifted left 16 places in line
14. Line 15 gets the dividend in register 1. We initialize the
result to zero and set the thingto add to the right place in
lines 16 and 17. The loop starts and the count is checked in
lines 19 to 21. We do the computation of d1-d2 in lines 22 and
23 and the check with zero in lines 24 to 25. If we fall
through, we do the insertion of the bit by adding "thingtoadd"in
line 26 and make the appropriate subtraction from the dividend in
line 27. The two shifts at the end of the loop are done in lines
29 and 30. We increment "i" and end theloop in lines 31 to 33.
Line 34 puts our result in a memory location.
94.PAS