Method and apparatus for performining floating point division

• US 5,249,149 A
• Filed: 09/03/1991
• Issued: 09/28/1993
• Est. Priority Date: 01/13/1989
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cocanougher, Daniel, Markstein, Peter W.
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US07/755,588
• Time in Patent Office: 756 Days
• Field of Search: 364/748, 364/765
• US Class Current: 708/504
• CPC Class Codes: G06F 2207/5351 Multiplicative non-restoring division, e.g. SRT, using multiplication in quotient selection
• CPC Class Codes: G06F 2207/5355 Using iterative approximation not using digit recurrence, e.g. Newton Raphson or Goldschmidt
• CPC Class Codes: G06F 2207/5356 Via reciprocal, i.e. calculate reciprocal only, or calculate reciprocal first and then the quotient from the reciprocal and the numerator
• CPC Class Codes: G06F 7/4873 Dividing
• CPC Class Codes: G06F 7/49957 Implementation of IEEE-754 Standard
• CPC Class Codes: G06F 7/535 Dividing only

Abstract

A method for performing floating point division is provided for producing a quotient having a mantissa of n bits. The method consists of the steps of accessing an initial guess of a reciprocal of the divisor from a table of divisor reciprocals, computing an initial estimate the quotient in a corresponding estimate from the initial estimate of the reciprocal, increasing the precision of the mantissa of the reciprocal estimate, quotient estimate, and remainder estimate by computing an error parameter and iteratively computing a current reciprocal estimate, a current quotient estimate and a current remainder estimate from the error parameter and the latest reciprocal estimate, quotient estimate and remainder estimates. Also, the step of increasing the precision is repeated until the quotient estimate and reciprocal estimate exceed n bits. Lastly, the final quotient is computed from the last current quotient estimate plus the last current reciprocal estimate times the last current remainder estimate. A floating point apparatus is also provided that implements the floating point division method. The application of this method and apparatus provide a quotient result that is correctly rounded without conditionally testing the magnitude of the quotient.

Claims

1. In a data processing system including a memory and having a multiplying circuit connected to an adding circuit, said adding circuit connected to a rounding circuit, and a control circuit connected to the multiplying, adding and rounding circuits, a method for performing floating point division of a dividend by a divisor for producing a quotient having a mantissa of N bits, said method comprising said steps of:

(1) accessing an initial reciprocal guess of a divisor from a table of divisor reciprocals in said memory by said control circuit;

(2) computing an initial guess of said quotient by multiplying said reciprocal guess by the dividend in said multiplying circuit and computing a corresponding remainder guess from said initial reciprocal guess by multiplying said divisor by said quotient guess in said multiplying circuit producing a first product followed by adding said dividend to said first product in said connected adding circuit producing a first sum followed by rounding said first sum in said connected rounding circuit, wherein said multiplying, adding and rounding circuits are regulated by said control circuit;

(3) computing an error parameter and iteratively computing a current reciprocal guess, a current quotient guess and a current remainder guess from said error parameter and said initial reciprocal guess, initial quotient guess and initial remainder guess wherein for each current guess computation a multiplying operation is performed in said multiplying circuit followed by an adding operation in said adding circuit followed by a rounding operation in said rounding circuit;

(4) repeating step 3 until said precision of said reciprocal guess and said quotient guess exceeds N bits wherein for each current guess computation a multiplying operation is performed in said multiplying circuit followed by an adding operation in said adding circuit followed by a rounding operation in said rounding circuit; and

(5) computing a final quotient wherein a last current reciprocal guess is multiplied by a last remainder guess in said multiplying circuit providing a final product followed by adding a last current quotient guess to said final product in said adding circuit providing a final sum followed by rounding the final sum in said rounding circuit.

2. A method according to claim 1 wherein said step (1) includes said steps of (1a) determining when said divisor mantissa is all binary ones and (1b) if said divisor mantissa is all binary ones, selecting said initial guess from a set of numbers equal to or greater than an actual magnitude of said reciprocal.

3. A method according to claim 2 wherein said step (5) includes a step of providing an indication that said final quotient is exact when and only when said remainder magnitude is zero.

4. In a data processing system including a memory and a multiplying circuit connected to an adding circuit and said adding circuit connected to a rounding circuit, the multiplying circuit, adding circuit and rounding circuit each connected to a control circuit, a method for performing floating point division of a dividend by a divisor for producing a quotient having a mantissa of N bits, said method comprising said steps of:

(1) accessing an initial reciprocal guess of a divisor from a value from said memory;

