Bipartite look-up table with output values having minimized absolute error
First Claim
1. A computer-readable medium encoded with a data structure, wherein the data structure comprises a bipartite look-up table usable for determining an initial estimated value for a function within a predefined input range, wherein the predefined input range is partitioned into a first number of intervals, wherein each interval is partitioned into a second number of equal subintervals, wherein each subinterval is partitioned into a third number of equal sub-subintervals, wherein said bipartite look-up table is formed by:
- generating a base table entry for each subinterval of each interval;
computing one or more difference table entries for each interval, wherein computing an Ith difference table entry for a first interval comprises;
(a) computing a first midpoint in an Ith sub-subinterval of each subinterval of the first interval, and evaluating the function at the first midpoint to determine a first function value;
(b) computing a reference midpoint in a reference sub-subinterval of each subinterval of the first interval;
(c) evaluating the function at the reference midpoint to determine a reference function value;
(d) subtracting the first function value and the reference function value to determine a difference value for each subinterval of the first interval; and
(e) averaging three or more of the difference values corresponding to three or more of the subintervals of the first interval to determine an Ith average value, wherein said Ith difference table entry is substantially equal to said Ith averaged value.
2 Assignments
0 Petitions
Accused Products
Abstract
A method for generating entries for a bipartite look-up table having base and difference table portions. In one embodiment, these entries are usable to form output values for a mathematical function, f(x), in response to receiving corresponding input values within a predetermined input range. The method first comprises partitioning the input range into I intervals, J subintervals/interval, and K sub-subintervals/subinterval. For a given interval M, the method includes generating K difference table entries and J base table entries. Each of the K difference table entries corresponds to a particular group of sub-subintervals within interval M, each of which has the same relative position within their respective subintervals. Each difference table entry is computed by averaging difference values for the sub-subintervals included in a corresponding group N. Each difference value which makes up this average is equal to f(X1)−f(X2), where X1 is the midpoint of the sub-subinterval within group N, and X2 is the midpoint of a predetermined reference sub-subinterval within the same subinterval as X1. Each of these midpoints is calculated such that maximum absolute error is minimized for all possible input values in the sub-subinterval. Each of the J base table entries, on the other hand, corresponds to a subinterval within interval M. Each entry is equal to f(X2)+adjust, where X2 is the midpoint of the reference sub-subinterval of the subinterval corresponding to the base table entry. The adjust value is calculated so that error introduced by the averaging of the difference table entries is evenly distributed over the entire subinterval.
-
Citations
32 Claims
-
1. A computer-readable medium encoded with a data structure, wherein the data structure comprises a bipartite look-up table usable for determining an initial estimated value for a function within a predefined input range, wherein the predefined input range is partitioned into a first number of intervals, wherein each interval is partitioned into a second number of equal subintervals, wherein each subinterval is partitioned into a third number of equal sub-subintervals, wherein said bipartite look-up table is formed by:
-
generating a base table entry for each subinterval of each interval;
computing one or more difference table entries for each interval, wherein computing an Ith difference table entry for a first interval comprises;
(a) computing a first midpoint in an Ith sub-subinterval of each subinterval of the first interval, and evaluating the function at the first midpoint to determine a first function value;
(b) computing a reference midpoint in a reference sub-subinterval of each subinterval of the first interval;
(c) evaluating the function at the reference midpoint to determine a reference function value;
(d) subtracting the first function value and the reference function value to determine a difference value for each subinterval of the first interval; and
(e) averaging three or more of the difference values corresponding to three or more of the subintervals of the first interval to determine an Ith average value, wherein said Ith difference table entry is substantially equal to said Ith averaged value. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
(e) subtracting the reference function value of the reference sub-subinterval of the subinterval from the first function value of an initial sub-subinterval of the subinterval to determine an actual difference;
(f) subtracting the Ith average value corresponding to an initial difference table entry for the first interval from the actual difference to determine a maximum error;
(g) dividing the maximum error by two to determine an adjustment value;
(h) adding the adjustment value to the reference function value of the reference sub-subinterval of the subinterval to generate a sum value Q.
-
-
12. The data structure of claim 11, wherein said generating a base table entry for each subinterval of the first interval further comprises:
-
computing a first intermediate value according to (2{circumflex over ( )}(PR+1)*Q+0.5, wherein PR is a positive integer, wherein Q is the sum value, wherein A denotes exponentiation;
truncating the first intermediate value to determine a first integer value;
subtracting 2{circumflex over ( )}PR from the first integer value to determine the base table entry.
-
-
13. The data structure of claim 1, wherein the computer-readable medium is a read-only memory.
-
14. The data structure of claim 1, wherein (d) comprises summing the difference value corresponding to all of the subintervals of the first interval resulting in a final sum, and dividing the final sum by the second number.
-
15. The data structure of claim 1, wherein said first midpoint in the Ith sub-subinterval of each subinterval of the first interval is chosen so that the corresponding first function value minimizes absolute error with respect to the function for input values within the Ith sub-subinterval.
-
16. A processor having a memory which contains the data structure of claim 1.
-
17. A method for making a microprocessor, the method comprising:
- forming a memory which contains the data structure of claim 1.
-
18. A bipartite lookup table for generating approximations to a function for input values in a predefined input range, wherein the predefined input range is partitioned into a first number of intervals, wherein each interval is partitioned into a second number of equal subintervals, wherein each subinterval is partitioned into a third number of equal sub-subintervals, the bipartite look-up table comprising:
-
a difference table configured to store the third number of difference table entries for each interval, wherein an Ith difference table entry for a first interval is determined by;
(a) computing a first midpoint in an Ith sub-subinterval of each subinterval of the first interval, and evaluating the function at the first midpoint to determine a first function value;
(b) computing a reference midpoint in a reference sub-subinterval of each subinterval of the first interval, and evaluating the function at the reference midpoint to determine a reference function value;
(c) subtracting the first function value and the reference function value to determine a difference value for each subinterval of the first interval;
(d) averaging three or more of the difference values corresponding to three or more of the subintervals of the first interval to determine an Ith average value;
a base table configured to store a base table entry for each subinterval of each interval;
an address control unit configured to receive an input value, and to extract high, middle and low order bit segments from the input value, to generate a base table index by concatenating the high and middle order bit segments, to generate a difference table index by concatenating the high and low order bit segments;
wherein the base table is further configured to receive the base table index and to provide a first base table entry in response to the base table index, wherein the difference table is further configured to receive the difference table index and to provide a first difference table entry in response to the difference table index. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32)
(e) subtracting the reference function value of the reference sub-subinterval of the subinterval from the first function value of an initial sub-subinterval of the subinterval to determine an actual difference;
(f) subtracting the Ith average value corresponding to an initial difference table entry for the first interval from the actual difference to determine a maximum error;
(g) dividing the maximum error by two to determine an adjustment value;
(h) adding the adjustment value to the reference function value of the reference sub-subinterval of the subinterval to generate a sum value Q.
-
-
31. The bipartite lookup table of claim 30, wherein the base table entry for each subinterval of each interval is determined offline by a computer executing (e), (f), (g) and (h).
-
32. The bipartite lookup table of claim 18, wherein said first midpoint in the Ith sub-subinterval of each subinterval of the first interval is chosen so that the corresponding first function value minimizes absolute error with respect to the function for input values within the Ith sub-subinterval.
Specification