Create sine lookup table in C++

How can I rewrite the following pseudocode in C++?

real array sine_t开发者_如何转开发able[-1000..1000]
    for x from -1000 to 1000
        sine_table[x] := sine(pi * x / 1000)

I need to create a sine_table lookup table.

You can reduce the size of your table to 25% of the original by only storing values for the first quadrant, i.e. for x in [0,pi/2].

To do that your lookup routine just needs to map all values of x to the first quadrant using simple trig identities:

• sin(x) = - sin(-x), to map from quadrant IV to I
• sin(x) = sin(pi - x), to map from quadrant II to I

To map from quadrant III to I, apply both identities, i.e. sin(x) = - sin (pi + x)

Whether this strategy helps depends on how much memory usage matters in your case. But it seems wasteful to store four times as many values as you need just to avoid a comparison and subtraction or two during lookup.

I second Jeremy's recommendation to measure whether building a table is better than just using std::sin(). Even with the original large table, you'll have to spend cycles during each table lookup to convert the argument to the closest increment of pi/1000, and you'll lose some accuracy in the process.

If you're really trying to trade accuracy for speed, you might try approximating the sin() function using just the first few terms of the Taylor series expansion.

• sin(x) = x - x^3/3! + x^5/5! ..., where ^ represents raising to a power and ! represents the factorial.

Of course, for efficiency, you should precompute the factorials and make use of the lower powers of x to compute higher ones, e.g. use x^3 when computing x^5.

One final point, the truncated Taylor series above is more accurate for values closer to zero, so its still worthwhile to map to the first or fourth quadrant before computing the approximate sine.

Addendum: Yet one more potential improvement based on two observations:
1. You can compute any trig function if you can compute both the sine and cosine in the first octant [0,pi/4]
2. The Taylor series expansion centered at zero is more accurate near zero

So if you decide to use a truncated Taylor series, then you can improve accuracy (or use fewer terms for similar accuracy) by mapping to either the sine or cosine to get the angle in the range [0,pi/4] using identities like sin(x) = cos(pi/2-x) and cos(x) = sin(pi/2-x) in addition to the ones above (for example, if x > pi/4 once you've mapped to the first quadrant.)

Or if you decide to use a table lookup for both the sine and cosine, you could get by with two smaller tables that only covered the range [0,pi/4] at the expense of another possible comparison and subtraction on lookup to map to the smaller range. Then you could either use less memory for the tables, or use the same memory but provide finer granularity and accuracy.

long double sine_table[2001];
for (int index = 0; index < 2001; index++)
{
    sine_table[index] = std::sin(PI * (index - 1000) / 1000.0);
}

One more point: calling trigonometric functions is pricey. if you want to prepare the lookup table for sine with constant step - you may save the calculation time, in expense of some potential precision loss.

Consider your minimal step is "a". That is, you need sin(a), sin(2a), sin(3a), ...

Then you may do the following trick: First calculate sin(a) and cos(a). Then for every consecutive step use the following trigonometric equalities:

• sin([n+1] * a) = sin(n*a) * cos(a) + cos(n*a) * sin(a)
• cos([n+1] * a) = cos(n*a) * cos(a) - sin(n*a) * sin(a)

The drawback of this method is that during this procedure the round-off error is accumulated.

double table[1000] = {0};
for (int i = 1; i <= 1000; i++)
{
    sine_table[i-1] = std::sin(PI * i/ 1000.0);
}


double getSineValue(int multipleOfPi){
     if(multipleOfPi == 0) return 0.0;
     int sign = 1;
     if(multipleOfPi < 0){
         sign = -1;

     }
     return signsine_table[signmultipleOfPi - 1];
}

You can reduce the array length to 500, by a trick sin(pi/2 +/- angle) = +/- cos(angle). So store sin and cos from 0 to pi/4. I don't remember from top of my head but it increased the speed of my program.

You'll want the std::sin() function from <cmath>.

another approximation from a book or something

streamin ramp;
streamout sine;

float x,rect,k,i,j;

x = ramp -0.5;

rect = x * (1 - x < 0 & 2);
k = (rect + 0.42493299) *(rect -0.5) * (rect - 0.92493302) ;
i = 0.436501 + (rect * (rect + 1.05802));
j = 1.21551 + (rect * (rect - 2.0580201));
sine = i*j*k*60.252201*x;

full discussion here: http://synthmaker.co.uk/forum/viewtopic.php?f=4&t=6457&st=0&sk=t&sd=a

I presume that you know, that using a division is a lot slower than multiplying by decimal number, /5 is always slower than *0.2

it's just an approximation.

also:

streamin ramp;
streamin x;  // 1.5 = Saw   3.142 = Sin   4.5 = SawSin
streamout sine;
float saw,saw2;
saw = (ramp * 2 - 1) * x;
saw2 = saw * saw;

sine = -0.166667 + saw2 * (0.00833333 + saw2 * (-0.000198409 + saw2 * (2.7526e-006+saw2 * -2.39e-008)));
sine = saw * (1+ saw2 * sine);