What is the fastest way to calculate sine?

Рет қаралды 23,192

Күн бұрын

#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 💭
Link to source: github.com/iris-engine-dev/ca...

Пікірлер: 80

@plusplusplus9837 Жыл бұрын

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.

@nathanbaggs Жыл бұрын

Glad you enjoyed it. Thanks for the suggestion!

@turun_ambartanen Жыл бұрын

Finally someone else mentioning KZbin removing comments with links in them. I thought I was going crazy. Even simple wikipedia links are removed all the time. It makes KZbin incredibly bad to have any kind of discussion.

@stickguy9109 Жыл бұрын

Try zooming in on the code next time

@nathanbaggs Жыл бұрын

Thanks for the feedback. Was there specific code that was too small? The background code was just to avoid having a blank frame, it wasn’t todo with the project. Maybe I could make that clearer?

@danielsena6161 Жыл бұрын

@@nathanbaggs It maybe because It looked like the code on the background had something to do with the topic

@KXBeats Жыл бұрын

@@nathanbaggs i think if you keep it blurred it should be clear

@jesse8521 Жыл бұрын

I literally can’t read any of the code

@rutabega306 Жыл бұрын

Nothing wrong with a blank frame.. just saying :)

@dedvzer 7 ай бұрын

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

@damouze 4 ай бұрын

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.

@thoriqadillah7780 Жыл бұрын

Finally, myopia challenge

@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.

@nathanbaggs Жыл бұрын

Thanks for the suggestion!

@NeuwDk Жыл бұрын

@@nathanbaggs I've tried to link to a forum post that shows exactly how to do it - but youtube keeps removing the reply -.-'

@Johnny-tw5pr 8 ай бұрын

Isn't that what the Taylor series is?

@lazerpie101 7 ай бұрын

@@Johnny-tw5pr not really, the most notable difference is that taylor series goes from -pi to pi accurately, making 2 'bumps,' 1 negative, 1 positive. a parabola only does 1 bump. a parabola is just x^2, meaning it only works for numbers from 0 up to pi, which means it's more complicated to check if a number's negative or not. taylor series works from -pi to pi, meaning it's simpler to give a proper check for if the number's negative. There is also the problem that using x^2 (even when modifying the parabola to better fit sine) is less accurate, and in my testing can even go as far off as .03, which can be a pretty major deviation, compared to taylor series, which has incredible accuracy in only 6 degrees of the series.

@372leonard Жыл бұрын

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.

@nathanbaggs Жыл бұрын

As I said at the end I didn’t really look into caching as I was more interested in how you actually calculate the values. Seeing as the glibc sin uses a lookup table I’d say it’s certainly viable.

@wile9763 Жыл бұрын

My guess is that a lookup table that large would be slower than a typical Taylor series approach, due to the increased amount of time to fetch the data. A Taylor series approach only requires a few muladds and jump instructions.

@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.

@xinfinity4756 Жыл бұрын

Do you think you could explain the logic behind your idea for that implementation a little more?

@nathanbaggs Жыл бұрын

Glad you found it useful!

@ryanpmcguire Жыл бұрын

@@xinfinity4756 Instead of calling for a sine approximation 20,000 times, you make one "good enough" sine approximation small enough to fit in the cpu cache. Directly after the sine in memory is a table of pointers leading back to the sine lookup table. the idea is to iterate each oscillator's position in the lookup table and use a 'buffer overflow' style approach to reset each oscillator's position when they overshoot the sine table in memory. In essence, it is a real oscillation within the cpu/memory - not a calculated one. This would be useful in rendering FFT data into an audio signal in real time. It would make audio synthesis way better.

@godofecht Жыл бұрын

@@ryanpmcguire Neat idea! Do you use JUCE?

@kanshank Жыл бұрын

@@ryanpmcguire I was thiniking of ram but cpu cache is even better ! It could be dumb, I didn't dig the question. But why not construct your sin [ 0; pi] with point and straight line with slope of 2 or 1/2. So you can correct value by addition and shifting the bytes right ( x 1/2 ) and left (x2)

@logansmith-perkins515 Жыл бұрын

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

@logansmith-perkins515 Жыл бұрын

Great video! It's smart to selectively choose the sine function depending on the range from 0 to 2pi. std::sin was most likely to be the most optimized anyway.

@nathanbaggs Жыл бұрын

Glad you enjoyed it (:

@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

@nathanbaggs Жыл бұрын

It’s a nice optimisation (:

@gwentarinokripperinolkjdsf683 Жыл бұрын

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

@nathanbaggs Жыл бұрын

That’s interesting, thanks for sharing!

@Az181 9 ай бұрын

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 .

@jedcheng5551 Жыл бұрын

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

@nathanbaggs Жыл бұрын

Of course: stackoverflow.com/questions/12485190/calling-fsincos-instruction-in-llvm-slower-than-calling-libc-sin-cos-functions

@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.

@turun_ambartanen Жыл бұрын

High end network equipment emulates ternary logic in order to match network masks. Ternary logic allows to determine the result as Yes/No/Doesn't matter much more quickly than binary logic. I'm not aware of any such (emulated or not) ternary logic in regular CPUs and I don't think there are any real processors sold that actually use ternary logic. I think the advantages are just too small to make it competitive against the very very mature binary stuff we have now.

@undeadpresident 9 ай бұрын

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.

@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.

@Kaelygon 11 ай бұрын

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% KZbin keeps marking this as spam I believe. pastebin is GfEDzmCj

@nathanbaggs 10 ай бұрын

Interesting technique

@theevilcottonball Ай бұрын

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

@theexplosionist2019 6 ай бұрын

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

@thoriqadillah7780 Жыл бұрын

Clearest code display in Ohio

@nathanbaggs Жыл бұрын

Thanks for the feedback, did you find all the text too big or just specific parts?

@KXBeats Жыл бұрын

@@nathanbaggs he meant the background code and also was sarcastic about it in case you didnt notice. i am also wondering, what display are you coding on to be able to have so much code on screen at a time and also have it so small?

@parlor3115 Жыл бұрын

@@KXBeats It's just a background bro. Do you seriously think that code is meant to be read? Don't you see enough code in your job to want to see other people's code?

@lukaszspychaj9210 Жыл бұрын

Funniest Ohio joke

@wompastompa3692 Ай бұрын

Assume small angle and use sin(x)=x.

@king_james_official 23 күн бұрын

god what's your monitor's res

@gigantopithecus8254 5 ай бұрын

i use the chebesv polinomal

@JerryThings Жыл бұрын

From what I know x87 is slower than x86, but I'm not sure how sine/cosine are calculated in x86 without win32.

@nathanbaggs Жыл бұрын

I have a look at the glibc implementation in the video

@victorius2975 Жыл бұрын

meanwhile my ass just getting the sine from getting the x coordinate of a dot moving in a circle

@madghostek3026 Жыл бұрын

That's dissapointing how assembly trig instructions are so much worse, lesson is to always benchmark stuff

@nathanbaggs Жыл бұрын

Agreed. There's this idea that you can use assembly to "beat the compiler", but it's not always true.

@pxolqopt3597 Жыл бұрын

@@nathanbaggs that saying refers to the assembly output of a compiler vs a human and not replacing several lines of assembly into a single instruction.