This takes me back in time, to c. 1982 when I got curious about how computers calculated trig functions. Luckily I was using one of the first OSS systems (modulo AT&T lawyers): Unix V7. So I pulled up the source and took a look. You can still see it here: https://github.com/v7unix/v7unix/blob/master/v7/usr/src/libm...
There's a comment referencing "Hart & Cheney", which is this book : https://www.google.com/books/edition/Computer_Approximations...
Also luckily I had access to a library that had the book which I was able to read, at least in part.
This taught me a few things : that the behavior of a computer can be a white box, not a black box; the value of having access to the source code; to use comments effectively; that for many difficult tasks someone probably had written a book on the subject. Also that polynomials can approximate transcendental functions.
Implementing Cosine in C from Scratch (2020)
91–100 of 139 posts
Re: Implementing Cosine in C from Scratch (2020)
#92Mandatory 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.
Dont forget optics, there tan x=sin x
Yep, it's all over Physics, really. Many non-mechanical concepts are often mapped to a mechanical analog model (so many tiny oscillators out there!).
Re: Implementing Cosine in C from Scratch (2020)
#93Earlier quoted context omitted.
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).
It's not obvious when you should switch over to an approximation (base case), so I'd say it's not a good example to introduce recursion. I have never seen it, and I did not do it in school.
When the difference between iterations is less than whatever threshold of accuracy you're looking for, I'd assume.
"Relaxation" algorithms for calculating fields work that way.
Re: Implementing Cosine in C from Scratch (2020)
#94It'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 whatever.
A better way to do it to take the vector where the shotgun is pointing, and the vector to a candidate enemy is, and take the dot product of those two. Pre-compute the cosine of the angle of effect, and compare the dot product to that -- if the dot product is higher, it's a hit, if it's lower, it's a miss. (you can get away with very rough normalization in a game, for instance using the rqsrt instruction in sse2) You've taken a potentially slow arccos operation and turned it into a fast handful of basic float operations.
Or for instance, you're moving something in a circle over time. You might have something like
float angle = 0
for (...)
angle += 0.01
const float sin_dx = sin(0.01)
const float cos_dx = cos(0.01)
float sin_angle = 0
float cos_angle = 1
for (...)
const float new_sin_angle = sin_angle * cos_dx + cos_angle * sin_dx
cos_angle = cos_angle * cos_dx - sin_angle * sin_dx
sin_angle = new_sin_angle
And there's the ever popular comparing squares of distances instead of comparing distances, saving yourself a square root.
In general, inner loops should never have a transcendental or exact square root in them. If you think you need it, there's almost always a way to hoist from an inner loop out into an outer loop.
Re: Implementing Cosine in C from Scratch (2020)
#95Earlier quoted context omitted.
This has been the standard algorithm used by every libm for decades. Its not special to Musl.
But isn't this code rarely called in practice? I guess on intel architectures the compiler just calls the fsin instruction of the cpu.
Wasn't there some blog article a few years ago which showed how glibc's implementation was faster than fsin ?
Re: Implementing Cosine in C from Scratch (2020)
#96The article uses a game movement function as a possible motivation for needing the cosine. If object.rotation is constant as the spiral animation seems to suggest, there is an important optimization for rapidly computing the sequence: cos(theta), cos(theta + delta), cos(theta + 2delta), cos(theta + 3delta), ...
This comes up in movement under constant rate of rotation as well as Fourier transforms. See [1] for details, but the basic idea uses the simple trig identities:
cos(theta + delta) = cos(theta) - (a*cos(theta) + b*sin(theta))
sin(theta + delta) = sin(theta) - (a*sin(theta) - b*cos(theta))
a = 2 sin^2(delta/2)
b = sin(delta)
[1] Press, William H. et. al., Numerical Recipes, Third Edition, Cambridge University Press, p. 219
Re: Implementing Cosine in C from Scratch (2020)
#97Earlier quoted context omitted.
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).
It's not obvious when you should switch over to an approximation (base case), so I'd say it's not a good example to introduce recursion. I have never seen it, and I did not do it in school.
It's "obvious" if you remember how the Taylor series for sin(x) works. The error between x and sin(x) is bounded above by x^3/6. So there you go.
Re: Implementing Cosine in C from Scratch (2020)
#98I think off-zero Taylor series along with lookup table should be at least tried. You can approximate cos(x+a) using only cos(a) and sin(a) and the series converges really fast
Remez always beats Taylor series.
Re: Implementing Cosine in C from Scratch (2020)
#99This is a fun article! Alternative avenues that complement the approaches shown: - Padé Approximants ( https://en.wikipedia.org/wiki/Pad%C3%A9_approximant ) can be better than long Taylor Series for this kind of thing. - Bhaskara I's sin approximation ( https://en.wikipedia.org/wiki/Bhaskara_I%27s_sine_approximat... ) is easily adaptable to cosine, remarkably accurate for its simplicity and also fast to calculate.
I have a few cases where I think a Padé approximation could really help me, but I've never been able to figure out, given a function, how to get the coefficients.
Do you have any suggested reading?
Re: Implementing Cosine in C from Scratch (2020)
#100Earlier quoted context omitted.
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).
It's not obvious when you should switch over to an approximation (base case), so I'd say it's not a good example to introduce recursion. I have never seen it, and I did not do it in school.
For a physicist sin(x) ~= x if x^3/6 << x