Fast approximations of the sine and cosine functions

I made up the web-page http://bookofgames.ch/fastSin.html to check out the different approximations for sine and cosine functions. Load it and make your own tests. You can use the “save”-function of your browser to download the code, change and use it for your own projects.

Because cos(x)=sin(x+π/2) we need only a table for the sine function. It is periodic over 2*π and we use a table for this range. We could save memory with the symmetries sin(x+π/2)=-sin(x) and sin(π/4-x)=sin(π/4+x), but this considerably slows done the computation. The length of the table should be a power of 2 plus one for linear approximation. Then we can use bitwise-and (&) to impose periodicity instead of the much slower modulus (%) operation.

For checking the accuracy we note that the for all derivatives of the sine function the largest value is equal to 1. Using a table of 4097 elements we get an error of the nearest value approximation of 0.0007. This agrees with the results of the last post. This error might be somewhat too big, depending on your application.

The linear interpolation is better with an error of less than 3e-7. This is good enough for all calculations. To get a similar accuracy with the simple nearest value approximation we would need a table of 8 million entries.

We can estimate the second derivative with d²sin(x)/dx²≅-0.5*(sin(x_i)+sin(x_(i+1)) and improve on the linear approximation. This results in rather accurate results with an error of less than 3e-11. I conclude that we can get very fast and accurate approximations of the sine and cosine functions with only small tables of saved results.

But how fast are these approximations ? I used 100 million function evaluations to get reliable results. My computer is an average laptop with an Intel i7-3610QM CPU at 2.3 GHz with 8GB memory, running Linux Mint 64-bit.

All browsers take about 11 seconds for the standard Math.sin(x) function. But then I got surprised because Firefox seems to be about 5 times faster than Chrome, Chromium or Opera. Doing 100 million times an empty while-loop or an empty for-loop takes about 0.3 seconds for Firefox and 1.4 seconds for the other browsers. There does this difference come from ? I cannot explain and I am confused.

Chrome, Chromium and Opera take about 3.5 seconds to do the while loop with the function approximations. Subtracting the loop overhead, this leaves about 2 seconds for 100 million function evaluations and an acceleration by 5. There is no significant difference between the different approximations. Why ?

Firefox is much faster. The loop with the simple nearest point lookup takes only 0.35 seconds. Without loop overhead that makes 0.05 seconds per 100 million function evaluations and is 200 times faster than Math.sin ! Then, the linear interpolation takes in total 0.48 seconds, making 0.18 seconds for the function evaluation and a 60 fold acceleration. That is a great improvement ! Similarly, the improved “linear” interpolation takes 0.3 seconds for the function evaluations and makes a 30 fold acceleration. Note that the speed of these approximations decreases as expected.

In conclusion, we get a big acceleration of sine and cosine functions using Firefox and linear interpolation.

 

 

This entry was posted in programming and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s