(2) computing an initial guess of said quotient from said initial guess of said reciprocal by multiplying said reciprocal guess by the dividend in said multiplying circuit as regulated by the control circuit;

(3) computing an error parameter and computing a current guess of said reciprocal from said error parameter and said initial reciprocal guess wherein for each of said error parameter and current reciprocal guess computation, a multiplying operation is performed in said multiplying circuit followed by an adding operation in said adding circuit followed by a rounding operation in said rounding circuit all regulated by the control circuit;

(4) computing a current quotient guess from said current guess of said reciprocal wherein for the current quotient guess computation a multiplying operation is performed in said multiplying circuit followed by an adding operation in said adding circuit followed by a rounding operation in said rounding circuit;

(5) computing a current remainder guess from said current reciprocal guess and said current quotient guess wherein for the current remainder guess computation a multiplying operation is performed in said multiplying circuit followed by an adding operation in said adding circuit followed by a rounding operation in said rounding circuit;

(6) repeating steps 3, 4 and 5 until said precision of said reciprocal guess and said quotient guess exceeds N bits wherein for each current guess computation a multiplying operation is performed in said multiplying circuit followed by an adding operation in said adding circuit followed by a rounding operation in said rounding circuit;

(7) computing a final quotient wherein a last current reciprocal guess is multiplied by a last remainder guess in said multiplying circuit to provide a final product followed by adding a last current quotient guess to said final product in said adding circuit to provide a final sum followed by rounding the final sum in said rounding circuit.

5. A method according to claim 4 wherein said step (1) includes said steps of (1a) determining when said divisor mantissa is all binary ones and (1b) if said divisor mantissa is all binary ones, selecting said initial guess from a set of numbers equal to or greater than an actual magnitude of said reciprocal.

6. A method according to claim 5 wherein said step (1) further includes a step of selecting a round-to-nearest operation for rounding said initial reciprocal guess.

7. A method according to claim 6 wherein each of steps (2) through (6) includes a step of rounding by a round-to-nearest operation.

8. A method according to claim 7 wherein said step (7) includes a step of rounding by other than a round-to-nearest operation.

9. A method according to claim 8 wherein said step (7) includes a step of providing an indication that said final quotient is exact when and only when said remainder magnitude is zero.

10. In a data processing system including a memory and a multiplying circuit connected to an adding circuit and said adding circuit connected to a rounding circuit circuit, said multiplying, adding and rounding circuits each connected to a control circuit, a method for performing floating point division of a dividend by a divisor for producing a quotient having a rounded mantissa of N bit precision, said method comprising said steps of:

(1) accessing an initial reciprocal guess of a divisor from a value from said memory;

(2) computing an initial guess of said quotient from said initial guess of said reciprocal by multiplying said reciprocal guess by the dividend in said multiplying circuit and followed by rounding by a round-to-nearest operation in said rounding circuit, wherein said multiplying and rounding circuits are regulated by said control circuit;

(3) computing an error parameter and computing a current guess of said reciprocal from said error parameter and said initial guess of said reciprocal wherein for each of said error parameter and current reciprocal guess computations, a multiplying operation is performed in said multiplying circuit followed by an adding operation in said adding circuit followed by a round-to-nearest operation in said rounding circuit;

(4) computing a current quotient guess from said current guess of said reciprocal wherein for said current quotient guess computation, a multiplying operation is performed in said multiplying circuit followed by an adding operation in said adding circuit followed by a round-to-nearest operation in said rounding circuit;

(5) computing a remainder guess from said current reciprocal guess and said current quotient guess wherein for said remainder guess computation, a multiplying operation is performed in said multiplying circuit followed by an adding operation in said adding circuit followed by a round-to-nearest operation in said rounding circuit;

(6) repeating steps 3, 4 and 5 until precision of said reciprocal guess and said quotient guess exceeds N bits wherein for each current guess computation a multiplying operation is performed in said multiplying circuit followed by an adding operation in said adding circuit followed by a rounding operation in said rounding circuit; and

(7) computing a final quotient wherein a last current reciprocal guess is multiplied by a last remainder guess in said multiplying circuit providing a final product followed by adding a last current quotient guess to said final product in said adding circuit to provide a final sum followed by rounding by an operation other than a round-to-nearest operation in said rounding circuit.

11. A method according to claim 10 wherein said step (1) includes said steps of (1a) determining when said divisor mantissa is all binary ones and (1b) if said divisor mantissa is all binary ones, selecting said initial guess from a set of numbers equal to or greater than an actual magnitude of said reciprocal.

12. A method according to claim 11 wherein said step (1) further includes a step of selecting a round-to-nearest operation for rounding said initial reciprocal guess.

