Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Implementing Cosine in C from Scratch (2020)

austinhenley.com

Post reply on HN
Print view View original

101–110 of 139 posts

Re: Implementing Cosine in C from Scratch (2020)

#101

Post by ajross »

dancsi wrote: post #12

The 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…

That's got nothing to do with Musl per se, that's just the SunPro code that basically every C library uses. I'm sure the polynomials themselves (there's another one for the "crest" of the sin curve, and still more for log and exp and the rest of the family) date from somewhere in computing pre-history. Optimizing polynomial fits to analytic functions was something you could do on extremely early computers.

Re: Implementing Cosine in C from Scratch (2020)

#102

Post by arthur2e5 »

It’s an old article, so… guess I won’t beat a dead horse as much.

* The range reduction is, well, probably worse than acos. Look for Payne–Hanek–Corbett. Not an issue for games, I assume.

* The LERP is nice and all, but Qt actually has an even better one: instead of doing a LERP, you use the local derivative also available from the lookup table. https://stackoverflow.com/a/52841086

Others have already mentioned the Remez and the Horner stuff. Won’t repeat here.

Re: Implementing Cosine in C from Scratch (2020)

#103

Post by arthur2e5 »

freemint wrote: post #29
xioxox wrote: post #19

Here'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 )

This matters less once you put things through the horner scheme. And if you are not you are leaving performance on the table.

Horner does not conflict with vectorization in this case. If you read the code, it actually uses Horner — the vectorizability applies to when you call the online function in a loop.

Re: Implementing Cosine in C from Scratch (2020)

#104

Post by adgjlsfhk1 »

jacobolus wrote: post #90
lifthrasiir wrote: post #81

Earlier quoted context omitted.

It does use Horner's rule, but splits the expression into two halves in order to exploit instruction-level parallelism.

Considering the form of both halves is the same, are compilers smart enough to vectorize this code?

I might be wrong but I would think for something like this vectorizing wouldn't save time (since you would have to move data around before and afterwards. The real benefit of this is it lets you run two fma operations in parallel.

Re: Implementing Cosine in C from Scratch (2020)

#105

Post by anonymousiam »

adgjlsfhk1 wrote: post #54
anonymousiam wrote: post #35

I did the same thing for sqrt() seven years ago. It benchmarked at about five times faster than math.h/libm, but the trade was a reduction in the maximum value of the result. My version would not produce accurate results for inputs greater than 2^16. It did work very well for generating real-time laser pointing X/Y coordinates for an Archimedean Spiral. https://en.wikipedia.org/wiki/Archimedean_spiral (This was on a…

I'm surprised this was faster than an initial guess (half the exponent and mantisa) followed by newton's method.

Newton's method involves division, which is a problem on an embedded platform with a limited FPU that can only do multiplication. I tried several classic approaches and benchmarked all of them against the function in libm. I reviewed what I did and it turns out that my own memory is not that great. My version (nsqrt) is limited to input values of less than 2^14 and not 2^16 as I said above. Also, it's only 50% faster and not 5x as I said above.

Even a 50% increase in speed was well worth my effort though.

* Replacement sqrtf() function. This function runs about 50% faster than

* the one in the TI math library. It provides identical accuracy, but

* it is limited to input values less than 2^14. This shouldn't be a problem

* because the passed argument will always be in the range of

* 0-(max spiral scan period). The spiral scan period is presently about

* 140 seconds.

Re: Implementing Cosine in C from Scratch (2020)

#106

Post by spacechild1 »

munificent wrote: post #25
dekhn wrote: post #4

lookup tables and lerp are the most common solution I've seen (for a wide range of functions). You can also memorize with an LRU cache.

Yeah, lerping into a lookup table is common in audio and (old school) games. A common trick to make that faster is to not use doubles and radians to represent the phase. Instead, represent phase using an integer in some power-of-two range. That lets you truncate the phase to fit in a single period using a bit mask instead of the relatively slow modulo.

Or use some evil bit hackery :-) https://github.com/pure-data/pure-data/blob/18c9695ba4de543c...

Re: Implementing Cosine in C from Scratch (2020)

#107

Post by spacechild1 »

naoqj wrote: post #24

>I couldn't find any notable projects on GitHub that use a table for trig functions, but I'm sure they exist. Doom?

Pure Data: https://github.com/pure-data/pure-data/blob/18c9695ba4de543c...

SuperCollider: https://github.com/supercollider/supercollider/blob/ec2dedfd...

Re: Implementing Cosine in C from Scratch (2020)

#108

Post by chmaynard »

aj7 wrote: post #64

So 57 years ago, there weren’t any programming books. Well, there was one. McCracken and Dorn, Numerical Methods and Fortran Programming. A kindly childless couple, Ben and Bluma Goldin, who lived in the same apartment house in Brooklyn, bought me this book as a gift. An axiomatic lesson from the book was distrust of Taylor expansions, and the necessity of moving the expansion point of any function to a favorable loc…

Why tell us the couple's names and tell us they were childless? Strange. I'm not inclined to trust anything you said after that.

Re: Implementing Cosine in C from Scratch (2020)

#109

Post by eyelidlessness »

chrisseaton wrote: post #86
enriquto wrote: post #72

Earlier quoted context omitted.

> the FPU, which is basically legacy you'll pry my long doubles from my cold, dead hands!

You're selectively quoting me - I said it's 'legacy emulated'. It's emulated using very long-form microcode, so basically emulated in software. I didn't say it was simply 'legacy'.

I’m completely out of my depth reading through these comments so I don’t have much of value to contribute, but I do think I can gently say I think the selective quoting was harmless, but deliberate to fit the shape of a harmless joke’s setup. I don’t think there was any intent to misrepresent your more salient information.

Re: Implementing Cosine in C from Scratch (2020)

#110

Post by eyelidlessness »

jhgb wrote: post #20
aaaronic wrote: post #18

Mandatory 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).

I didn’t do this (or any programming, or any trigonometry) in school, but I’m appreciative of tidbits like this from people who did. I definitely feel comfortable with recursion, and have a stalled art project which could benefit from better understanding how to apply trig as I accumulate understanding in a much less structured way.
Post reply on HN