Transcendental function approximation apparatus and method

• US 5,224,064 A
• Filed: 07/11/1991
• Issued: 06/29/1993
• Est. Priority Date: 07/11/1991
• Status: Expired due to Fees

• Current Assignee: Honeywell Incorporated (Honeywell International Inc.)
• Original Assignee: Honeywell Incorporated (Honeywell International Inc.)
• Inventors: Martin, Gregory M., Henry, Matthew R.
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US07/728,445
• Time in Patent Office: 719 Days
• Field of Search: 364/729, 364/721
• US Class Current: 708/440
• CPC Class Codes: G06F 1/0356 by using two or more smaller tables, e.g. addressed by parts of the argument

Abstract

Transcendental function approximation using a regional approximation look-up table, offset lookup table, scaling shifter and interpolation adder/subtractor. Rapid fixed-point arithmetic calculations can be accomplished which approximate values of transcendental functions to a predetermined accuracy. An N bit argument is used to produce an N bit result allowing the placement of the radix point in the two numbers to be different. Different parts of the input argument are fed in parallel to the regional approximation look-up table and the offset lookup table. A scaling shifter converts the output of the offset lookup table and regional lookup table to a result usable by the interpolation adder/subtractor processor. The regional approximation lookup table also provides information to the interpolation processor which provides the N bit approximation.

Claims

1. A function approximation method wherein the function is evaluated over a domain comprising a plurality of the domain wherein each element of the domain is addressable by a unique N bit function argument wherein the function approximation method comprises the steps of:

(a) dividing each N bit function into a L most significant bit argument and a P least significant bit offset argument for each element of the domain;

(b) storing an N bit regional approximation of the transcendental function, a Q bit profile index, and an R bit offset shift count, in a regional approximation lookup table for each L most significant bit argument wherein the regional approximation lookup table is addressed by the L most significant bit argument for each of the plurality of elements of the domain;

(c) concentrating the P least significant bit offset argument with the Q bit profile index to arrive at a P+Q bit address for each of the plurality of elements of the domain;

(d) storing a P bit offset value and a sign magnitude value in an offset lookup table for each P least significant bit offset argument wherein the offset lookup table is addressed by the P+Q bit address for each set of 2^P elements for each one of the plurality of elements of the domain; and

evaluating the value of the function at any one of the plurality of elements of the domain.

2. The function approximation method of claim 1 wherein the step of evaluating the value of the function at any one of the plurality of elements of the domain comprises the steps of:

(a) dividing the N bit function argument representing the one of the plurality of elements of the domain into a L most significant bit element argument and a P least significant bit element argument wherein the concatenation of the L most significant bit element argument and the P least significant bit element argument results in the N bit function argument representing the one of the plurality of elements of the domain;

(b) accessing the regional approximation lookup table with the L most significant bit element argument to generate an N bit element regional approximation of the transcendental function, a Q bit element profile index, and an R bit element offset shift count;

(c) concatenating the P bit element offset with the Q bit element profile index to arrive at a P +Q bit element offset lookup table address;

(d) accessing the offset lookup table with the P +Q bit element offset lookup table address to generate a P bit element offset value and an element sign magnitude value ;

(e) scaling the P bit element offset value by shifting the P bit element offset value right by the number of bits represented by the R bit element offset shift count to generate the P bit data value;

(f) forming a signed P bit data value from the element sign magnitude value and the P bit data value; and

(g) adding the N bit element regional approximation to the signed P bit data value to generate the N bit result.

3. The function approximation method of claim 2 wherein there is a target level of error for the function approximation method and the number of set elements are reduced by exhaustively checking each set element for each element of the domain by the steps comprised of:

(a) precisely determining a function value for each set element for each one of the plurality of elements of the domain and storing the precise function reduction value in a precise function reduction value memory;

(b) repeating the method of claim 1 steps (a) through (e) for each set element of each element of the domain and storing the N bit result for each set element of each element of the domain and in a reduction approximation memory;

(c) comparing the value of the precise function reduction value memory with the reduction approximation memory for each element of the domain and computing a level of error; and

