Branch-free software methodology for transcendental functions

• US 20040015882A1
• Filed: 06/05/2001
• Published: 01/22/2004
• Est. Priority Date: 06/05/2001
• Status: Abandoned Application

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Peter Tang, Ping Tak
• Application Number:
  US09/875,464
• Publication Number:
  US 20040015882A1
• Time in Patent Office: Days
• US Class Current: 717/129
• CPC Class Codes: G06F 7/544 for evaluating functions by calculation G06F7/4824 takes precedence

Abstract

Various embodiments of a computer-implemented branch-free methodology for approximating a function of an input argument are disclosed. The methodology includes selecting one of a number of breakpoints, such that a reduced argument for the function is less than a predetermined value. An approximate function of the reduced argument is evaluated, including accessing a look-up table based on the selected breakpoint to obtain value of a term in the approximate function. The look-up table has at least one breakpoint for which the reduced argument can be computed without roundoff error when the input argument is close to a root of the function. The branch-free methodology may be applied to compute transcendental functions such as the exponential, logarithm, and trigonometric functions.

Claims

1. A computer-implemented method for approximating a function of an input argument, comprising:

selecting one of a plurality of breakpoints, such that a reduced argument for the function is less than a predetermined value; and

evaluating an approximate function of the reduced argument, including accessing a look-up table based on the selected breakpoint to obtain a value of a term in the approximate function,

wherein the look-up table has at least one breakpoint for which the reduced argument can be computed without roundoff error when the input argument is close to a root of the function.

2. The method of claim 1 wherein the function is log_b(X).

3. The method of claim 2 further comprising:

representing X in the floating point form Y*G^k where Y is greater than or equal to 1, and wherein the reduced argument is Z=C*(Y*B_j−

1) where C is a function of log_b(e), and evaluating the approximate function includes determining log_b(1/B,) using the look-up table and determining log_b(X) as an arithmetic combination of at least k*log_b(2), log_b(1/B_j), and log_b(1+Z/C).

4. The method of claim 3 wherein Y<

=2 and the look-up table is modified such that B₀=1 and B_N=1/2.

5. The method of claim 3 wherein log_b(1/B_j) is given by the look-up table as at least two lower precision values T_j,hi and T_j,lo whose sum equals log_b(1/B_j), log_b(2) is given by at least two lower precision values L_hi. and L_lo whose sum equals log_b(2), and Z is given by at least two lower precision values Z_hi and Z_lo whose sum equals Z.

6. The method of claim 5 wherein log_b(X) is approximated by A₁+A₂+Z_lo, where A₁ is k*L_hi+T_j,hi+Z_hi, A₂ is k*L_lo+T_j,lo+P and P is log_b(1+Z/C)−

Z.

7. The method of claim 6 wherein if k*N+j=0 for the breakpoint, then log_b(X) is approximated by (A₁+Z_lo)+A₂.

8. The method of claim 7 wherein log_b(X) is otherwise given by A₁+(A₂+Z_lo).

9. The method of claim 3 wherein the predetermined value is proportional to 1/(2*N).

10. The method of claim 9 wherein k*L_hi+T_j,hi can be represented without roundoff error for all valid values of k,j.

11. The method of claim 10 wherein T_0,hi=T_0,lo,=0 and T_N,hi=L_hi, T_N,lo=L_lo.

12. An article of manufacture, comprising:

a machine readable medium having instructions stored therein that can be executed by a processor to approximate a function of an input argument by selecting one of a plurality of breakpoints, such that a reduced argument for the function is less than a predetermined value, and evaluating an approximate function of the reduced argument including accessing a look-up table based on the selected breakpoint to obtain a value of a term in the approximate function, wherein the look-up table has at least one breakpoint for which the reduced argument can be computed without roundoff error when the input argument is close to a root of the function.

13. The article of manufacture of claim 12 wherein the function is log_b(X).

14. The article of manufacture of claim 13 wherein the medium has further instructions for representing X in the floating point form Y*G^k where Y is greater than or equal to 1, and wherein the reduced argument is Z=C*(Y*B_j−

1) where C is a function of log_b(e), and evaluating the approximate function includes determining log_b(1/B_j) using the look-up table and determining log_b(X) as an arithmetic combination of at least k*log_b(2), log_b(1/B_j), and log_b(1+Z/C).

15. The article of manufacture of claim 14 wherein Y<

=2 and the look-up table is modified such that B₀=1 and B_N=1/2.

16. The article of manufacture of claim 13 wherein log_b(1/B_j) is given by the look-up table as at least two lower precision values T_j,hi and T_j,lo whose sum equals log_b(1/B_j), log_b(2) is given by at least two lower precision values L_hi and L_lo whose sum equals log_b(2), and Z is given by at least two lower precision values Z_hi and Z_lo whose sum equals Z.

17. The article of manufacture of claim 16 wherein log_b(X) is approximated by A₁+A₂+Z_lo, where A₁ is k*L_hi+T_j,hi+Z_hi, A₂ is k*L_lo+T_j,lo+P and P is log_b(1+Z/C)−

Z.

18. The article of manufacture of claim 17 wherein if k*N+j=0 for the breakpoint, then log_b(X) is approximated by (A₁+Z_lo)+A₂.

19. The article of manufacture of claim 18 wherein log_b(X) is otherwise given by A₁+(A₂+Z_lo).

20. The article of manufacture of claim 14 wherein the predetermined value is proportional to 1/(2*N).

21. The article of manufacture of claim 20 wherein k*L_hi+T_j,hi can be represented without roundoff error for all valid values of k,j.

22. The article of manufacture of claim 21 wherein T_0,hi=T_0,lo=0 and T_N,hi=L_hi, T_N,lo=L_lo.

23. A computer system comprising:

a processor coupled to a non-volatile storage device, the storage device contains instructions that when executed by the processor approximate a function of a number, by selecting one of a plurality of breakpoints, such that a reduced argument for the function is less than a predetermined value, and evaluating an approximate function of the reduced argument including accessing a look-up table based on the selected breakpoint to obtain a value of a term in the approximate function, wherein the look-up table has at least one breakpoint for which the reduced argument can be computed without roundoff error when the input argument is close to a root of the function.

24. The computer system of claim 23 wherein the function is log_b(X).

25. The computer system of claim 24 wherein the storage device has further instructions that when executed by the processor represent X in the floating point form Y*G^k where Y is greater than or equal to 1, and wherein the reduced argument is Z=C*(Y*B_j−

1) where C is a function of log_b(e), and evaluating the approximate function includes determining log_b(1/B_j) using the look-up table and determining log_b(X) as an arithmetic combination of at least k*log_b(2), log_b(1/B_j), and log_b(1+Z/C).

26. The computer system of claim 25 wherein log_b(1/B_j) is given by the look-up table as at least two lower precision values T_j,hi and T_j,lo whose sum equals log_b(1/B_j), log_b(2) is given by at least two lower precision values L_hi and L_lo whose sum equals log_b(2), and Z is given by at least two lower precision values Z_hi and Z_lo whose sum equals Z.

27. The computer system of claim 26 wherein log_b(X) is approximated by A₁+A₂+Z_lo, where A₁ is k*L_hi+T_j,hi+Z_hi, A₂ is k*L_lo+T_j,lo+P and P is log_b(1+Z/C)−

Z.

28. The computer system of claim 23 wherein the processor has a hardware architecture that is deeply pipelined and in which branch mispredictions cause a significant performance penalty.

29. The computer system of claim 28 wherein the processor is one of a plurality of IA-32 series of processors by Intel Corp.