To compute the output of the function given an input, the computer will usually have to perform all the mathematical or logical operations in the function. Depending on the complexity of the function, it can be very slow. However, if the number of different inputs for the function is small, we could actually pre-compute the output for each input and save it as a lookup table on the memory. During the runtime, when the function is given an input, instead of computing the result, we could just look up the output in the lookup table. In some scenarios, even if the number of different inputs is huge, we can still use lookup table and do interpolation to approximate the function output for acceleration.
In this blog post, I would like to quickly discuss the function approximation using lookup table and interpolation.
Square Root Approximation Using Lookup Tables and Interpolation
This is a C++ implementation for the example of computing the UINT16 value square root using one or two lookup tables presented in the “Motorola CPU32 Bulletin”.
We could see that computing the square root of UINT16 values in the range of [0, 256) using two lookup tables is more accurate than just using one lookup table.
1 2 3 4 5 6 7 8 9 10 11
$ g++ sqrt_lut.cpp -o sqrt_lut -std=c++14 $ ./sqrt_lut Enter a UINT16 number [0, 65536) to calculate its square root: 361 Square root using one lookup table: 19 Square root using two lookup tables: 19 Actual square root: 19 $ ./sqrt_lut Enter a UINT16 number [0, 65536) to calculate its square root: 64 Square root using one lookup table: 4 Square root using two lookup tables: 8 Actual square root: 8
Note that the actual implementation presented in the bulletin uses Motorola CPU32 assembly instructions and is much more efficient than the C++ implementation. For example, the table bin index and the interpolation fraction does not have to be computed in practice. They just constitute the hexadecimal value of the input value. For instance, the input value 361 decimal is 0169 hexadecimal. 01 is the table bin index hexadecimal (1 decimal), and 69 is the interpolation fraction hexadecimal (361 - 256 = 105 decimal).
For simple functions that can be computed very fast, using lookup table and specialized hardware might not be beneficial. However, if the function is computational heavy, lookup table and specialized hardware for approximation can be employed for acceleration.