3

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.

user16217248
  • 3,119
  • 19
  • 19
  • 37
  • Relevant: https://stackoverflow.com/questions/2284860/how-does-c-compute-sin-and-other-math-functions – Passerby Feb 22 '22 at 04:27
  • 0.999999 could be good enough. Consider that floating-point numbers equality check can only be obtained within some precision: https://stackoverflow.com/questions/17333/what-is-the-most-effective-way-for-float-and-double-comparison – G. C. Feb 22 '22 at 11:27
  • @G.C. Even if it is close enough that it does not matter, it still means the implementation is conceptually incorrect. – user16217248 Apr 11 '23 at 21:29

3 Answers3

5

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.

Brendan
  • 35,656
  • 2
  • 39
  • 66
1

You should check about CORDIC algorithm that allows you to get sine and cosine functions with full precision with full savings in space for tables (those are employed in trigonometric functions for embedded architectures since long long time). And use fixed point, instead of floating point or just plain integer values (which gives no sub degree precision at all) Let's say you use a 1/64 of degree (or better 1/2^32 of a full 2*PI rotation or one quadrant, would require around two 32 entries tables) fixed point to achieve enough precision. The CORDIC algorithm will permit you to use two simple tables with one entry per bit of precision you are interested in, and easy and quick calculations (only sums and multiplications are done), and will give you full precision in calculations.

Luis Colorado
  • 10,974
  • 1
  • 16
  • 31
  • How can I used fixed point in C? – user16217248 Feb 25 '22 at 00:52
  • you can by using an integer and considering that part of the bits are the decimal part. If you try arithmetic, you'll need to do some adjustments on multiplication and division, but it is possible. There are no fiixed point types in C, so you need to improvise. – Luis Colorado Feb 28 '22 at 06:50
-1

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;
G. C.
  • 387
  • 2
  • 6
  • Not sure why bit manipulation would interfere with changing float to double – user16217248 Feb 22 '22 at 15:32
  • In the code I can see (Angle&2048) and (Angle&1024) that are not much portable. Using a single define can save you a lot of work in the future. You are right, I mean lookup table address manipulation, not float/double – G. C. Feb 22 '22 at 16:18
  • To increase precision I could change the constants relatively easily, for example if I want 16 bit precision instead of 12 bit, I would use (Angle&32768) and (Angle&16384) respectively. Besides I could still use (1< – user16217248 Feb 22 '22 at 17:00