(d) exhaustively searching all offsets for each set of elements for all elements of the domain and repeating steps (a) through (c) and eliminating any redundant offsets or shifts until the level of error is exceeds the target level of error.

4. The function approximation method of claim 1 wherein there is a target level of error for the function approximation method and wherein the number of bits designated for the L most -significant bit argument and the P most significant bit argument is determined by the steps comprised of:

(a) heuristically determining a P bit length and an L bit length;

(b) precisely determining a function value for each element of the domain and storing the precise function value in a precise function value memory;

(c) repeating the method of claim 1 steps (a) through (e) for each element of the domain and storing the N bit result in an approximation memory;

(d) comparing the value of the precise function value memory with the approximation memory for each element of the domain and computing a level of error; and

(e) changing the values of P and L and repeating steps (a) through (d) until the level of error is less than the target level of error.

5. The function approximation method of claim 1 wherein there is a target level of error for the function approximation method and wherein the number of bits designated for the Q bit element profile index and the R bit element offset shift count is determined by the steps comprised of:

(a) initializing the value of Q to L;

(b) initializing the value of R to zero so as to substantially provide a unique value from the offset lookup table for every element of the domain;

(c) precisely determining a function value for each element of the domain and storing the precise function value in a precise function value memory;

(d) repeating the method of claim 1 steps (a) through (e) for each element of the domain and storing the N bit result in an approximation memory;

(e) comparing the value of the precise function value memory with the approximation memory for each element of the domain and computing a level of error; and

(f) changing the values of Q and R and repeating steps (b) through (d) until the level of error is less than the target level of error.

6. The function approximation method of claim 1 wherein there is a target level of error for the function approximation method and wherein the values stored in the offset lookup table are determined by the steps comprised of:

(a) precisely determining a function value for each set of 2^P elements for each one of the plurality of elements of the domain and storing the precise function value in a precise function profile value memory;

(b) determining a middle value for each set;

(c) determining the precise difference values by calculating the difference between the middle value and each of the set elements and storing them in a precise difference memory;

(d) determining the element sign magnitude value to be positive if the precise difference is positive or determining the element sign magnitude value to be negative otherwise;

(e) determining the value of each set element that is to be stored in the profile lookup table to be the precise difference value rounded to the Pth bit.

7. The function approximation method of claim 1 wherein the function is a transcendental function.

8. The function approximation method of claim 1 wherein the size of the offset lookup table is 2^P+Q.

9. The function approximation method of claim 1 wherein the size of R is no greater than the log of P base 2.

10. The function approximation method of claim 1 wherein the data values are pipelined.

11. A function approximation apparatus wherein the function is evaluated over a domain comprising a plurality of elements of the domain wherein each element of the domain is addressable by a unique N bit function argument wherein the function approximation apparatus comprises:

(a) a means for dividing each N bit function argument into a L most significant bit argument and a P least significant bit offset argument for each element of the domain;

(b) a means for storing an N bit regional approximation of the transcendental function, a Q bit profile index, and an R bit offset shift count, in a regional approximation lookup table for each L most significant bit argument wherein the regional approximation lookup table is addressed by the L most significant bit argument for each of the plurality of elements of the domain;

(c) a means for concatenating the P least significant bit offset argument with the Q bit profile index to arrive at a P+Q bit address for each of the plurality of elements of the domain;

(d) a means for storing a P bit offset value and a sign magnitude value in an offset lookup table for each P least significant bit offset argument wherein the offset lookup table is addressed by the P+Q bit address for each set of 2^P elements for each one of the plurality of elements of the domain; and

(e) means for evaluating the value of the function at any one of the plurality of elements of the domain.

12. The function approximation apparatus of claim 11 wherein the function is a transcendental function.

13. The function approximation apparatus of claim 11 wherein the size of the offset lookup table is 2^P+Q.

14. The function approximation apparatus of claim 11 wherein the size of R is no greater than the log of P base 2.

15. The function approximation apparatus of claim 11 wherein the data values are pipelined.

