Processing unit having decimal floating-point divider using Newton-Raphson iteration

• US 20060064454A1
• Filed: 11/05/2004
• Published: 03/23/2006
• Est. Priority Date: 09/23/2004
• Status: Active Grant

• Current Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Original Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Inventors: Schulte, Michael J., Wang, Liang-Kai
• Granted Patent: US 7,467,174 B2
• Time in Patent Office: Days
• US Class Current: 708/651
• CPC Class Codes: G06F 1/035 Reduction of table size G06F1/0314 takes precedence
• CPC Class Codes: G06F 2101/12 Reciprocal functions
• CPC Class Codes: G06F 2207/4911 Decimal floating-point representation
• CPC Class Codes: G06F 2207/5355 Using iterative approximation not using digit recurrence, e.g. Newton Raphson or Goldschmidt
• CPC Class Codes: G06F 7/4873 Dividing
• CPC Class Codes: G06F 7/496 Multiplying; Dividing
• CPC Class Codes: G06F 7/49963 Rounding to nearest G06F7/49957 takes precedence
• CPC Class Codes: G06F 7/49968 Rounding towards positive infinity G06F7/49957 takes precedence
• CPC Class Codes: G06F 7/49973 Rounding towards negative infinity, e.g. truncation of two's complement numbers G06F7/49957 takes precedence
• CPC Class Codes: G06F 7/49978 Rounding towards zero G06F7/49957 takes precedence
• CPC Class Codes: G06F 7/49984 Rounding away from zero

Abstract

A decimal floating-point divider is described that implements efficient hardware-based techniques for performing decimal floating-point division. The divider uses an accurate piecewise linear approximation to obtain an initial estimate of a divisor'"'"'s reciprocal. The divider improves the initial estimate of the divisor'"'"'s reciprocal using a modified form of Newton-Raphson iteration. The divider multiplies the estimated divisor'"'"'s reciprocal by the dividend to produce a preliminary quotient. The preliminary quotient is rounded to produce the final decimal floating-point quotient.

Claims

1. A method comprising:

receiving a decimal floating-point dividend and a decimal floating-point divisor with a decimal floating-point divider; and

performing Newton-Raphson iterations with the decimal floating-point divider to output a decimal floating-point quotient.

2. The method of claim 1, further comprising converting the dividend and the divisor to binary coded decimal (BCD) prior to performing the Newton-Raphson iterations with the decimal floating-point divider.

3. The method of claim 1, wherein the dividend and the divisor conform to the IEEE-754 decimal format.

4. The method of claim 1, further comprising:

accessing a lookup table to retrieve a decimal coefficient using a portion of the divisor as an index into the lookup table; and

computing an initial approximation of the divisor'"'"'s reciprocal based on the coefficient.

5. The method of claim 4, further comprising:

performing the Newton-Raphson iterations with the decimal floating-point divider to compute an improved estimate of the divisor'"'"'s reciprocal; and

multiplying the dividend by the improved approximation to produce a preliminary quotient.

6. The method of claim 5, further comprising:

rounding the preliminary quotient; and

outputting the decimal floating-point quotient based on the rounded preliminary quotient.

7. The method of claim 4, further comprising storing the decimal coefficient within the lookup table in a densely packed decimal (DPD) format.

8. The method of claim 1,

wherein the decimal floating-point divider comprises a decimal multiplier, and

wherein performing Newton-Raphson iterations comprises performing Newton-Raphson iterations with the decimal multiplier.

9. The method of claim 1, further comprising:

accessing a lookup table to retrieve a decimal coefficient using a portion of the divisor as an index into the lookup table; and

computing an initial approximation of the divisor'"'"'s reciprocal based on the coefficient,

wherein performing Newton-Raphson iterations comprises computing an improved estimate by performing the following for each of the Newton-Raphson iterations;

(a) computing a nine'"'"'s complement of the 2G+2 most significant fraction digits of X×

R_i to calculate calculates an approximation V≈

(2−

X×

R_i), where i represents the i^th iteration, X represents the divisor, R_i represents the approximation for the divisor'"'"'s reciprocal for the i^th iteration, G is the accurate fraction digit for R_i, where G=2k−

3 when i=0; and

(b) computing the next approximation for the divisor'"'"'s reciprocal R_i+1=R_i×

V.

10. A method comprising:

receiving a decimal dividend and a decimal divisor with a decimal floating-point divider;

accessing a lookup table to retrieve a decimal coefficient using a portion of the divisor as an index into the lookup table;

computing an initial approximation of the divisor'"'"'s reciprocal based on the coefficient;

iteratively computing an improved estimate of the divisor'"'"'s reciprocal with the decimal floating-point divider;

multiplying the dividend by the improved approximation of the divisor'"'"'s reciprocal to produce a preliminary decimal quotient;

computing a biased decimal quotient from the preliminary decimal quotient; and

