EDN Access -- 02.16.95 cubic interpolation hikes table's accurac
Design Ideas:February 16, 1995
Cubic interpolation hikes table's accuracy
Industrial Commercial Electronics, Buffalo, NY
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|
The theory of cubic interpolation begins with the cubic function
f(x)=w0+w1x x+w2x x2+w3x x3
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:
(5) f'(x)=w1+2w2 x x+3w3 x x2
(6) f"(x)=2w2+6w3 x x.
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
rate of change of curvature
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 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 x n/2cell_size
+w2 x n/2cell_size x n/2cell_size
+w3 x n/2cell_size x n/2cell_size x 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.f(x)=((W3 x x+W2) x x+W1) x x+W0.
You do not need a "powers" function if you evaluate the function as
Copyright c 1995 EDN Magazine. EDN is a registered trademark of Reed Properties Inc, used under license.