The Pentium division Flaw - Chapter 2
Recall how we divide by hand:
<-- quotient
+---------
3 | 7.203125 <-- Dividend (starting Remainder R)
|
Divisor (D)
Step 1.
Choose a quotient digit:
+-- quotient digit q
2
+---------
3 | 7.203125
Step 2.
Multiply quotient digit by Divisor.
Subtract result from Remainder to get New Remainder:
2
+---------
3 | 7.203125 <-- Remainder R
6 <-- (2 * 3 = 6)
---------
1.203125 <-- New Remainder R
Step 3.
To prepare for the next iteration, move the decimal point right one
place (multiply by 10):
2
+---------
3 | 7.203125
6
---------
1.203125 <-- New Remainder R
========
12.03125 <-- R = 10 * R
At this point our remainder R must be within the following acceptable limits:
0 <= R < 10*D ( D = Divisor, 3 in this example)
If the remainder R is below zero, then the quotient digit we chose in
step 1 was too high. If R is greater than or equal to 10*D, then the
quotient digit we chose in step 1 was too low.
We now repeat those three steps above for division in a more general abstract setting:
q - quotient digit
D - Divisor
R[j] - Remainder after the j'th iteration.
(The starting remainder R[0] is the Dividend.)
+---------
D | R[j] <-- Remainder
/
Divisor
Step 1.
Choose a quotient digit:
+-- quotient digit q
q
+---------
D | R[j]
Step 2.
Multiply quotient digit by Divisor.
Subtract result from Remainder to get New Remainder:
q
+---------
D | R[j]
-qD
---------
Rnew[j] <-- Rnew[j] = (R[j] - qD)
| Step 3. |
| To prepare for the next iteration, move radix point right one place.
(In base 10 the radix point is more familiarly known as the decimal
point, and we multiply by 10. In base 4, which the Pentium uses for
division, we multiply by 4.) |
q
+---------
D | R[j]
-qD
---------
Rnew[j] <-- Rnew[j] = (R[j] - qD)
========
R[j+1] = base * Rnew[j] (base = 10 for decimal
4 for radix 4)
Repeat the above 3 steps until the desired number of quotient digits
have been calculated.
Note steps 2 and 3 can be combined to give the following iterative
formula (this is THE iterative formula for performing division that we
will be referencing throughout the rest of this paper):
R[j+1] = base * (R[j] - q[j]*D)
Note that the minimum we can make the final quotient answer at this
point in the iteration is to have all subsequent quotient digits be
the smallest quotient digit possible. Likewise the maximum we can make
the final quotient answer at this point in the iteration is to have all
subsequent quotient digits be the largest quotient digit possible.
From this observation we can conclude that our remainder R[J=1] at this
point must be within the following range:
(D * n.nnnnn...) <= R[j+1] < (D * m.mmmmm...)
where: n = lowest quotient digit we can use
m = highest quotient digit we can use
If our remainder R[j+1] at this point is less than (D * n.nnnnn...),
then the correct quotient answer is less than the minimum we can make
our final quotient answer. Likewise if our remainder R[j+1] at this
point is greater than (D * m.mmmmm...) then the correct quotient answer
is greater than the maximum we can make our final quotient answer. In
the first instance our quotient answer will always be too high; in the
second instance our quotient answer will always be too low.
To aid us in determining what quotient digit to choose at each
iteration we can make ourselves a table showing remainder R[j] vs.
divisor D. Here is a simple table for doing base 10 (decimal)
division:
9 | 9 4 3 2 1 1 1 1 1
8 | 8 4 2 2 1 1 1 1 0
7 | 7 3 2 1 1 1 1 0 0
6 | 6 3 2 1 1 1 0 0 0
Current 5 | 5 2 1 1 1 0 0 0 0
Remainder 4 | 4 2 1 1 0 0 0 0 0
3 | 3 1 1 0 0 0 0 0 0
2 | 2 1 0 0 0 0 0 0 0
1 | 1 0 0 0 0 0 0 0 0
0 +------------------
0 1 2 3 4 5 6 7 8 9
For example if we have a divisor of 3 and a current remainder of 7, we
can look at our table and see that 2 is the correct next quotient digit
to choose. The Pentium uses a table such as this to determine what
quotient digit to choose next. The bug is some of the table entries
are incorrect. We'll look more closely at the Pentium's lookup table in
a moment.
We now introduce one last concept which may seem confusing at first but
it's actually fully legitimate and it results in a faster computer
division implimentation, which of course is the whole point. For our
base 10 division examples above we have implicitly restricted our
quotient digits to the usual set {0,1,...,8,9}. Consider what would
happen now if we allowed our quotient digits to also be negative,
{-9,-8,...,8,9} This would allow for some numbers to be represented in
more than one way. For example (using a bar over a number to represent
negation):
_
16 = 24 (i.e. 1*10 + 6 = 2*10 + -4)
