Efficient error-check and exact-check for Newton-Raphson divide and square-root operations

1. A method for performing both error-check and exact-check operations for a Newton-Raphson divide or square-root computation, comprising:

in an arithmetic unit in a computing device,

performing Newton-Raphson iterations followed by a multiply for a divide or a square-root operation to produce a result, that includes one or more additional bits of accuracy beyond a desired accuracy for the result;

rounding the result to the desired accuracy to produce a rounded result t; and

analyzing the additional bits of accuracy to determine whether t is correct and whether t is exact;

wherein, if there are k additional bits and n=2 k , analyzing the additional bits involves using n to compare to a value j contained in the additional bits.

2. The method of claim 1 ,

wherein while analyzing the additional bits, if it is not possible to determine whether t is correct, the method further comprises performing an additional error-check computation to determine whether t is correct;

wherein while analyzing the additional bits, if it is not possible to determine whether t is exact, the method further comprises performing an additional exact-check computation to determine whether t is exact; and

wherein the process of analyzing the additional bits ensures that it is sometimes possible to determine either whether t is correct or whether t is exact, or both, whereby it is not necessary to perform both an additional error-check computation and/or an additional exact-check computation.

3. The method of claim 2 , wherein while analyzing the additional bits, if it is possible to determine both whether t is correct and whether t is exact, no additional error-check or exact-check computations are performed.

4. The method of claim 1 , wherein if the Newton-Raphson operation divides a by b to produce a result which is rounded down to t, analyzing the additional bits involves:

if j<n−1, determining that t is correct and inexact; and

if j=n−1, computing g=((t+1)*b)−a, and if g>0, determining that t is correct, and otherwise determining that t+1 is correct, and determining that t+1 exact if and only if g=0.

5. The method of claim 1 , wherein if the Newton-Raphson operation divides a by b to produce a result which is a result that is rounded to the nearest representable value t, analyzing the additional bits involves:

if j<(n/2)−1, determining that t is correct and inexact;

if j=(n/2)−1, determining t is inexact, and computing g=((t+½)*b)−a,

wherein if g>0, determining that t is correct,

wherein if g<0 determining that t+1 is correct,

wherein if g=0 and the least-significant bit (LSB) of t is on, determining that t+1 is correct, and

wherein if g=0 and the LSB of t is off, determining that t is correct; and

if n/2≦j<n−1, determining that t is correct and inexact; and

if j=n−1, determining that t is correct, and computing g=(t*b)−a, and determining that t is exact if and only if g=0.

6. The method of claim 1 , wherein if the Newton-Raphson operation divides a by b to produce a result which is rounded up to t, analyzing the additional bits of accuracy involves:

if j<n−1, determining that t is correct and inexact; and

if j=n−1, computing g=(t*b)−a, and if g<0 determining t+1 is correct and otherwise determining that t is correct, and determining that t is exact if and only if g=0.

7. The method of claim 1 , wherein if the Newton-Raphson operation computes a square-root of a radicand b to produce a result that is rounded down to t, analyzing the additional bits involves:

if j<n−1, determining that t is correct and inexact; and

if j=n−1, determining that t is inexact, and computing g=((t+1)*(t+1))−b, and if g>0, determining that t is correct, and otherwise determining that t+1 is correct, and determining that t+1 is exact if and only if g=0.

8. The method of claim 1 , wherein if the Newton-Raphson operation computes a square-root of a radicand b to produce a result that is rounded to the nearest representable value t, analyzing the additional bits involves:

if j<(n/2)−1, determining that t is correct and inexact;