16. The function approximation apparatus of claim 11 wherein the means for evaluating the value of the function at any one of the plurality of elements of the domain comprises:

(a) a means for dividing the N bit function argument representing the one of the plurality of elements of the domain into a L most significant bit element argument and a P least significant bit element argument wherein the concatenation of the L most significant bit element argument and the P least significant bit element argument results in the N bit function argument representing the one of the plurality of elements of the domain;

(b) means for accessing the regional approximation lookup table with the L most significant bit element argument to generate an N bit element regional approximation of the transcendental function, a Q bit element profile index, and an R bit element offset shift count;

(c) a means for concatenating the P bit element offset with the Q bit element profile index to arrive at a P+Q bit element offset lookup table address;

(d) a means for accessing the offset lookup table with the P+Q bit element offset lookup table address to generate a P bit element offset value and an element sign magnitude value;

(e) a means for scaling as P bit element offset value by shifting the P bit element offset value right by the number of P bits represented by the R bit element offset shift count to generate the P bit data value;

(f) a means for forming a signed P bit data value from the element sign magnitude value and the P bit data value; and

(g) a means for adding the N bit element regional approximation to the signed P bit data value to generate the N bit result.

17. The function approximation apparatus of claim 16 wherein there is a target level of error for the function approximation apparatus and the number of set elements are reduced by exhaustively checking each set element for each element of the domain by the apparatus comprised of:

(a) a means for precisely determining a function value for each set element for each one of the plurality of elements of the domain and storing the precise function reduction value in a precise function reduction value memory;

(b) a means for evaluating the value of the function for each element of each set of the domain and storing the N bit result for each set element of each element of the domain in a reduction approximation memory;

(c) a means for comparing the value of the precise function reduction value memory with the reduction approximation memory for each element of the domain and computing a level of error; and

(d) a means for exhaustively searching all offsets for each set of elements for all elements of the domain while eliminating any redundant offsets of shifts until the level of error exceeds the target level of error.

18. The function approximation apparatus of claim 11 wherein there is a target level of error for the function approximation apparatus and wherein the number of bits designated for the L most significant bit argument and the P most significant bit argument is determined by an apparatus comprising:

(a) a means for heuristically determining a P bit length and an L bit length;

(b) a means for precisely determining a function value for each element of the domain and storing the precise function value in a precise function value memory;

(c) a means for evaluating the value of the function for each element of the domain and storing the N bit result in an approximation memory;

(d) means for comparing the value of the precise function value memory with the approximation memory for each element of the domain and computing a level of error; and

(e) a means for changing the values of P and L until the level of error is less than the target level of error.

19. The function approximation apparatus of claim 11 wherein there is a target level of error for the function approximation apparatus and wherein the number of bits designated for the Q bit element profile index and the R bit element offset shift count is determined by the steps comprised of:

(a) a means for initializing the value of Q to L;

(b) a means for initializing the value of R to zero so as to substantially provide a unique value from the offset lookup table for every element of the domain;

(c) a means for precisely determining a function value for each element of the domain and storing the precise function value in a precise function value memory;

(d) a means for evaluating the value of the function for each element of the domain and storing the N bit result in an approximation memory;

(e) a means for comparing the value of the precise function value memory with the approximation memory for each element of the domain and computing a level of error; and

(f) means for changing the values of Q and R until the level of error is less than the target level of error.

20. The function approximation apparatus of claim 11 wherein there is a target level of error for the function approximation apparatus and wherein the values stored in the offset lookup table are determined by an apparatus comprised of:

(a) a means for precisely determining a function value for each set of 2^P elements for each one of the plurality of elements of the domain and storing the precise function value in a precise function profile value memory;

(b) a means for determining a middle value for each set;

(c) a means for determining the precise difference value by calculating the difference between the middle value and each of the set elements and storing them in a precise difference memory;

(d) a means for determining the element sign magnitude value to be positive if the precise difference is positive or determining the element sign magnitude value to be negative otherwise; and

(e) a means for determining the value of each set element that is to be stored in the profile lookup table to be the precise difference value rounded to the Pth bit.