13. A method according to claim 12 wherein said step (7) includes a step of providing an indication that said final quotient is exact when and only when said remainder magnitude is zero.

14. In a data processing system an apparatus for performing floating point division of a dividend by a divisor for producing a quotient having a mantissa of N bits, said apparatus comprising:

a memory;

a multiplying circuit;

an adding circuit connected to said multiplying circuit;

a rounding circuit connected to said adding circuit;

a control circuit connected to said multiplying circuit, said adding circuit and said rounding circuit;

means for accessing an initial reciprocal guess of said divisor from a table of divisor reciprocals in said memory;

means for computing an initial guess of said quotient by multiplying said reciprocal guess by the dividend in said multiplying circuit and computing a corresponding remainder guess from said initial guess of said reciprocal by multiplying said divisor by said quotient guess in said multiplying circuit producing a first product followed by adding said dividend to said first product in said connected adding circuit producing a first sum followed by rounding said first sum in said connected rounding circuit, wherein said multiplying, adding and rounding circuits are regulated by said control circuit;

means, connected to said multiplying circuit, said adding circuit, said rounding circuit and said control circuit, for computing an error parameter and iteratively computing a current reciprocal guess, a current quotient guess and a current remainder guess from said error parameter and said initial reciprocal guess, initial quotient guess and initial remainder guess until said precision of said reciprocal guess and said quotient guess exceeds N bits wherein for each error parameter and current guess computation a multiplying operation is performed in said multiplying means followed by an adding operation in said adding circuit followed by a rounding operation in said rounding circuit;

means for computing a final quotient wherein a last current reciprocal guess is multiplied by a last remainder guess in said multiplying circuit providing a final product followed by adding a last current quotient guess to said final product in said adding circuit providing a final sum followed by rounding the final sum in said rounding circuit.

15. An apparatus according to claim 14 wherein said means for accessing includes means for determining when said divisor mantissa is all binary ones and means for selecting said initial guess from a set of numbers equal to or greater than an actual magnitude of said reciprocal in response thereto.

16. An apparatus according to claim 15 wherein said means for computing a final quotient includes means for providing an indication that said final quotient is exact when and only when said remainder magnitude is zero.

17. In a data processing system an apparatus for performing floating point division of a dividend by a divisor for producing a quotient having a mantissa of N bits, said apparatus comprising:

a memory;

a multiplying circuit;

an adding circuit connected to said multiplying circuit;

a rounding circuit connected to said adding circuit;

a control circuit connected to said multiplying circuit, said adding circuit and said rounding circuit;

means for accessing an initial reciprocal guess of said divisor from a value from said memory;

means for computing an initial guess of said quotient from said initial reciprocal guess by multiplying said reciprocal guess by the dividend in said multiplying circuit as regulated by the control circuit;

means, connected to said multiplying circuit, said adding circuit and said rounding circuit, for computing an error parameter and computing a current guess of said reciprocal from said error parameter and said initial guess of said reciprocal wherein for each of said error parameter and current reciprocal guess computation, a multiplying operation is performed in said multiplying circuit followed by an adding operation in said adding circuit followed by a rounding operation in said rounding circuit all regulated by the control circuit;

means, connected to said multiplying circuit, said adding circuit, said rounding circuit and said control circuit, for computing a current quotient guess from said current guess of said reciprocal wherein for the current quotient guess computation a multiplying operation is performed in said multiplying circuit followed by an adding operation in said adding circuit followed by a rounding operation in said rounding circuit;

means, connected to said multiplying circuit, said adding circuit, said rounding circuit and said control circuit, for computing a current remainder guess from said current reciprocal guess and said current quotient guess wherein for the current remainder guess computation a multiplying operation is performed in said multiplying circuit followed by an adding operation in said adding circuit followed by a rounding operation in said rounding circuit;

means, connected to said multiplying circuit, said adding circuit, said rounding circuit and said control circuit, for increasing precision of said current reciprocal, quotient and remainder guesses until said precision of said reciprocal guess and said quotient guess exceeds N bits wherein for each current guess computation a multiplying operation is performed in said multiplying circuit followed by an adding operation in said adding circuit followed by a rounding operation in said rounding circuit;

means, connected to said multiplying circuit, said adding circuit, said rounding circuit and said control circuit, for computing a final quotient wherein a last current reciprocal guess is multiplied by a last remainder guess in said multiplying circuit to provide a final product followed by adding a last current quotient guess to said final product in said adding circuit to provide a final sum followed by rounding the final sum in said rounding circuit.

