Home > database >  How can I properly build a sin lookup table with C?
How can I properly build a sin lookup table with C?

Time:02-22

To save performance on sin calls, and to handle integer angles, which are more portable manipulated and saved, instead of floating points as angles, I am building a sin lookup function, where 4096 units equals 2pi radians. To save memory, I only store the first 1024 sin values, which are equivalent to sin( [0, pi/2) ).

static const float SinTable[1024] = {0, 0.00153398, ..., 0.999995, 0.999999};

To handle angles in the 3rd and 4th quadrant, I simply conditionally negate:

return Angle&2048 ? -UnsignedSin : UnsignedSin;

Where UnsignedSin is the looked up sin value wrapped between [0, 2048). But how can I handle the second and 4th quadrants? How can I properly map the stored sin values of [0, 1) to [1, 0) conditionally by checking if the angle is in the 2nd or 4th quadrants such as with Angle&1024? I tried this but this is not quite right, because the result for 1024 angle is 0.999999 and not 1 which it should be.

const float UnsignedSin = SinTable[(Angle&1024 ? ~A : A)&1023];

The value of 1 is never stored in the sin table, so I assume a 1-SinTable[...] is required? But I cannot get it quite right.

CodePudding user response:

This'd be like:

float getSine(unsigned int angle) {
    angle &= 4095;        // Reduce angle to the range of 1 circle

    if( (angle & 2048) == 0) {
        if( (angle & 1024) == 0) {
            // Angle is from 0 to 1023
            return SinTable[angle];
        } else {
            // Angle is from 1024 to 2047
            return SinTable[2048-angle];
        }
    } else {
        if( (angle & 1024) == 0) {
            // Angle is from 2048 to 3071
            return -SinTable[angle-2048];
        } else {
            // Angle is from 3072 to 4095
            return -SinTable[4096-angle];
        }
    }

Note that for this code SinTable needs 1025 entries, so that SinTable[1024] is valid and contains the value 1.0. This only happens if the original angle was 1024 or 3072 (where SinTable[2048-1024]; or SinTable[4096-3072]; becomes SinTable[1024];). These angles could be handled as a special case instead (like if( (angle == 1024) || (angle == 3072) ) return 1.0;) but that's likely to be slower (due to branch mispredictions, etc).

Also note that it's possible to improve precision by using linear interpolation. E.g. you could say that angle is 20 bits and ranges from 0 to 1048575; then use bits 8 to 19 as the index into the table (like SinTable[angle >> 8]) to determine the lower value and the next value; then do int factions = angle & 0xFF; result = ( lower_value * (0x100 - factions) upper * fractions ) / 0x100; to create an estimate.

CodePudding user response:

I suggest you to avoid bit manipulation, since in the future you could change float to double. I propose a more portable version of Brendan answer

`define PI_ADDR 2048

float getSine(unsigned int angle) {
    angle = angle % (2*PI_ADDR);  // Reduce angle to the range of 1 circle
    if( angle < PI_ADDR/2) {
        return SinTable[angle];
    } else if( angle < PI_ADDR) {
        return SinTable[PI_ADDR - angle];
    } else if( angle < (PI_ADDR*3/2) ) {
        return -SinTable[angle-PI_ADDR];
    } else {
        return -SinTable[2*PI_ADDR -angle];
    }
}

About handling negative angles, be portable too:

return (Angle < 0) ? -UnsignedSin : UnsignedSin;
  • Related