Create sine lookup table in C++

Question

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

real array sine_table[-1000..1000]
    for x from -1000 to 1000
        sine_table[x] := sine(pi * x / 1000)

I need to create a sine_table lookup table.

Solution 1

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.

Solution 2

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

Solution 3

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.

Solution 4

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

Solution 5

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.

View more solutions

Comments

[Mike DeSimone]

1) Don't forget #include <cmath> 2) This actually creates one less item; it's equivalent to sine_table[-1000..999] in the pseudocode.

[Mike DeSimone]

Also, the quarter-sine table can be used to find cosines through a similar quadrant-remapping method.

[Alex Blakemore]

One caution. The argument name for getSineValue() could be misleading. It really represents a multiple of Pi/1000, so could be called thousandthsOfPi. Not trying to be pedantic, but it could easily confuse someone that getSineValue(500) means sin(pi/2)

[Jeremy Friesner]

I'm amused by the optimization of starting the for loop at one instead of zero. :) Note that the loop has a bug though, it writes to table[1000] which is not a valid index in the array (it's one past the end)

[Master Yoda]

I am sorry for the loop error. Actually what I meant was store for 1 to 1000 as 0 is n obvious case. I have edited the code to correct this.

[Jeremy Friesner]

I think it's still not quite right.... for example, now sine_table[0] will have the value of sin(PI*1/1000.0), when the correct value of sin(0) should be zero.

[Master Yoda]

that's why this is there: return signsine_table[signmultipleOfPi - 1];

[Ben Voigt]

The first identity has a typo, should be sin (-x) = -sin(x)

[Alex Blakemore]

Thanks for catching that Ben, I corrected my answer accordingly

[mins]

"You can reduce the size of your table to 25% of the original by only storing values for the first quadrant". And anyway to get actual values for [-pi, +pi] the series order must be at least 10, order 6 provides good approximation for [-pi/2, +pi/2] (plots)