Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-12-23
2003-07-22
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06598065
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to data processing systems generally and particularly to perform a floating point division operation on a data processing system.
BACKGROUND
Floating point division operations often begin computing a quotient in a computer by generating an estimate of the reciprocal of the divisor first. Then the estimate of the reciprocal is further refined, or in other words, the precision of the estimate's mantissa is increased to exceed a threshold value, before the estimated reciprocal is applied to produce the quotient.
The Institute of Electrical and Electronic Engineers (IEEE) provides a standard for floating point arithmetic and correct results. This standard is entitled “An American National Standard—IEEE Standard For Binary Floating-Point Arithmetic”, ANSI/IEEE std. 754-1985 (hereinafter IEEE
754
standard). One prior art approach, described in Cocanougher et al., U.S. Pat. No. 5,249,149 (hereinafter Cocanougher), discloses a method of performing a floating point division conforming to this IEEE
754
standard.
Specifically, the prior art approach obtains a correctly rounded-to-nearest quotient with two prerequisite conditions. The conditions are: 1) the reciprocal of the divisor is correctly rounded, except for one special case; and 2) the initial estimated quotient is known to be within 1 unit-in-the-last-place (ulp) of the correct quotient. The following further illustrates this prior art approach by mathematical equations:
Equation 1: |q′−a/b|<=1 ulp of a/b, where a/b represents “the correct quotient”, and q′ represents “the initial estimated quotient”
Equation 2: y′=rounded (1/b), where 1/b represents “the true reciprocal of the divisor”, and y′ represents a rounded value of (1/b).
Equation 3: when y′ is correctly rounded (except for one special case), then q
final
′ (or “correctly rounded-to-nearest quotient”) can be obtained by performing the following:
r′=rounded (a−b*q′)
q
final
′=rounded (q′+r′*y′)
Although this prior art approach provides one method of performing floating point division and producing a correctly rounded quotient, satisfying the two required conditions described above can be difficult. Specifically, obtaining a correctly rounded y′ often demands iterations of calculating an error parameter and a y′ value associated with the error parameter. These iterations consume clock cycles and as a result negatively impact the overall performance of a floating point division operation.
Therefore, a method and apparatus is needed to further speed up the process of obtaining a correctly rounded quotient.
SUMMARY OF THE INVENTION
A method and apparatus for performing a floating point division of a dividend (a) by a divisor (b) to produce a correctly rounded-to-nearest quotient (q′) having a mantissa of P bits in a data processing system is disclosed.
In one embodiment, the data processing system computes a current quotient estimate (q
m
′, where m represents an integer and m>=0) that is within 1 ulp of a true quotient (a/b). Then the data processing system computes a current remainder estimate (r
m
′) based on the dividend (a), the divisor (b) and the current quotient estimate (q
m
′). The data processing system also computes a current reciprocal estimate (y
n
′, where n represents an integer and n>=0) based on a reciprocal intermediate value (E) with a relative error with respect to a true reciprocal of the divisor (1/b) of less than or equal to z/(2
2P
) (where z is an integer derived from error analyses of computations of the current reciprocal estimate (y
n
′)).
Finally, the data processing system obtains the correctly rounded-to-nearest quotient (q′), except possibly when z>=(2
P
−M
b
) (where M
b
represents mantissa of the divisor, b), based on the current remainder estimate (r
m
′), the current reciprocal estimate (y
n
′) and current quotient estimate (q
m
′).
REFERENCES:
patent: 5249149 (1993-09-01), Cocanougher et al.
patent: 5341321 (1994-08-01), Karp et al.
patent: 5515308 (1996-05-01), Karp et al.
patent: 5671170 (1997-09-01), Markstein et al.
patent: 5928318 (1999-07-01), Araki
patent: 6115733 (2000-09-01), Oberman et al.
Marius Cornea-Hasegan, Proving the IEEE of Iterative Floating-Point Square Root, Divide, and Remainder Algorithms, pp. 1-11, Intel Technology Journal Q2'98.
P.W. Markstein, Computation of elementary functions on the IBM RISC System/ 6000 Processor, Jan. 1990, pp. 111-119, vol. 34 No. 1.
LandOfFree
Method for achieving correctly rounded quotients in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for achieving correctly rounded quotients in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for achieving correctly rounded quotients in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3042156