EDN Access -- 02.16.95 cubic interpolation hikes table's accurac

-February 16, 1995

EDN logo
Design Ideas:February 16, 1995

Cubic interpolation hikes table's accuracy

Brad Eckert,
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
CurveData set
Sloping line6,7,8,91007.5
Arbitrary curve1,2,3,111.5-1.52.6875

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:

  • (1) f(0)=y1

value at P1
  • (2) f(1)=y2

value at P2
  • (3) f'(0)=(y2-y0)/2

slope at P1
  • (4) f'(1)=(y3-y1)/2

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

    • w0=y1

    initial value
    • w1=(y2-y0)/2

    initial slope
    • w2=(-y3+4y2-5y1+2y0)/2

    initial curvature
    • w3=(y3-3y2+3y1-y0)/2

    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 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.
    You do not need a "powers" function if you evaluate the function as

    f(x)=((W3 x x+W2) x x+W1) x x+W0.

    | EDN Access | feedback | subscribe to EDN! |
    | design features | design ideas | columnist |

    Copyright c 1995 EDN Magazine. EDN is a registered trademark of Reed Properties Inc, used under license.

Loading comments...

Write a Comment

To comment please Log In