You can obtain very accurate approximations of a function from only a few data points contained in a look-up table, trading storage space for calculation time. For example, you can derive log2(1...2) and sin(1...(pi)/2) functions to 16-bit accuracy from only 18 data points.
Cubic interpolation takes into account the curvature of a function by using the beginning and ending slopes of a curve segment to approximate the missing curve with a cubic polynomial. Taking four data points, P0, P1, P2, and P3, from a table, cubic interpolation approximates the curve connecting P1 and P2 and returns the value corresponding to any point along that curve between P1 and P2.
| Table 1—Sample cubic-interpolation calculations | |||||
|---|---|---|---|---|---|
| Curve | Data set f(x)= | w1 | w2 | w3 | f(0.5) |
| Sloping line | 6,7,8,9 | 1 | 0 | 0 | 7.5 |
| Parabola | 5,7,7,5 | 1 | -1 | 0 | 7.25 |
| Arbitrary curve | 1,2,3,1 | 1 | 1.5 | -1.5 | 2.6875 |
The theory of cubic interpolation begins with the cubic function
that defines a curve between points P1 and P2. To simplify the math, assume that variable x ranges from only 0 to 1.
You must set the coefficients, w0, w1, w2, and w3, so that the cubic polynomial satisfies these four initial conditions:
| value at P1 | |
| value at P2 | |
| slope at P1 | |
| slope at P2 |
Differentiating f(x) twice yields two more equations:
You can immediately derive w0 and w1 from initial conditions 1 and 3. Using initial conditions 2 and 4, you can solve Eqs 5 and 6 for w2 and w3.
The resulting coefficients are
| initial value | |
| initial slope | |
| initial curvature | |
| rate of change of curvature |
Table 1 contains example interpolations for a sloping line, a parabola, and an arbitrary curve.
To use cubic interpolation with fast-integer math on unsigned numbers, first scale the function by defining n=2cell_size × x. The cell_size depends on your processor and is usually 8, 16, or 32. Plugging in n, the scaled function becomes
- f(n)=w0+w1 × n/2cell_size
- +w2 × n/2cell_size × n/2cell_size
- +w3 × n/2cell_size × n/2cell_size × n/2cell_size
With the function properly scaled, you can drop the lower half of products after multiplying. Be sure to wait until you have completed a computation before throwing away the lower half of a double-precision integer calculation because the fractions could easily sum to more than 1 LSB.
You do not need a "powers" function if you evaluate the function as