High accuracy estimates of elementary functions

• US 6,163,791 A
• Filed: 02/02/1998
• Issued: 12/19/2000
• Est. Priority Date: 02/02/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Senziq, Donald Norman, Schmookler, Martin Stanley
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US09/017,233
• Time in Patent Office: 1,051 Days
• Field of Search: 708/605, 708/654, 708/502, 708/627-628
• US Class Current: 708/502
• CPC Class Codes: G06F 7/535 Dividing only
• CPC Class Codes: G06F 7/5525 Roots or inverse roots of single operands

Abstract

An improved method of estimating the square root, reciprocal square root, and reciprocal of an input value in a computer system. The input value, after being normalized, is used to select a pair of constants from a table. The constants are based on a linear approximation of the function for each interval of the input value, offset to reduce a maximum error value for a given interval. The estimated function is calculated by adding or subtracting the product of a part of the normalized input value and the first constant from the second constant. In one implementation, the input value is normalized within the range 1≦x<2, and one lookup table is used, having an interval size of 1/32. In a further preferred embodiment, only a lower order part of the mantissa is used in the multiply-add operation, to reduce the number of bits required (the high order part of the mantissa is used to select the constants from the table). In another implementation, the input value is normalized within the range 0.5≦x<2, and two lookup tables are used, a first table having an interval size of 1/32 for the range 0.5≦x<1, and a second table having an interval size of 1/16 for the range 1≦x<2.

Claims

1. A method of estimating the reciprocal of an input value in a computer system having a processor, comprising the steps of:

normalizing the input value to yield a normalized input value;

selecting a first constant and a second constant from a table stored in the computer system, the table having a plurality of intervals, based on the normalized input value, wherein said first and second constants are based on a linear approximation of the function 1/x using left and right edges of a given interval, offset to reduce a maximum error value for the given interval; and

calculating an estimated reciprocal using the processor by combining the product of the normalized input value and the first constant with the second constant in a logic unit of the processor.

2. The method of claim 1 wherein said normalizing step normalizes the input value within the range 1≦

x<

2.

3. The method of claim 1 wherein:

the normalized input value has a mantissa; and

said selecting step selects the first and second constants based on the most significant bits of the mantissa.

4. The method of claim 3 wherein the second constant is further based on the values of the left and right edges of a given interval, and said selecting step is accomplished using a high order part of the mantissa to reduce the number of bits required in a multiply-add operation.

5. The method of claim 1 wherein the first and second constants have sufficient precision such that the estimated reciprocal has a relative error less than 1/4096.

6. The method of claim 1 wherein the processor has a multiplier which uses a modified Booth recoder to reduce the number of levels of carry-save-adders, and further comprising the step of using the Booth recoding in parallel with the table to reduce an effective delay of the multiplier.

7. The method of claim 1 wherein at least two intervals in the table have the same value for the first constant.

8. A processor for a computer system, comprising:

a plurality of registers;

a plurality of logic units connected to said registers, including a floating-point execution unit allowing multiply-add operations; and

a table lookup for estimating a reciprocal of a normalized input value in one of said registers, said table lookup having a plurality of intervals and associated pairs of first and second constants used as inputs to said floating-point execution unit, said first and second constants being based on a linear approximation of the function 1/x using left and right edges of a given interval, offset to reduce a maximum error value for the given interval, such that the reciprocal is estimated by combining the product of the normalized input value and the first constant with the second constant.

9. The processor of claim 8 further comprising means for normalizing an input value within a range of said table lookup to produce the normalized input value.

10. The processor of claim 8 wherein said table lookup provides said first and second constants having sufficient precision such that the estimated reciprocal has a relative error less than 1/4096.

11. The processor of claim 8 wherein the normalized input value has a mantissa portion, and said second constant is further based on the values of the left and right edges of a given interval such that the product of the normalized input value and the first constant is calculated using a lower order part of the mantissa to reduce the number of bits required in a multiply-add operation.

12. The processor of claim 8 wherein at least two intervals in the table have the same value for the first constant.

13. A method of estimating the reciprocal square root of an input value in a computer system having a processor, comprising the steps of:

