The Pentium division Flaw - Chapter 3

Chapter 2          Intel inside          Chapter 4
index
Back to Deley's Homepage



CHAPTER 3:    RADIX 4 SRT DIVISION


3.1    THE SRT DIVISION ALGORITHM

The SRT division algorithm was named after the 3 scientists who discovered it independently at about the same time: D. Sweeney of IBM, J.E. Robertson of the University of Illinois, and T.D. Tocher of the Imperial College of London.

The Pentium uses a Radix 4 SRT Division algorithm for floating point divisions. It's simply the division we've been doing above, except it's done in base 4, and the quotient digits we can choose are {-2,-1,0,1,2}.

(I think the reason we don't include 3 and -3 as possible quotent digits is because hardware to implement multiplies by anything other than a power of 2 is very expensive both in chip area and time. Multiplications by positive and negative powers of two are just shifts and inverts. Having radix 4 and the possible quotient digits of {-2,-1,0,1,2} meet the multiplication criteria nicely.)



3.2    THE ITERATIVE FORMULA FOR DIVISION BASE 4

Our iterative formula for base 4 is:

        R[j+1] = 4 * (R[j] - q[j]*D)                (3-1)



3.3    BOUNDS ON RESULTING REMAINDER

At the beginning of each iteration we must choose a quotient digit which will result in the next remainder R[j+1] being within the acceptable limits of:

             _ _____
        (D * 2.22222...) < R[j+1] < (D * 2.22222...)
             [base 4]                    [base 4]
                _
        where:  2 = lowest quotient digit we can use (-2)
                2 = highest quotient digit we can use

Using a little calculus we can show that:

           2.22222... (base 4) = 8/3 (decimal)

   Proof:  2.22222... = 2*(x0 + x1 + x2 + x3 +...)    [x = 1/4]
           (base 4)     (decimal)

                          Recall from calculus if |x| < 1 then:

                                                           1
                          (x0 + x1 + x2 + x3 +...) = -----
                                                         1 - x

                                1       8
                      =  2 * ------- = ---
                             1 - 1/4    3
   Q.E.D.


Similarly, it can be show that:

        _ _____
        2.22222... (base 4) = -8/3 (decimal)

Our restriction on the remainder R[j+1] thus becomes:

        (D * -8/3) < R[j+1] < (D * 8/3)


Substituting Eq. (3-1) for R[j+1] gives:

        (-8/3)*D  <  4*(R[j] - qD)  <  (8/3)*D          (3-2)

Given a remainder R[j] at the beginning of an iteration, we can now determine what values of q will satisfy the above restraint.

    FOR q=+2        (-8/3)*D < 4*(R[j] - 2*D) < (8/3)*D
    becomes:         (4/3)*D <    R[j]        < (8/3)*D

We may thus choose quotient digit 2 when our remainder R[j] is between (4/3)*D and (8/3)*D.

    FOR q=+1:       (-8/3)*D < 4*(R[j] - 1*D) < (8/3)*D
    becomes:         (1/3)*D <    R[j]        < (5/3)*D

We may thus choose quotient digit 1 when our remainder R[j] is between (1/3)*D and (5/3)*D.

FOR q=0: (-8/3)*D < 4*(R[j] - 0*D) < (8/3)*D becomes: (-2/3)*D < R[j] < (2/3)*D
We may thus choose quotient digit 0 when our remainder R[j] is between (-2/3)*D and (2/3)*D.

    FOR q=-1:       (-8/3)*D <4*(R[j] - (-1)*D) < (8/3)*D
    becomes:        (-5/3)*D <    R[j]          < (-1/3)*D

We may thus choose quotient digit -1 when our remainder R[j] is between (-5/3)*D and (-1/3)*D.

    FOR q=-2:       (-8/3)*D < 4*(R[j] - (-2)*D) < (8/3)*D
    becomes:        (-8/3)*D <    R[j]           < (-4/3)*D


We may thus choose quotient digit -2 when our remainder R is between (-8/3)*D and (-4/3)*D.

Notice there is some overlap in the choices of q:
If R is between (5/3)*D and (4/3)*D we can choose either q=2 or q=1.
If R is between (2/3)*D and (1/3)*D we can choose either q=1 or q=0.
If R is between (-1/3)*D and (-2/3)*D we can choose either q=0 or q=-1.
If R is between (-4/3)*D and (-5/3)*D we can choose either q=-1 or q=-2.


3.4    THE PENTIUM LOOKUP TABLE (P-D plot)

The above information leads to the following plot, called the Partial remainder vs. Divisor plot, or P-D plot for short. Dividing the plot up into cells generates a lookup table that we can use to aid us in choosing the next quotient digit q given the current remainder R[j]. The divisions up the vertical axis are 0.001 [binary] apart, representing R[j] values. The divisions across the horizontal axis are 0.0001 [binary] apart, representing Divisor values. (The divisor values range from 1 to 1.11111..., since a normalized divisor mantissa will always be in this range).

There are five red cells marked with a 0 near the top of the graph running along the (8/3)D line. These are the error cells that should specify a quotient digit of 2, but instead specify a quotient digit of 0. Selecting a quotient digit of 0 when R[j] is within this range is unacceptable -- the digit value is too low, and no matter what subsequent quotient digits are chosen the total quotient answer will always be lower than the correct answer from this point on. This is the Pentium flaw. Those five cells failed to get the proper value loaded into them when Intel made the chip.

These 5 error cells are very rarely used being positioned where they are and with less than half of each error cell actually below the (8/3)D line. It is also impossible to hit any of these error cells early on in the divison process, so even if an error cell is encountered the generated result will still be close to the correct answer.

THE PENTIUM P-D PLOT:

PD Plot

Let's look at this graph for a moment. There are diagonal lines (8/3)D, (5/3)D, (4/3)D, (2/3)D, (1/3)D, (-1/3)D, (-2/3)D, (-4/3)D, (-5/3)D, (-8/3)D. These lines would pass through the origin if we extended the graph to the left. These are the theoretical boundaries discussed above.

Above (8/3)D is out of bounds. If we ever end up there, something has gone wrong. The Pentium returns a value of q=0 if we ever hit this area.

Between (8/3)D and (5/3)D we must have q=2. Each cell which is in or partly overlaps this area must have the value 2. The five red error cells marked with have a value of 0 instead of 2.

Between (5/3)D and (4/3)D we can have either q=2 or q=1. The actual division line (as best as we know) is the staircase line drawn in brown. Cells above that staircase shaded light blue have q=2, cells below that staircase shaded yellow have q=1. Cells immediately above the division line, marked with a '?', are cells which might return either q=2 or q=1 depending upon other factors that will be discussed in chapter 4. [2004—I apologize, I no longer remember the reason for the '?' in these cells, and chapter 4 doesn't explain them. Chapter 4 does explain why every cell must return a value suitable also for the cell directly above it. The dividing lines shown here I believe are from Tim Coe's Source Code.]

Between (4/3)D and (2/3)D we must have q=1. Each cell which is in or partly overlaps this area must have the value 1.

Between (2/3)D and (1/3)D we can have either q=1 or q=0. The actual division line (as best as we know) is the staircase line drawn in brown. Cells above that staircase have q=1, cells below that staircase have q=0. Cells immediately above the division line, marked with a '?', are cells which might return either q=1 or q=0 depending upon other factors that will be discussed in chapter 4.

Between (1/3)D and (-1/3)D we must have q=0. Each cell which is in or partly overlaps this area must have the value 0.

Between (-1/3)D and (-2/3)D we can have either q=0 or q=-1. The actual division line (as best as we know) is the staircase line drawn in brown. Cells above that staircase have q=0, cells below that staircase have q=-1. Note this division staircase is not a mirror image of the one in the positive plane, but is instead shifted down by two cells. Cells immediately above the division line, marked with a '?', are cells which might return either q=0 or q=-1 depending upon other factors that will be discussed in chapter 4.

Between (-2/3) and (-4/3) we must have q=-1. Each cell which is in or partly overlaps this area must have the value -1.

Between (-4/3)D and (-5/3)D we can have either q=-1 or q=-2. The actual division line (as best as we know) is the staircase line drawn in brown. Cells above that staircase have q=-1, cells below that staircase have q=-2. Note again this division staircase is not a mirror image of the one in the positive plane, but is instead shifted down by two cells. Cells immediately above the division line, marked with a '?', are cells which might return either q=-1 or q=-2 depending upon other factors that will be discussed in chapter 4.

Between (-5/3)D and (-8/3)D we must have q=-2. Each cell which is in or partly overlaps this area must have the value -2. Note there are no error cells down here in the negative plane. The 5 error cells are all in the positive plane.

Below (-8/3)D is out of bounds. If we ever end up there, something has gone wrong. The Pentium returns a value of q=0 if we ever hit this area. (We actually do hit this area after hitting the error cell.)



3.5    ITERATION USING THE P-D PLOT AS A LOOKUP TABLE

The cells in the above graph define the lookup table used during the Pentium's SRT division process. The iteration goes something like this:

    Given:
    D - Divisor (note this value remains fixed)
    R - Dividend (initial Remainder)
Step 1:
Using D and R, look in P-D table above for next quotient digit q. Note that we need only know the first 4 digits after the radix point of the Divisor, and we need only know the first 3 digits after the radix point of the Remainder.

Step 2:
Do the math:
    R[j+1] = 4 * (R[j] - q*D)
Repeat steps 1 & 2 until enough quotient digits have been determined.





Chapter 2          Intel Inside          Chapter 4
index
Back to Deley's Homepage