18. An apparatus according to claim 17 wherein said means for computing said initial reciprocal guess includes a means for determining when said divisor mantissa is all binary ones and means for selecting said initial guess from a set of numbers equal to or greater than an actual magnitude of said reciprocal in response thereto.

19. An apparatus according to claim 18 wherein said means for computing said initial reciprocal further includes means for selecting a round-to-nearest operation for rounding said initial reciprocal guess.

20. An apparatus according to claim 19 wherein each means for computing current guesses includes means for rounding by a round-to-nearest operation.

21. An apparatus according to claim 20 wherein means for computing said final quotient includes means for rounding by other than a round-to-nearest operation.

22. An apparatus according to claim 21 wherein said means for computing said final quotient includes means for providing an indication that said final quotient is exact when and only when said remainder magnitude is zero.

23. In a data processing system an apparatus for performing floating point division of a dividend by a divisor for producing a quotient having a rounded mantissa of N bit precision, said apparatus comprising:

a memory;

a multiplying circuit;

an adding circuit connected to said multiplying circuit;

a rounding circuit connected to said adding circuit;

a control circuit connected to said multiplying circuit, said adding circuit and said rounding circuit;

means for accessing an initial reciprocal guess of said divisor from a value from said memory;

means for computing an initial guess of said quotient from said initial guess of said reciprocal by multiplying said reciprocal guess by the dividend in said multiplying circuit and followed by rounding by a round-to-nearest operation in said rounding circuit, wherein said multiplying and rounding circuits are regulated by said control circuit;

means, connected to said multiplying circuit, said adding circuit, said rounding circuit and said control circuit, for computing an error parameter and computing a current guess of said reciprocal from said error parameter and said initial guess of said reciprocal wherein for each error parameter and current reciprocal guess computation, a multiplying operation is performed in said multiplying circuit followed by an adding operation in said adding circuit followed by a round-to-nearest operation in said rounding circuit and said multiplying, adding and rounding circuits are regulated by said control circuit;

means, connected to said multiplying circuit, said adding circuit, said rounding circuit and said control circuit, for computing a current quotient guess from said current guess of said reciprocal wherein for said current quotient guess computation, a multiplying operation is performed followed by an adding operation followed by rounding by a round-to-nearest operation in said rounding circuit;

means, connected to said multiplying circuit, said adding circuit, said rounding circuit and said control circuit, for computing a remainder guess from said current reciprocal guess and said current quotient guess wherein for said remainder guess computation, a multiplying operation is performed in said multiplying circuit followed by an adding operation in said adding circuit followed by a round-to-nearest operation in said rounding circuit;

means for increasing precision of said current guesses of said reciprocal and quotient until said precision of said reciprocal guess and said quotient guess exceeds N bits wherein for each current guess computation a multiplying operation is performed in said multiplying circuit followed by an adding operation in said adding circuit followed by a rounding operation in said rounding circuit; and

means for computing a final quotient wherein a last current reciprocal guess is multiplied by a last remainder guess in said multiplying circuit providing a final product followed by adding a last current quotient guess to said final product in said adding circuit to provide a final sum followed by rounding by an operation other than a round-to-nearest operation in said rounding circuit.

24. An apparatus according to claim 23 wherein said means for computing said initial guess of said reciprocal includes means for determining when said divisor mantissa is all binary ones and means for selecting said initial guess from a set of numbers equal to or greater than an actual magnitude of said reciprocal in response thereto.

25. An apparatus according to claim 24 wherein said means for computing said initial guess of said reciprocal further includes means for selecting a round-to-nearest operation for rounding said initial reciprocal guess.

26. An apparatus according to claim 25 wherein said means for computing said final quotient includes a means for providing an indication that said final quotient is exact when and only when said remainder magnitude is zero.

27. A data processing system for performing a division operation on a dividend and a divisor, said system comprising:

a memory;

a multiplying circuit;

an adding circuit connected to said multiplying circuit;

a rounding circuit connected to said adding circuit;

a control circuit connected to said memory, multiplying circuit, adding circuit and rounding circuit and including means for obtaining an estimate of a divisor reciprocal from said memory, means for controlling computing of a quotient estimate and remainder estimate, and means for controlling repetitively computing an error parameter and iteratively recomputing current quotient estimates and current remainder estimates from a current error parameter until a previously specified quotient bit precision has been obtained.

28. A data processing system of claim 27 wherein said means for controlling computing and means for controlling repetitively computing provides a sequence of a multiplication operation in said multiplying circuit followed by an addition operation in said adding circuit followed by a rounding operation in said rounding circuit.