Fast and accurate sine/cosine approximation
July 18, 2007 on 2:31 pm | In Actionscript | 50 CommentsTrigonometric functions are costly operations and can slow down your application if they are extensively used. There are two reasons why: First, Math.sin() is a function, and thus needs a function call which simple eats up some time. Second, the result is computed with much more precision than you would ever need in most situations.
Most often you just want the periodic wave-like characteristics of the sine or cosine, which can be approximated in various ways. One common way of making it faster is to create a lookup-table by computing the sine at discrete steps and storing the result in an array. For example:
var sineTable:Array = [];
for (var i:int = 0; i < 90; i++)
{
sineTable[i] = Math.sin(Math.PI/180 * i)
}
Due to the symmetry of the sine wave, it's sufficient to compute one quadrant only (0..pi/2), and the other 3/4's of the circle can be computed by shifting and wrapping the input value. The biggest drawback is that the values are stored at a fixed resolution and so the result is not very accurate. This can be enhanced with linear interpolation:
x = 22.5; y = sineTable[int(x)] + (sineTable[int(x + .5)] - sineTable[int(x)]) / 2;
Much better, but yet the error exists. It also involves accessing array elements which makes the code rather slow. Another technique uses taylor series approximation:
sin(x) = x - (x^3)/3! + (x^5)/5! - (x^7)/7! + ...
Like with the lookup-table, evaluating this term is costly.
After searching for alternatives, I finally found a fantastic solution using a quadratic curve which blows everything away in terms of performance and accuracy. For a detailed derivation, please follow the link because I won't go into it.
I did minor optimizations to figure out what AS3 likes most, and arrived at some code that can be up to 14x faster, while still being very accurate. However, you have to use it directly - do not place the code inside a function, because the additional function call sweeps out the performance gain, and you are left with an approximation that is actually slower compared to a native Math.sin() or Math.cos() call. Also note that cos(x) = sin(x + pi/2) or cos(x - pi/2) = sin(x), so computing the cosine is just of matter adding pi/2 to the input value.
Download source: fastTrig.as.
Below is a simple visualization to show you the quality of the approximation. The high precision version can replace the Math.sin() and Math.cos() calls in nearly all situations.
Low precision sine/cosine (~14x faster)
//always wrap input angle to -PI..PI
if (x < -3.14159265)
x += 6.28318531;
else
if (x > 3.14159265)
x -= 6.28318531;
//compute sine
if (x < 0)
sin = 1.27323954 * x + .405284735 * x * x;
else
sin = 1.27323954 * x - 0.405284735 * x * x;
//compute cosine: sin(x + PI/2) = cos(x)
x += 1.57079632;
if (x > 3.14159265)
x -= 6.28318531;
if (x < 0)
cos = 1.27323954 * x + 0.405284735 * x * x
else
cos = 1.27323954 * x - 0.405284735 * x * x;
}
High precision sine/cosine (~8x faster)
//always wrap input angle to -PI..PI
if (x < -3.14159265)
x += 6.28318531;
else
if (x > 3.14159265)
x -= 6.28318531;
//compute sine
if (x < 0)
{
sin = 1.27323954 * x + .405284735 * x * x;
if (sin < 0)
sin = .225 * (sin *-sin - sin) + sin;
else
sin = .225 * (sin * sin - sin) + sin;
}
else
{
sin = 1.27323954 * x - 0.405284735 * x * x;
if (sin < 0)
sin = .225 * (sin *-sin - sin) + sin;
else
sin = .225 * (sin * sin - sin) + sin;
}
//compute cosine: sin(x + PI/2) = cos(x)
x += 1.57079632;
if (x > 3.14159265)
x -= 6.28318531;
if (x < 0)
{
cos = 1.27323954 * x + 0.405284735 * x * x;
if (cos < 0)
cos = .225 * (cos *-cos - cos) + cos;
else
cos = .225 * (cos * cos - cos) + cos;
}
else
{
cos = 1.27323954 * x - 0.405284735 * x * x;
if (cos < 0)
cos = .225 * (cos *-cos - cos) + cos;
else
cos = .225 * (cos * cos - cos) + cos;
}
Nice find, though I think I’d have to be in a real optimization bind before I replaced all my sin/cos calls with all that stuff. :)
Comment by Keith Peters — July, 18 2007 #
Once again, incredible post.
There is an error in the link. The good link is :
http://lab.polygonal.de/wp-content/articles/fast_trig/fastTrig.as
Comment by Jerome — July, 18 2007 #
thank you, fixed now.
Comment by Michael — July, 18 2007 #
Woah, that’s sick! Thanks for sharing, I always stopped at the first step :/
Comment by Mr.doob — July, 19 2007 #
Awesome! Let’s see how PV3D can benefit from that! ;-)
Comment by Ralph Hauwert — July, 19 2007 #
The article on DevMaster mentions that you should avoid branching, especially in loops. I wonder if the same problem applies to AS3? Is there a speed improvement if you replace the branches by binary logic twists?
Comment by Patrick — July, 20 2007 #
Hi, it didn’t work for me (the author also says that this is not valid C code at all) Binary & converts the result to an integer. Only this works:
x -= int(x > y) && z;But the code above is a lot slower than the pure if..else statements.
Comment by Michael — July, 20 2007 #
Nice work Michael – this one goes a long way back. I think it may have been in Hart’s ‘Computer Approximations.’
One thing I’ve found helpful when working with compilers that don’t support function inlining is to use the C preprocessor or awk or something similar to do all my debugging with library calls and then have the tool replace them with inline approximations going into production.
Another benefit of having inline code is that you can combine the sin or cos computation with whatever equation it’s used in and realize additional gains by having the trig function result immediately available in a register.
regards,
- jim
Comment by Jim Armstrong — July, 20 2007 #
hey cool I didn’t know there is even a whole book about approximations only ;-) talking about preprocessors, what IDE do you use ? I was trying to integrate the C preprocessor into FlashDevelop, but failed at configuring make or ant to use it.
Comment by Michael — July, 21 2007 #
Michael:
Another classic is Cody’s ‘A Software Manual for the Elementary Functions’. There is a relatively new book by Muller – ‘Elementary Functions: Algorithms and Implementation’, but I haven’t read it yet.
I’ve given up on direct integration of other tools to any IDE – don’t have the bandwidth to work out all the issues, so I run awk or another text processor directly on the .AS files — very old school.
Best of luck in your continued (and superb) efforts!
regards,
- jim
Comment by Jim Armstrong — July, 22 2007 #
Hey thanks for the reference!
Doing University and making a blog isn’t easy but shortly some content will popout =D
Comment by Eduardo — August, 9 2007 #
[...] Fast and accurate sine/cosine approximation More code optimization to do sine/cosine operations without using the Math class. [...]
Pingback by » Blog Archive » Links: Mathematical themes with Actionscript polyGeek.com — August, 26 2007 #
[...] Fast and accurate sine/cosine approximation [...]
Pingback by 雨飞 BLOG » Blog Archive » as3效率优化 — September, 19 2007 #
Here’s a modified fixed-point version that performs better : http://blog.haxe.org/entry/26
Comment by Nicolas — November, 12 2007 #
I’ev tested this in AS2, and it’s not faster. So this optimisation trick is ONLY for AS3. Just to let you know.
Comment by JP — January, 8 2008 #
Thanks. This post was useful and more accurate than using an MS-Excell trendline function (2nd degree). Made minor changes that should speed things up since addition is cheaper than mult usually. This is the c code:
double sin(double rad){
double sine;
if (rad < 0)
sine = rad*(1.27323954 + .405284735 * rad);
else
sine = rad*(1.27323954 – 0.405284735 * rad);
if (sine < 0)
sine = sine*(-0.225 * (sine + 1) + 1);
else
sine = sine*(0.225 * (sine – 1) + 1);
return sine;
}
Comment by DYessick — January, 28 2008 #
@DYessick: I tried your version in AS3 and there is no noticeable difference unfortunately. Probably due to the weirdness of AS3.
Overall the high precision approximation gives a nice boost though, although it is closer to ~6.7 faster on my tests. This could depend on a variety of factors I imagine, not least of all your processor architecture.
Comment by brainclog — February, 4 2008 #
[...] polygonal labs ‽ Fast and accurate sine/cosine approximation (tags: optimization math) [...]
Pingback by fcicq's del.icio.us » Blog Archive » links for 2008-02-09 — February, 9 2008 #
You wrote:
“[...] it’s sufficient to compute one quadrant only (0..pi), and the other 3/4’s [...]”
But … 1/4 of 2pi is pi/2 and not pi, so a quadrant is (0..pi/2), i’m wrong ?
Greg
Comment by Gregoire — March, 4 2008 #
thanks greg, you are right. i have fixed the article.
Comment by Michael — March, 5 2008 #
More over, you can use a Quadrant but an Octant is sufficient due to the symetry (x y, -x y, -x -y, x -y, y x, -y x, -y -x, y -x)
Comment by Passault Grégoire — March, 18 2008 #
This is about 50% slower than using Math.cos(); ive found…I don’t get it? I’m not using it in a function either.
Comment by ColbyCheeze — April, 12 2008 #
always compile in release mode and use the release player (not the debug version) for doing benchmarks.
Comment by Michael — April, 12 2008 #
That makes a difference? Damn I didn’t know that…I’ll have to go find my release player, haven’t even used that thing in forever.
Comment by ColbyCheeze — April, 14 2008 #
[...] Fast and accurate sine/cosine approximation [...]
Pingback by Rozengain.com - New Media Development Blog » Blog Archive » Some ActionScript 3.0 Optimizations — August, 11 2008 #
[...] Fast and accurate sine/cosine approximation [...]
Pingback by Optimizations links | JADBOX: Web Application Musings — August, 11 2008 #
This may be a bit outdated – I think Adobe took pretty harsh to your approximation genius and generated a super fast trig table…
Compiling using the Flex 3.2 SDK, I get these results…
iterations: 1,000,000
algorithm: FastMath [ high-quality approximation ]
angle: 1.302888286613767
FastMath.sin( 1.302888286613767 ) = 0.9643253756148902
– Time: 475 ms
…
iterations: 100,000
algorithm: Math [ flash ]
angle: 1.302888286613767
Math.sin( 1.302888286613767 ) = 0.9643267785343497
– Time: 167 ms
…
Can anyone else confirm this? Thanks!
Comment by Matt Bolt — January, 2 2009 #
I also made a mistake when typing the last post….The iterations for the Math.sin() test were also = 1,000,000 – *not* 100,000.
Comment by Matt Bolt — January, 2 2009 #
hi matt,
I cannot confirm this. make sure you are using the mxmlc compiler with debug=false and run the swf inside a release player. otherwise you get misleading results. with the Flex3.2 SDK the high quality approximation is now almost exactly 10x faster on my machine.
Comment by Michael — January, 3 2009 #
[...] Optimización de operaciones con seno y coseno http://lab.polygonal.de/2007/07/18/fast-and-accurate-sinecosine-approximation/ [...]
Pingback by Rendimiento y Optimización de AS3 | ¿y por qué no? — January, 23 2009 #
Thanks alot, this really helps. But I was wondering if anyone could tell me where the numbers 0.405284735 and 0.225 came from?
Comment by Chris — January, 28 2009 #
Hi,
I know this is outdated, but these results may help somebody – these tests were done in Flash Lite 2.0 on a Nokia 6121 (I will test on more phones)
Calculating both sin and cos of 100 angles using Math.sin and Math.cos
= 6216 ms
Calculating the same thing using FastMath inline
= 4685 ms
In Flash Lite FastMath is around 25-30% faster
Just a note (it says this in the post too) that wrapping FastMath in a function call negates the speed increase, and you get the same results as just using Math.sin/cos.
Comment by Peter — February, 7 2009 #
And sorry ‘of 100 angles’ should be ‘of 1000 angles’…
Comment by Peter — February, 7 2009 #
[...] Fast and accurate sine and cosine approximation [...]
Pingback by Fast and accurate sine and cosine approximation — Some Random Dude — February, 21 2009 #
for sin, radians 0 <= x <= pi
temp = x * 2 / pi = x * 0.636619…
sin = temp * ( 2 – temp )
sin = sin * ( 0.225 * ( sin – 1 ) + 1 )
without refinement step, maximum error is 0.056 at +- 0.47
with refinement, maximum error is 0.001 at +- 1.38
for degrees, swap pi with 90
Comment by Eric Cole — February, 22 2009 #
sorry, swap pi with 180, so temp = x / 90
Comment by Eric Cole — February, 22 2009 #
[...] in January I saw this blog post by Michael Baczynski over at http://lab.polygonal.de/. The blog post describes a technique for fast [...]
Pingback by Low Precision Sine and Cosine — March, 21 2009 #
[...] a big fan of Polygonal Labs, and Michael has numerous posts such as this one that deal with fast approximation algorithms. This is another good one from his Actionscript [...]
Pingback by Actionscript Optimization « The Algorithmist — March, 27 2009 #
[...] polygonal labs » Fast and accurate sine/cosine approximation [...]
Pingback by polygonal labs » Fast and accurate sine/cosine approximation — Some Random Dude — March, 27 2009 #
[...] Fast sin/cosine approximation [...]
Pingback by Flash and the art of optimization « whitenoise — June, 19 2009 #
[...] polygonal labs – Fast and accurate sine/cosine approximation [...]
Pingback by sine approximation with fixed point math « console-dev.de — July, 6 2009 #
Hi
i want draw sine curve same as above but i need text insted of pixel
Comment by Sweety — December, 1 2009 #
[...] os usamos intensamente como por exemplo em sistemas de partículas. Por isso uma leitura a este post do Michael Baczynski é [...]
Pingback by Comunidade Portuguesa de Rich Internet Applications» Blog Archive » Introdução ao seno e coseno com Actionscript — January, 26 2010 #
[...] os usamos intensamente como por exemplo em sistemas de partículas. Por isso uma leitura a este post do Michael Baczynski é [...]
Pingback by Introdução ao seno e coseno com Actionscript - redeRIA | Agregador de noticias, artigos, tutoriais Flex, Flash, JavaFX, AJAX e Rich internet applications em geral! — January, 26 2010 #
Thanks for a wonderful post, l ve been looking for such information, I will join jour rss feed now.
Comment by Mike — March, 22 2010 #
Thanks for this. Excellent post.
Does anyone have a similar technique for Atan? I’m scratching my head a bit on this one.
Thanks.
Comment by MikeBee — April, 27 2010 #
For help with atan/atan2 check out this thread for starters. Hope it helps.
Comment by Peter — April, 28 2010 #
And this fast atan2 with very low error also seems sound.
Comment by Peter — April, 28 2010 #
Man, thanks for taking the time to post this. I’m sure you’ve been getting a few of these generic thank-you’s, but this blog is basically a godsend for us as3 game devs!
Comment by Victor Reano — May, 7 2010 #
AS3…
Code Practices Use constants when appropriate Only use variables if the value is going to change otherwise use constants. \\ References vs. lookups In general,……
Trackback by Confluence: Social City — July, 9 2010 #