Sign in to follow this  
Matthew Doucette

optimized sine/cosine algorithms

Recommended Posts

I'm looking for fast, optimized, sine and/or cosine algorithms. Any info is appreciated. Depending on the accuracy of the algorithms, I will use them in various places in my code in place of the default sin() and cos() functions in Visual C++. I am assuming faster algorithms exist. 100% accuracy is not necessary. (One option I have considered is a simple look up table. Another thought was to use Taylor series, or something similar, and only "go" so far. If you have any experience with this, I would love to hear your opinion.)

Share this post


Link to post
Share on other sites
Lookup table is a good idea if you don't need 100% accuracy. It should be pretty simple to set up a test app and test it, I did it a few months ago and remember having good results. I see if I can find it.

Share this post


Link to post
Share on other sites
If you only need sequential access to sine and cosine functions then one extremely fast way is to use AR-model (aka IIR-filter or recurrence equation) to produce the sine. This only requires one multiplication per sample. There might be some problems with numerical stability but when using fixed-point ops they haven't been a real problem to me (and not with floating-point either, but this I haven't tested so extensively).

Here's the z-transform for sin:
u[n]*sin(w0*n) <=Z=> ( sin(w0)*z^-1 )/( 1 - 2*cos(w0)*z^-1 + z^-2 )

If you need random access, I think you could get away with smaller LUT if you would use AR-model to iterate into correct solution from some coarse LUT value. I mean that you would only store values for indices M*n instead of n and you would have to iterate at most M-1 times.. M/2 times at average.
That is you could get away with M/2 muls per sample when using small LUT and recursive calc of sin.

Share this post


Link to post
Share on other sites
x_gamer_x, I have used lookup tables for some real-time 3D graphics (for rotation). It was used in my older real-time graphics work. It worked really well from what I remember. I actually cannot see many algorithms faster than a lookup table. The only sacrafice is the memory.

Winograd, I mostly need random access, but thanks for the sequential access idea. I love to hear new ideas like this. You never know when it might inspire a better solution for something in the future.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this