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

131–139 of 139 posts

Re: Implementing Cosine in C from Scratch (2020)

#131

Post by jhgb »

jeremysalwen wrote: post #122
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…

Thanks for explaining this. I actually wrote a SIMD implementation of trig functions years ago, using the techniques you describe. You can check it out: https://github.com/jeremysalwen/vectrig I compared several different methods of generating polynomials of different sizes for speed and precision (spoilers: taylor series were the worst and minimax polynomials (Remez algorithm) were the best). Another (surprising) th…

> I compared several different methods of generating polynomials of different sizes for speed and precision (spoilers: taylor series were the worst and minimax polynomials (Remez algorithm) were the best).

I would have expected at least an LSQ approximation with a basis of Legendre polynomials thrown into the mix. I got that as a basic homework in my numerics class once, after we've shown to ourselves in the class that [1, x, x², x³...] is not a really good basis to project things onto.

Re: Implementing Cosine in C from Scratch (2020)

#132

Post by djmips »

nwallin wrote: post #94

It's all well and good to have a library with fast sin/cos/tan functions, but always remember to cheat if you can. For instance, in a game, it's common to have a gun/spell or whatever that shoots enemies in a cone shape. Like a shotgun or burning hands. One way to code this is to calculate the angle between where you're pointing and the enemies, (using arccos) and if that angle is small enough, apply the damage or wh…

Nice! Also see

https://fgiesen.wordpress.com/2010/10/21/finish-your-derivat...

Re: Implementing Cosine in C from Scratch (2020)

#133

Post by adgjlsfhk1 »

ramshorns wrote: post #130
adgjlsfhk1 wrote: post #83

Earlier quoted context omitted.

It's not just sub-normal numbers. As https://randomascii.wordpress.com/2014/10/09/intel-underesti... shows, fsin only uses 66 bits of pi, which means you have roughly no precision whenever abs(sin(x))<10^-16 which is way bigger than the biggest subnormal (10^-307 or so)

In that range, just returning x would be way better. Maybe even perfect actually - if x is less than 10^-16, then the error of x^3/6 is less than the machine precision for x.

the error isn't when x is small. it's when sin(x) is small. the problem happens for x near multiples of pi

Re: Implementing Cosine in C from Scratch (2020)

#134

Post by aj7 »

chmaynard wrote: post #108
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.

They are long dead. It was sad. They doted on me and my sister because they had no kids. He was a salesman. He knew how to get books in Manhattan. He used to get my sister classics with the most beautiful color plate illustrations. In the sixties, these had little value. Today?

Re: Implementing Cosine in C from Scratch (2020)

#135

Post by 0x20cowboy »

I haven’t seen this version mentioned in the thread - if you don’t need a lot of precision, here is a simple 4 line version[1] and here’s how it works[2].

Not sure who initially came up with it.

[1] https://github.com/robrohan/wefx/blob/1a918cc2d5ad87402a3830...

[2] https://www.desmos.com/calculator/lo7cf60mjz

Re: Implementing Cosine in C from Scratch (2020)

#136

Post by adgjlsfhk1 »

bertr4nd wrote: post #121
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…

Are there libraries/tools that people use to do Remez/Chebyshev/etc. function expansions? I can do a basic Taylor series expansion by hand but I’m out of my depth with more sophisticated techniques.

sollya is the king here

Re: Implementing Cosine in C from Scratch (2020)

#137

Post by bertr4nd »

adgjlsfhk1 wrote: post #136
bertr4nd wrote: post #121

Earlier quoted context omitted.

Are there libraries/tools that people use to do Remez/Chebyshev/etc. function expansions? I can do a basic Taylor series expansion by hand but I’m out of my depth with more sophisticated techniques.

sollya is the king here

Thanks!

Re: Implementing Cosine in C from Scratch (2020)

#138

Post by em3rgent0rdr »

Asraelite wrote: post #113
em3rgent0rdr wrote: post #43

Earlier quoted context omitted.

I guess scratch (or LOGO) is Turing complete, so someone could make a CPU built using a little turtle in a box where all functionality is built out of LOGO commands.

It's not just Turing complete but even practical. People have built entire CPU emulators that run pretty fast, e.g. https://scratch.mit.edu/projects/175052082/

Amazing!

Re: Implementing Cosine in C from Scratch (2020)

#139

Post by LeifCarrotson »

marginalia_nu wrote: post #16
LeifCarrotson wrote: post #9

Earlier quoted context omitted.

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

Ah, now it makes sense. Thanks for the reminder of 8th grade trig...it's been a while!
Post reply on HN