How to build a lookup table in C (SDCC compiler) with linear interpolation

Question

For a LPC922 microcontroller (with SDCC) I want to create a lookup table with linear interpolation. Lets assume I got x and y values like

x=300 y=10,0201 
x=700 y=89,542 
x=800 y=126,452 
x=900 y=171,453 
x=1500 y=225,123

How can the code for a lookup table with linear interpolation look like, so I get for example for x=850 the right value for y ((171,453+126,452)/2)?

Answer 1

typedef struct { double x; double y; } coord_t;

coord_t c[5] = 
{
    {300, 10.02},
    {700, 89.542},
    {800, 126.452}, 
    {900, 171.453}, 
    {1500,225.123}
};    

double interp( coord_t* c, double x, int n )
{
    int i;

    for( i = 0; i < n-1; i++ )
    {
        if ( c[i].x <= x && c[i+1].x >= x )
        {
            double diffx = x - c[i].x;
            double diffn = c[i+1].x - c[i].x;

            return c[i].y + ( c[i+1].y - c[i].y ) * diffx / diffn; 
        }
    }

    return 0; // Not in Range
}

int main(int argc, char** argv) 
{
    double y = interp( c, 850, 5 );
}

Answer 2

double get_value(double x)
{
    /* NOTE: xs MUST be sorted */
    static const double xs[] = { 300, 700, 800, 900, 1500 };
    static const double ys[] = { 10.0201, 89.542, 126.452, 171.453, 225.123 };

    /* number of elements in the array */
    static const int count = sizeof(xs)/sizeof(xs[0]);

    int i;
    double dx, dy;

    if (x < xs[0]) {
        /* x is less than the minimum element
         * handle error here if you want */
        return ys[0]; /* return minimum element */
    }

    if (x > xs[count-1]) {
        return ys[count-1]; /* return maximum */
    }

    /* find i, such that xs[i] <= x < xs[i+1] */
    for (i = 0; i < count-1; i++) {
        if (xs[i+1] > x) {
            break;
        }
    }

    /* interpolate */
    dx = xs[i+1] - xs[i];
    dy = ys[i+1] - ys[i];
    return ys[i] + (x - xs[i]) * dy / dx;
}

This can fairly easily be extended to other interpolation methods if you wish. Note that you will then probably have to extend the special cases for the border regions however you wish to handle that. A common method is to do linear interpolation when not enough neighboring values are available for the preferred method.

Also when the number of values starts to grow i would recommend using a binary search method to compute the starting point. This shouldn't be a problem with this few values though.

Update: Since OP is working on a limited platform, here's a version of the above using libfixmath:

/* NOTE: xs MUST be sorted */
static const fix16_t xs[] = { 300<<16, 700<<16, 800<<16, 900<<16, 1500<<16 };
static const fix16_t ys[] = { (fix16_t)(65536.0*10.0201+0.5), (fix16_t)(65536.0*89.542+0.5), (fix16_t)(65536.0*126.452+0.5), (fix16_t)(65536.0*171.453+0.5), (fix16_t)(65536.0*225.123+0.5) };

fix16_t get_value_fix(fix16_t x)
{    
    /* number of elements in the array */
    static const int count = sizeof(xs)/sizeof(xs[0]);
    int i;
    fix16_t dx, dy;

    if (x < xs[0]) {
        /* x is less than the minimum element
         * handle error here if you want */
        return ys[0]; /* return minimum element */
    }

    if (x > xs[count-1]) {
        return ys[count-1]; /* return maximum */
    }

    /* find i, such that xs[i] <= x < xs[i+1] */
    for (i = 0; i < count-1; i++) {
        if (xs[i+1] > x) {
            break;
        }
    }

    /* interpolate */
    dx = fix16_sub(xs[i+1], xs[i]);
    dy = fix16_sub(ys[i+1], ys[i]);
    return fix16_add(ys[i],  fix16_div(fix16_mul(fix16_sub(x, xs[i]), dy), dx));
}

Answer 3

Put all the values in an array. Then search for x.. if you didn't find the correct value you have an index and a neighbour index, then calculate the value using your formula..