normalizing the input value to yield a normalized input value;

selecting a first constant and a second constant from a table stored in the computer system, the table having a plurality of intervals, based on the normalized input value, wherein said first and second constants are based on a linear approximation of the function 1/√

x using left and right edges of a given interval, offset to reduce a maximum error value for the given interval; and

calculating an estimated reciprocal square root using the processor by combining the product of the normalized input value and the first constant with the second constant in a logic unit of the processor.

14. The method of claim 13 wherein said normalizing step normalizes the input value within the range 0.5≦

x<

2.

15. The method of claim 13 wherein:

the normalized input value has a mantissa; and

said selecting step selects the first and second constants based on the most significant bits of the mantissa.

16. The method of claim 15 wherein the second constant is further based on the values of the left and right edges of a given interval, and said selecting step is accomplished using a high order part of the mantissa to reduce the number of bits required in a multiply-add operation.

17. The method of claim 16 wherein said selecting step selects the first and second constants by first selecting the table from a plurality of different tables corresponding to different intervals of the normalized input value.

18. The method of claim 13 wherein said selecting step selects the first and second constants by first selecting the table from a plurality of different tables corresponding to difference intervals of the normalized input value.

19. The method of claim 18 wherein:

said normalizing step normalizes the input value within the range of 0.5≦

x<

2;

the first and second constants have sufficient precision such that the estimated reciprocal square root has a relative error less than 1/4096; and

said selecting step selects the first and second constants from a first table having an interval size of 1/32 for the range 0.5≦

x<

1, and a second table having an interval size of 1/16 for the range 1≦

x2.

20. The method of claim 13 wherein the first and second constants have sufficient precision such that the estimated reciprocal square root has a relative error less than 1/4096.

21. The method of claim 13 further comprising the step of calculating an estimated square root of the input value by multiplying the input value with the estimated reciprocal square root.

22. The method of claim 21 further comprising the step of improving the precision of the estimated square root by using the estimated reciprocal square root as a first approximation in a Newton-Raphson iteration.

23. The method of claim 13 wherein the processor has a multiplier which uses a modified Booth recoder to reduce the number of levels of carry-save-adders, and further comprising the step of using the Booth recoding in parallel with the table to reduce an effective delay of the multiplier.

24. A processor for a computer system, comprising:

a plurality of registers;

a plurality of logic units connected to said registers, including a floating-point execution unit allowing multiply-add operations; and

a table lookup for estimating a reciprocal square root of a normalized input value in one of said registers, said table lookup having a plurality of intervals and associated pairs of first and second constants used as inputs to said floating-point execution unit, said first and second constants being based on a linear approximation of the function 1/√

x using left and right edges of a given interval, offset to reduce a maximum error value for the given interval, such that the reciprocal square root is estimated by combining the product of the normalized input value and the first constant with the second constant.

25. The processor of claim 24 further comprising means for normalizing an input value within a range of said table lookup to produce the normalized input value.

26. The processor of claim 24 wherein the table lookup is a first table lookup, and further comprising a second table lookup having an interval which is different from that of said first table lookup.

27. The processor of claim 26 wherein:

said normalized input value lies within the range 0.5≦

x<

2;

the first and second constants have sufficient precision such that the estimated reciprocal square root has a relative error less than 1/4096;

the first table is used for the range 0.5≦

x<

2 and has an interval size of 1/32; and

the second table is used for the range 1≦

x<

2 and has an interval size of 1/16.

28. The processor of claim 24 wherein said table lookup provides said first and second constants having sufficient precision such that the estimated reciprocal square root has a relative error less than 1/4096.

29. The processor of claim 24 wherein the normalized input value has a mantissa portion, and said second constant is further based on the values of the left and right edges of a given interval such that the product of the normalized input value and the first constant is calculated using a lower order part of the mantissa to reduce the number of bits required in a multiply-add operation.

30. The processor of claim 24 further comprising means for calculating a square root of the normalized input value by multiplying the input value with the estimated reciprocal square root.

31. The processor of claim 30 further comprising means for improving the precision of the estimated square root by using the estimated reciprocal square root as a first approximation in a Newton-Raphson iteration.