Approximation of non-linear functions in fixed point using look-up tables
Computing a non-linear function ƒ(x) in hardware or embedded systems can be complex and resource intensive. In one or more aspects of the disclosure, a method, a computer-readable medium, and an apparatus are provided for computing a non-linear function ƒ(x) accurately and efficiently in hardware using look-up tables (LUTs) and interpolation or extrapolation. The apparatus may be a processor. The processor computes a non-linear function ƒ(x) for an input variable x, where ƒ(x)=g(y(x),z(x)). The processor determines an integer n by determining a position of a most significant bit (MSB) of an input variable x. In addition, the processor determines a value for y(x) based on a first look-up table and the determined integer n. Also, the processor determines a value for z(x) based on n and the input variable x, and based on a second look-up table. Further, the processor computes ƒ(x) based on the determined values for y(x) and z(x).
1. A method of computing, in a processor, a non-linear function ƒ(x) for an input variable x, where ƒ(x)=g(y(x),z(x)), the method comprising:
determining an integer n by determining a position of a most significant bit (MSB) of the input variable x;
determining a value for y(x) based on a first look-up table and the determined integer n;
determining a value for z(x) based on n and the input variable x, and based on a second look-up table; and
computing ƒ(x) based on the determined values for y(x) and z(x).
2. The method of claim 1 , wherein the position of the MSB of the input variable x is the position of the MSB of a binary representation of the input variable x.
3. The method of claim 2 , wherein the position of the MSB of the binary representation of the input variable x is a position of a leading 1 in the binary representation of the input variable x.
4. The method of claim 3 , wherein the determining the integer n comprises:
determining a position of a decimal point in the binary representation of the input variable x;
determining the position of the MSB of the binary representation of the input variable x; and
determining a number t as being a number of numeral digits between the position of the MSB and the position of the decimal point.
5. The method of claim 4 , wherein the determining the integer n further comprises determining n as
n
=
⌊
t
p
⌋
·
p
,
where p≥1 and is an integer, z(x) is a function of z, and z∈(1.0, 2.0 p ).
6. The method of claim 5 , wherein y(x)=2 nβ , where n=pm,
m
=
⌊
t
p
⌋
,
β is a constant, and β∈ , is a set of real numbers.
7. The method of claim 2 , wherein the determining the value for z(x) based on n comprises:
moving a decimal point in the binary representation of the input variable x by n positions to the left to determine z; and
looking up z(x) in the second look-up table based on the determined z.
8. The method of claim 1 , wherein the value for z(x) is determined based on a binary representation of the input variable x.
9. The method of claim 1 , further comprising receiving by the processor a value for the input variable x via an input device.
10. The method of claim 1 , wherein ƒ(x)=y(x)*z(x), the non-linear function ƒ(x) is equal to x β , where x>0, β is a constant and β∈ , is a set of real numbers.
11. The method of claim 10 , wherein y(x)=2 nβ .
12. The method of claim 11 , wherein the first look-up table provides a mapping between at least one of n or 2 n , and 2 nβ , and the determining the value for y(x) comprises determining the value for 2 nβ associated with the at least one of n or 2 n .
13. The method of claim 10 , wherein z(x)=z β , z∈(1.0, 2 p ), p is an integer.
14. The method of claim 13 , wherein the second look-up table provides a mapping between z and z β , and the determining the value for z(x) comprises determining the value for 2 β associated with z.
15. The method of claim 1 , wherein the input variable x is a positive real number.
16. The method of claim 1 , wherein ƒ(x)=y(x)+z(x), the non-linear function ƒ(x) is equal to log 2 x, where x>0.
17. An apparatus for computing a non-linear function ƒ(x) for an input variable x, where ƒ(x)=g(y(x),z(x), comprising:
a memory; and
at least one processor coupled to the memory and configured to:
determine an integer n by determining a position of a most significant bit (MSB) of the input variable x;
determine a value for y(x) based on a first look-up table and the determined integer n;
determine a value for z(x) based on n and the input variable x, and based on a second look-up table; and
compute ƒ(x) based on the determined values for y(x) and z(x).
18. The apparatus of claim 17 , wherein the position of the MSB of the input variable x is the position of the MSB of a binary representation of the input variable x.
19. The apparatus of claim 18 , wherein the position of the MSB of the binary representation of the input variable x is a position of a leading 1 in the binary representation of the input variable x.
20. The apparatus of claim 19 , wherein the at least one processor determines the integer n by:
determining a position of a decimal point in the binary representation of the input variable x;
determining the position of the MSB of the binary representation of the input variable x; and
determining a number t as being a number of numeral digits between the position of the MSB and the position of the decimal point.
21. The apparatus of claim 20 , wherein the at least one processor determines the integer n by further determining n as
n
=
⌊
t
p
⌋
·
p
,
where p≥1 and is an integer, z(x) is a function of z, and z∈(1.0, 2.0 p ).
22. The apparatus of claim 21 , wherein y(x)=2 nβ , where n=pm,
m
=
⌊
t
p
⌋
,
β is a constant, and β∈ , is a set of real numbers.
23. The apparatus of claim 18 , wherein the at least one processor determines the the value for z(x) based on n by:
moving a decimal point in the binary representation of the input variable x by n positions to the left to determine z; and
looking up z(x) in the second look-up table based on the determined z.
24. The apparatus of claim 17 , wherein the value for z(x) is determined based on a binary representation of the input variable x.
25. The apparatus of claim 17 , wherein the at least one processor is further configured to:
receive a value for the input variable x via an input device.
26. The apparatus of claim 17 , wherein ƒ(x)=y(x)*z(x), the non-linear function ƒ(x) is equal to x β , where x>0, β is a constant and β∈ , is a set of real numbers.
27. The apparatus of claim 26 , wherein y(x)=2 nβ .
28. The apparatus of claim 27 , wherein the first look-up table provides a mapping between at least one of n or 2 n , and 2 nβ , and the at least one processor determines the value for y(x) by determining the value for 2 nβ associated with the at least one of n or 2 n .
29. The apparatus of claim 26 , wherein z(x)=z β , z∈(1.0, 2.0 p ), p is an integer.
30. The apparatus of claim 29 , wherein the second look-up table provides a mapping between z and z β , and the at least one processor determines the value for z(x) by determining the value for z β associated with z.
31. The apparatus of claim 17 , wherein the input variable x is a positive real number.
32. The apparatus of claim 17 , wherein ƒ(x)=y(x)+z(x), the non-linear function ƒ(x) is equal to log 2 x, where x>0.
33. An apparatus for computing a non-linear function ƒ(x) for an input variable x, where ƒ(x)=g(y(x),z(x), comprising:
means for determining an integer n by determining a position of a most significant bit (MSB) of the input variable x;
means for determining a value for y(x) based on a first look-up table and the determined integer n;
means for determining a value for z(x) based on n and the input variable x, and based on a second look-up table; and
means for computing ƒ(x) based on the determined values for y(x) and z(x).
34. The apparatus of claim 33 , wherein the position of the MSB of the input variable x is the position of the MSB of a binary representation of the input variable x.
35. The apparatus of claim 34 , wherein the position of the MSB of the binary representation of the input variable x is a position of a leading 1 in the binary representation of the input variable x.
36. The apparatus of claim 35 , wherein the means for determining the integer n further configured to:
determine a position of a decimal point in the binary representation of the input variable x;
determine the position of the MSB of the binary representation of the input variable x; and
determine a number t as being a number of numeral digits between the position of the MSB and the position of the decimal point.
37. The apparatus of claim 36 , wherein the means for determining the integer n further configured to determine n as
n
=
⌊
t
p
⌋
·
p
,
where p≥1 and is an integer, z(x) is a function of z, and z∈(1.0, 2.0 p ).
38. The apparatus of claim 37 , wherein y(x)=2 nβ , where n=pm,
m
=
⌊
t
p
⌋
,
β is a constant, and ∈ , is a set of real numbers.
39. The apparatus of claim 34 , wherein the means for determining the value for z(x) based on n further configured to:
move a decimal point in the binary representation of the input variable x by n positions to the left to determine z; and
look up z(x) in the second look-up table based on the determined z.
40. The apparatus of claim 33 , wherein the value for z(x) is determined based on a binary representation of the input variable x.
41. The apparatus of claim 33 , further comprising means for receiving a value for the input variable x via an input device.
42. The apparatus of claim 33 , wherein ƒ(x)=y(x)*z(x), the non-linear function ƒ(x) is equal to x β , where x>0, β is a constant and β∈ , is a set of real numbers.
43. The apparatus of claim 42 , wherein y(x)=2 nβ .
44. The apparatus of claim 43 , wherein the first look-up table provides a mapping between at least one of n or 2 n , and 2 nβ , and the means for determining the value for y(x) further configured to determine the value for 2 nβ associated with the at least one of n or 2 n .
45. The apparatus of claim 42 , wherein z(x)=z β , z∈(1.0, 2.0 p ), p is an integer.
46. The apparatus of claim 45 , wherein the second look-up table provides a mapping between z and z β , and the means for determining the value for z(x) further configured to determine the value for z β associated with z.
47. The apparatus of claim 33 , wherein the input variable x is a positive real number.
48. The apparatus of claim 33 , wherein ƒ(x)=y(x)+z(x), the non-linear function ƒ(x) is equal to log 2 x, where x>0.
49. A computer-readable medium storing computer executable code for execution on at least one processor, comprising code to:
determine an integer n by determining a position of a most significant bit (MSB) of an input variable x;
determine a value for y(x) based on a first look-up table and the determined integer n;
determine a value for z(x) based on n and the input variable x, and based on a second look-up table; and
compute a non-linear function ƒ(x)=g(y(x),z(x)) based on the determined values for y(x) and z(x).