optimized sine/cosine algorithms
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.)
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.
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.
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement