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.

Other References

• Oberman, et al, "Design Issues in Division and Other Floating-Point Operations," IEEE Transactions on Computers, vol. 46, Feb. 1997, pp. 154-161
• Ito, et al, "Efficient Initial Approximation for Multiplicative Division and Square Root by a Multiplication with Operand Modification," IEEE Transactions on Computers, vol. 46, No. 4, Apr. 1997
• Foley, "Computer Graphics: Principles and Practice," published by Addison-Wesley Pub Co., 1995, pp. 866-876
• Turkowski, "Computing the Inverse Square Root," published by Academic Press, Inc., 1995, pp. 16-21
• Takagi, "Generating a Power of an Operand by a Table Look-up and a Multiplication," IEEE publication, published 1997, pp. 126-131
• Das Sarma, et al, "Faithful Interpolation in Reciprocal Tables," IEEE publication, published 1997, pp. 82-91
• Das Sarma, et al, "Faithful Bipartite ROM reciprocal Tables," IEEE publication, published 1995, pp. 17-28
• Das Sarma, "Measuring the Accuracy of ROM Reciprocal Tables," IEEE publication, published 1993, pp. 95-102
• Schulte et al., "Symmetric Bipartite Tables for Accurate Function Approximation," Department of Electrical Engineering and Computer Science Lehigh University, 1997, pp. 175-183
• Hassler et al., "Function Evaluation by Table Look-up and Addition," Department of Information Engineering Nagoya University, 1995, pp. 10-1