I remember doing this in Macromedia Flash as I wanted to make stuff go in circles and the language didn't have any higher math functions back then. Good ole times.
Implementing Cosine in C from Scratch (2020)
11–20 of 139 posts
Re: Implementing Cosine in C from Scratch (2020)
#12The implementation of the __cos kernel in Musl is actually quite elegant. After reducing the input to the range [-pi/4, pi/4], it just applies the best degree-14 polynomial for approximating the cosine on this interval. It turns out that this suffices for having an error that is less than the machine precision. The coefficients of this polynomial can be computed with the Remez algorithm, but even truncating the Chebyshev expansion is going to yield much better results than any of the methods proposed by the author.
Re: Implementing Cosine in C from Scratch (2020)
#13My favorite implementation of a super fast but not that accurate cosinus is from a now defunct forum. Good thing we have webarchive ! https://web.archive.org/web/20111104163237/http://www.devmas...
You can also use the Chebyshev polynomials to economise a higher degree taylor series with bit of a loss of accuracy.
Re: Implementing Cosine in C from Scratch (2020)
#14I teach lookup tables specifically for sine/cosine (we just use one with a phase shift and modulus) on the Gameboy Advance. The hardware has no floating point unit support, so we do it in 8.8 fixed point with 1-degree resolution.
It turns out the BIOS on the hardware can do sine/cosine, but you have to do that via inline assembly (swi calls) and it's no faster than the simple lookup table.
This is all just to get terms for the affine matrix when rotating sprites/backgrounds.
Re: Implementing Cosine in C from Scratch (2020)
#15The implementation of the __cos kernel in Musl is actually quite elegant. After reducing the input to the range [-pi/4, pi/4], it just applies the best degree-14 polynomial for approximating the cosine on this interval. It turns out that this suffices for having an error that is less than the machine precision. The coefficients of this polynomial can be computed with the Remez algorithm, but even truncating the Cheby…
Re: Implementing Cosine in C from Scratch (2020)
#16Earlier quoted context omitted.
>> lookup tables and lerp are the most common solution I've seen The author missed one nice table method. When you need sin() and cos() split the angle into a coarse and fine angle. Coarse might be 1/256 of a circle and fine would be 1/65536 of a circle (whatever that angle is). You look up the sin/cos of the coarse angle in a 256 entry table. Then you rotate that by the fine angle which uses another 256 sin * cos en…
> Then you rotate that by the fine angle Explain? Are you trying to reduce the error in the linear interpolation by describing the convex curve between the endpoints? The derivative of the cosine is the sine, and the derivative of the sine is the cosine...so I'd expect the required output of the fine angle table to interpolate 0.15 between 0.1 and 0.2 and the required output to interpolate 45.15 between 45.1 and 45.2…
Remember that cos(a+b)=cos(a)cos(b)-sin(a)sin(b)
Re: Implementing Cosine in C from Scratch (2020)
#17Earlier quoted context omitted.
>> lookup tables and lerp are the most common solution I've seen The author missed one nice table method. When you need sin() and cos() split the angle into a coarse and fine angle. Coarse might be 1/256 of a circle and fine would be 1/65536 of a circle (whatever that angle is). You look up the sin/cos of the coarse angle in a 256 entry table. Then you rotate that by the fine angle which uses another 256 sin * cos en…
> Then you rotate that by the fine angle Explain? Are you trying to reduce the error in the linear interpolation by describing the convex curve between the endpoints? The derivative of the cosine is the sine, and the derivative of the sine is the cosine...so I'd expect the required output of the fine angle table to interpolate 0.15 between 0.1 and 0.2 and the required output to interpolate 45.15 between 45.1 and 45.2…
>> Explain?
Yeah I thought that might not be clear enough. Let's say you want 0.1 degree accuracy but don't want a 3600 entry table. Make one table for every 1 degree. You get to use the same table for sin and cos by changing the index. That is the coarse table with 360 entries. Then make another table with sin and cos values for every 0.1 degrees, or specifically 0.1*n for n going from 0-9. This is another 20 values, 10 sin and 10 cos for small angles.
Take your input angle and split it into a coarse (integer degrees) and fine (fractional degrees) angle. Now take the (sin(x),cos(x)) from the coarse table as a vector and rotate it using the sin & cos values of the fine angle using a standard 2x2 rotation matrix.
You can size these tables however you need. I would not use 360 and 10 for their sizes, but maybe 256 and 256. This can also be repeated with a 3rd table for "extra fine" angles.
Re: Implementing Cosine in C from Scratch (2020)
#18Mandatory Physics "troll" comment:
For small angles, sin(x) ~= x and cos(x) ~= 1 -- the ["small angle approximation"](https://en.wikipedia.org/wiki/Small-angle_approximation)
It's actually kind of ridiculous how many times it comes up and works well enough in undergraduate Mechanics.
Re: Implementing Cosine in C from Scratch (2020)
#19Here's a solution which is vectorizable: http://gallium.inria.fr/blog/fast-vectorizable-math-approx/
I've also read that Chebyshev polynomials are far better for approximating functions than Taylor series (eg https://en.wikipedia.org/wiki/Approximation_theory)
Re: Implementing Cosine in C from Scratch (2020)
#20Mandatory Physics "troll" comment: For small angles, sin(x) ~= x and cos(x) ~= 1 -- the ["small angle approximation"]( https://en.wikipedia.org/wiki/Small-angle_approximation ) It's actually kind of ridiculous how many times it comes up and works well enough in undergraduate Mechanics.
This a perfectly nice Programming 101 example of a recursive function -- if an angle is too large, calculate its sine using the sine of the half-angle, otherwise return the angle (or, if you're fancy, some simple polynomial approximation of the sine). I'm sure everyone did this in school (we did, in fact).