outputting a decimal quotient based on the biased decimal quotient.

11. The method of claim 10, further comprising multiplying the biased decimal quotient with the decimal divisor to obtain a trial dividend for determining rounding and correction signals.

12. The method of claim 10, wherein iteratively computing an improved estimate comprises performing Newton-Raphson iterations.

13. A processing unit comprising a decimal floating-point divider that performs Newton-Raphson iterations to output a decimal floating-point quotient.

14. The processing unit of claim 13, wherein the decimal floating-point divisor comprises inputs to receive a decimal dividend and a decimal divisor.

15. The processing unit of claim 14, wherein the decimal floating-point divisor comprises conversion modules to convert the dividend and the divisor to binary coded decimal (BCD).

16. The processing units of claim 14, wherein the dividend and the divisor conform to the IEEE-754 decimal format.

17. The processing unit of claim 13, wherein the decimal floating-point divisor comprises a lookup module that stores decimal data for use in computing an initial approximation of the divisor'"'"'s reciprocal.

18. The processing unit of claim 17, wherein the lookup module stores a coefficient for use in computing the initial approximation.

19. The processing unit of claim 17, wherein the lookup module stores the decimal data in densely packed decimal (DPD) format.

20. The processing unit of claim 17, wherein the lookup module is indexed by the k most significant digits of a significand of a divisor in DPD format and outputs the decimal data in DPD format.

21. The processing unit of claim 13, wherein the decimal floating-point divisor comprises:

inputs to receive a decimal dividend and a decimal divisor; and

a decimal multiplier to compute an initial approximation of the divisor'"'"'s reciprocal.

22. The processing unit of claim 21, wherein the initial approximation is given according to the following equation:

$R_0=\frac{X_m+\stackrel{\_}{X_L}+{10}^{-n}}{{\left(X_M+5\times <br><br>{10}^{-k-1}\right)}^2},$

where X_M represents a k-digit more significant part of an n-digit divisor, X, and X_L represents an (n−

k)-digit less significant part of X.

23. The processing unit of claim 21, wherein the decimal multiplier perform the Newton-Raphson iterations to compute an improved approximation of the divisor'"'"'s reciprocal based on the initial approximation.

24. The processing unit of claim 23, wherein the decimal multiplier multiplies the dividend by the improved approximation of the divisor'"'"'s reciprocal to produce a preliminary quotient.

25. The processing unit of claim 24, further comprising:

a rounding unit to round the preliminary quotient; and

a data post-processing unit to output the decimal floating-point quotient based on the rounded preliminary quotient.

26. The processing unit of claim 25, wherein the rounding unit supports a plurality of selectable rounding modes.

27. The processing unit of claim 21, further comprising:

a lookup module that stores decimal data for use in computing the initial approximation of the divisor'"'"'s reciprocal, wherein the lookup module is indexed by k most significant digits of a significand of the divisor in DPD format; and

a nine'"'"'s complement block;

wherein the nine'"'"'s complement block and the decimal multiplier calculate an approximation V≈

(2−

X×

R_i) by taking the nine'"'"'s complement of the 2G+2 most significant fraction digits of X×

R_i and setting the integer digit to one, where X represents the divisor, R_i represents the approximation for the divisor'"'"'s reciprocal for the i^th iteration, G=2k−

3,

wherein the decimal multiplier further computes an improved approximation for the divisor'"'"'s reciprocal as R_i+1=R_i×

V.

28. The processing unit of claim 27, wherein the decimal multiplier processes one digit per cycle.

29. The processing unit of claim 21, wherein the decimal multiplier comprises a fixed-point multiplier.

30. The processing unit of claim 13, wherein the decimal floating-point divider approximately doubles the number of accurate digits for each of the iterations.

31. The processing unit of claim 13, wherein the decimal floating-point divider processes a 64-bit (16-digit) decimal division in about 150 cycles.

32. A decimal floating-point divider comprising:

inputs to receive a decimal floating-point dividend and a decimal floating-point divisor;

a nine'"'"'s complement block;

a decimal multiplier;

wherein the nine'"'"'s complement block and the decimal multiplier compute an initial approximation of the divisor'"'"'s reciprocal,

wherein the decimal multiplier further (a) performs Newton-Raphson iterations to compute an improved approximation of the divisor'"'"'s reciprocal based on the initial approximation, and (b) multiplies the dividend by the improved approximation to produce a preliminary decimal quotient, and (c) performs an adjustment to the preliminary decimal quotient to produce a biased decimal quotient, and (d) multiplies the divisor by the biased decimal quotient to generate signals for rounding and correction; and

a processing unit to output a decimal floating-point quotient based on the biased decimal quotient.

33. The decimal floating-point divider of claim 32, wherein the decimal multiplier approximately doubles the number of accurate digits for each of the iterations.

34. The decimal floating-point divider of claim 32, wherein the decimal multiplier comprises a fixed-point multiplier.