What is the fastest way to calculate sine?

#programming #cpp #assembly #x86 #maths

This is a fun look into some of the different ways of calculating sine as well as how they compare to a standard implementation.

💭 All views are my own 💭

[plusplusplus]

Cool video. My favorite algorithm for calculating sine is CORDIC (coordinate rotation digital computer)! It's a digit-by-digit algorithm, so it converges relatively slowly, but it's also a shift-and-add algorithm, so you don't need to do any of those difficult multiplications or divisions. It's so simple to implement but also so versatile (you can use it for trigonometry, linear algebra, logarithms, etc.) that some limited processing power microcontrollers will even use CORDIC to implement floating point math.
I'm wary of posting links as I've already had this comment nuked by youtube once, but wikipedia has a great article on it and looking up "CORDIC, What is it?" on google will bring you to a great post on the Signal Processing Stack Exchange.

[damouze]

I was surprised to see that the x87 assembly instruction was slower. You would think that Intel and AMD would be able to keep these fast enough that a software solution is not necessary.

One of my universtiy assignments was to design a "fraction" class in C++, complete with operator overloading. You would get extra points if your class supported the three basic trigonometric functions. I also used the Taylor series for them and they were fun to implement.

[happytoaster]

fsin uses the old 80 bit legacy registers. With SSE (always available these days), you can do 32 bit operations, which obviously cuts the work required.

[dedvzer]

Kaze Emanuar recently did a video on this exact problem for the N64, using the only the first 1/8th of a period and some clever math to beat a 2nd or 3rd order polynomial (I think..). Might be fun to try on x86

[ryanpmcguire]

This is surprisingly topical and relevant for me as I am looking into using a fast lookup implementation with a bunch of pointer magic to very quickly calculate HUGE Fourier series sums (20, 000 sines) in real time.

The idea is to use position pointers and loop back pointers to quickly sum a list of positions on the lookup table.

[NeuwDk]

You could try approximating sine with a parabola; you can get quite good accuracy when doing that. I was looking into it a few months ago.

[lewismassie]

I've used x = sin(x) when dealing with very small angles before. Usually it's been when I'm estimating some of the other values in the calculation so the error is not as important as the rough correct number

[Kaelygon]

I made uint sine in c++ by calculating 2 periods of parabolas by bit manipulating and flipping latter half. For my use case it is 3-20 times faster, depending if it is input random or linear values when generating waveforms or tones.
These are fastest with gcc -Os flag and when you work with range 0 to uint_max like raw audio files. The functions are generalized to work in 8, 16, 32 and 64 bits. There's desmos page in comment explaining math behind this. Max error is 2.8%
Youtube keeps marking this as spam I believe. pastebin is GfEDzmCj

[logansmith-perkins]

This is a very interesting question. I've gotta watch

[gwentarinokripperinolkjdsf]

I remeber developing a method in highschool, it's super slow, and actually it only works for a quarter circle (trivially easy to solve that though).
Basically, you can easily calculate a normal vector for any vector by dividing by it's length, and if you take the average of any two points on a unit circle then normalize the vector you can get the vector of the angle really easily. So you can just do a binary search

[Az]

I'm so used to sin being defined in terms of circles. that when you said it's the ratio of the side lengths of a triangle I was so confused .

[leonard]

how about caching? precalculate at a 1000 different intervals and after that interpolate when you do a lookup.
is this faster? or is it just wasted energy?
I know this is what they used to do for old school DOOM but don't know if it's still useful to do.

[undeadpresident]

I've made functions that calc sin/cos/arctan using interpolation, circular motion formulas, incrementing sin/cos by multiplying them in a certain way at ever decreasing increments, and Taylor series, but I don't understand how to use Chebyshev polynomials...

So three expansions for the Chebyshev polynomial is just (3 * (theta^3) ) - (3 * theta) ? I was trying that and getting values over 1...

When I've watched videos on Chebyshev, the most I've been able to grasp is some interesting functions for incrementing and interpolating cosines, but I'm supposing that's not the right way to do it.

I could use some pointing in the right direction.

[theevilcottonball]

Have you tried interpolating the sine function with something like a cubic spline? Or is that too lookup-tabley for ya?

[ocrovest]

why use the whole range form 0 to 2pi? since 0 to pi/2 is enough. mirror it and flip it when needed

[SameAsAnyOtherStranger]

I get that this is essentially an exercise in running waveform formulas to test for efficiency as much as it is about actually achieving a faster sign wave. I get that and being limited to a predetermined range, but not much else.

It seems to me that real time signals processing is hampered by having to run code in binary that would be a much more straightforward operation for balanced ternary CPUs. I saw a video where an instructor in a class said that there were ternary components in Intel CPUs, but I couldn't find anything to verify this.

[DeathSugar]

There's compromise between speed, precision and memory consumption to store lookup tables. Some wooden computers of Raspberry Pi level potentially work better with bigger lookup tables.

[minorlogic]

As fun alterative, use composition of polynomials.

[theexplosionist]

The FPU has been obsolete since 1999. FPU sine is micro-coded hence its slow.

[jedcheng]

May I have the link to the stack overflow question on the speed of hardware trigonometry functions? I would like to look more into it