## The Pentium division Flaw - Chapter 2

Chapter 1                   Chapter 3

## CHAPTER 2:    DIVISION

### 2.1    EXAMPLE

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.

### 2.2    ABSTRACT DIVISON

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

```

Repeat the above 3 steps until the desired number of quotient digits have been calculated.

### 2.3    THE ITERATIVE FORMULA FOR DIVISON

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)
```

### 2.4    BOUNDS ON RESULTING REMAINDER

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.

### 2.5    LOOKUP TABLE

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.

### 2.6    NEGATIVE QUOTIENT DIGITS

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)
```

Chapter 1                   Chapter 3