if j=(n/2)−1, determining that the correct answer is inexact, and computing g=((t+½)*(t+½)−b,

wherein if g>0, determining that t is correct,

wherein if g<0 determining that t+1 is correct; and

if n/2≦j<n−1, determining that t is correct and inexact; and

if j=n−1, determining that is t is correct, and computing g=(t*t)−b, and determining that t is exact if and only if g=0.

9. The method of claim 1 , wherein if the Newton-Raphson operation computes a square-root of a radicand b to produce a result that is rounded up to t, analyzing the additional bits involves:

if j<n−1, determining that t is correct and inexact; and

if j=n−1, computing g=(t*t)−b, and if g<0 determining t+1 is correct and otherwise determining t is correct, and determining that t is exact if and only if g=0.

10. An apparatus that performs both error-check and exact-check operations for a Newton-Raphson divide or square-root computation, comprising:

a processor;

memory coupled to the processor;

an arithmetic unit configured to perform Newton-Raphson iterations followed by a multiply for a divide or a square-root operation to produce a result, which includes one or more additional bits of accuracy beyond a desired accuracy for the result;

wherein the arithmetic unit is configured to round the result to the desired accuracy to produce a rounded result t;

wherein the arithmetic unit is configured to analyze the additional bits of accuracy to determine whether t is correct and whether t is exact; and

wherein, if there are k additional bits and n=2 k , analyzing the additional bits involves using n to compare to a value j contained in the additional bits.

11. The apparatus of claim 10 ,

wherein while analyzing the additional bits, if it is not possible to determine whether t is correct, the arithmetic unit is configured to perform an additional error-check computation to determine whether t is correct;

wherein while analyzing the additional bits, if it is not possible to determine whether t is exact, the arithmetic unit is configured to perform an additional exact-check computation to determine whether t is exact; and

wherein the process of analyzing the additional bits ensures that it is sometimes possible to determine either whether t is correct or whether t is exact, or both, whereby it is not necessary to perform both an additional error-check computation and/or an additional exact-check computation.

12. The apparatus of claim 11 , wherein while analyzing the additional bits, if it is possible to determine both whether t is correct and whether t is exact, the arithmetic unit is configured to perform no additional error-check or exact-check computations.

13. The apparatus of claim 10 , wherein if the Newton-Raphson operation divides a by b to produce a result which is rounded down to t, while analyzing the additional bits:

if j<n−1, the arithmetic unit is configured to determine that t is correct and inexact; and

if j=n−1, the arithmetic unit is configured to compute g=((t+1)*b)−a, and if g>0, to determine that t is correct, and otherwise to determine that t+1 is correct, and to determine that t+1 exact if and only if g=0.

14. The apparatus of claim 10 , wherein if the Newton-Raphson operation divides a by b to produce a result which is a result that is rounded to the nearest representable value t, analyzing the additional bits:

if j<(n/2)−1, the arithmetic unit is configured to determine that t is correct and inexact;

if j=(n/2)−1, the arithmetic unit is configured to determine t is inexact, and to compute g=((t+½)*b)−a,

wherein if g>0, the arithmetic unit is configured to determine that t is correct,

wherein if g<0 the arithmetic unit is configured to determine that t+1 is correct,

wherein if g=0 and the least-significant bit (LSB) of t is on, the arithmetic unit is configured to determine that t+1 is correct, and

wherein if g=0 and the LSB of t is off, the arithmetic unit is configured to determine that t is correct; and

if n/2≦j<n−1, the arithmetic unit is configured to determine that t is correct and inexact; and

if j=n−1, the arithmetic unit is configured to determine that t is correct, and to compute g=(t*b)−a, and to determine that t is exact if and only if g=0.

15. The apparatus of claim 10 , wherein if the Newton-Raphson operation divides a by b to produce a result which is rounded up to t, while analyzing the additional bits:

if j<n−1, the arithmetic unit is configured to determine that t is correct and inexact; and

if j=n−1, the arithmetic unit is configured to compute g=(t*b)−a, and if g<0, to determine t+1 is correct, and otherwise to determine that t is correct, and determining that t is exact if and only if g=0.

16. The apparatus of claim 10 , wherein if the Newton-Raphson operation computes a square-root of a radicand b to produce a result that is rounded down to t, while analyzing the additional bits:

if j<n−1, the arithmetic unit is configured to determine that t is correct and inexact; and

if j=n−1, the arithmetic unit is configured to determine that t is inexact, and to compute g=((t+1)*(t+1))−b, and if g>0, to determine that t is correct, and otherwise to determine that t+1 is correct, and to determine that t+1 is exact if and only if g=0.

17. The apparatus of claim 10 , wherein if the Newton-Raphson operation computes a square-root of a radicand b to produce a result that is rounded to the nearest representable value t, while analyzing the additional bits:

if j<(n/2)−1, the arithmetic unit is configured to determine that t is correct and inexact;

if j=(n/2)−1, the arithmetic unit is configured to determine that the correct answer is inexact, and to compute g=((t+½)*(t+½)−b,

wherein if g>0, the arithmetic unit is configured to determine that t is correct,

wherein if g<0 the arithmetic unit is configured to determine that t+1 is correct; and

if n/2≦j<n−1, the arithmetic unit is configured to determine that t is correct and inexact; and

if j=n−1, the arithmetic unit is configured to determine that is t is correct, and computing g=(t*t)−b, and determining that t is exact if and only if g=0.

18. The apparatus of claim 10 , wherein if the Newton-Raphson operation computes a square-root of a radicand b to produce a result that is rounded up to t, while analyzing the additional bits:

if j<n−1, the arithmetic unit is configured to determine that t is correct and inexact; and

if j=n−1, the arithmetic unit is configured to compute g=(t*t)−b, and if g<0, to determine t+1 is correct and otherwise to determine t is correct, and determining that t is exact if and only if g=0.

19. A computer that performs both error-check and exact-check operations for a Newton-Raphson divide or square-root computation, comprising:

a processor;

a memory;

an arithmetic unit within the processor configured to perform Newton-Raphson iterations followed by a multiply for a divide or a square-root operation to produce a result, which includes one or more additional bits of accuracy beyond a desired accuracy for the result;

wherein the arithmetic unit is configured to round the result to the desired accuracy to produce a rounded result t;

wherein the arithmetic unit is configured to analyze the additional bits of accuracy to determine whether t is correct and whether t is exact; and

wherein while analyzing the additional bits, if there are k additional bits and n=2 k , the arithmetic unit is configured to use n to compare to a value j contained in the additional bits.

20. The computer system of claim 19 ,

wherein while analyzing the additional bits, if it is not possible to determine whether t is correct, the arithmetic unit is configured to perform an additional error-check computation to determine whether t is correct;

wherein while analyzing the additional bits, if it is not possible to determine whether t is exact, the arithmetic unit is configured to perform an additional exact-check computation to determine whether t is exact; and

wherein the process of analyzing the additional bits ensures that it is sometimes possible to determine either whether t is correct or whether t is exact, or both, whereby it is not necessary to perform both an additional error-check computation and/or an additional exact-check computation.

21. The computer system of claim 20 , wherein while analyzing the additional bits, if it is possible to determine both whether t is correct and whether t is exact, the arithmetic unit is configured to perform no additional error-check or exact-check computations.