Chapter 1 | Chapter 3 | |||||

## index | ||||||

## Back to Deley's Homepage |

Recall how we divide by hand:

<-- quotient +--------- 3 | 7.203125 <-- Dividend (starting Remainder R) | Divisor (D)

Step 1.

Choose a quotient digit:

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:

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

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.

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:

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:

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.

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

(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.

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.

_ 16 = 24 (i.e. 1*10 + 6 = 2*10 + -4)

Chapter 1 | Chapter 3 | |||||

## index | ||||||

## Back to Deley's Homepage |