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

How do computers calculate sine?

androidcalculator.com

Post reply on HN
Print view View original

151–160 of 167 posts

Re: How do computers calculate sine?

#151

Post by nwellnhof »

mads wrote: post #121
staplung wrote: post #94

I recently learned how Doom was ported to the SNES. It's quite impressive. The SNES hardware was nowhere near fast enough to do all the trig calculations needed for the game but cartridge based games had a trick up their sleeve: they could include actual hardware inside the cart that the game code could make use of. It was more expensive but if you expected to sell a boatload of copies, it could be worth it. However,…

Back in the 80's, when I made demos on the C64, we also used pre-calculated sines. I remember going to the library to get a book with the values.

I just wrote a BASIC program generating values using the SIN function [1] and poked them into memory.

[1] https://www.c64-wiki.com/wiki/SIN

Re: How do computers calculate sine?

#152

Post by albrewer »

mads wrote: post #121
staplung wrote: post #94

I recently learned how Doom was ported to the SNES. It's quite impressive. The SNES hardware was nowhere near fast enough to do all the trig calculations needed for the game but cartridge based games had a trick up their sleeve: they could include actual hardware inside the cart that the game code could make use of. It was more expensive but if you expected to sell a boatload of copies, it could be worth it. However,…

Back in the 80's, when I made demos on the C64, we also used pre-calculated sines. I remember going to the library to get a book with the values.

Abramowitz and Stegun's Handbook of Mathematical Functions[0] - I still use it to test whenever I need to implement any kind of fundamental math function that's not built into whatever environment I'm using. Haven't used it in some time but it comes in handy.

[0]https://en.wikipedia.org/wiki/Abramowitz_and_Stegun

Re: How do computers calculate sine?

#153

Post by albrewer »

aoanla wrote: post #131
inkyoto wrote: post #123

Earlier quoted context omitted.

> […] pre-calculated lookup tables […] The approach is older than that. I remember my grandfather's engineering books from 1950's – nearly each of them had a large addendum with the said pre-calculated sine, cosine, tangent and logarithm lookup tables. And there was at least one book that only had such tables and no other information. That is how engineers used to calculate before the advent of computers.

The classic of this field of books is Abramowitz and Stegun's "Handbook of Mathematical Functions" - although the two listed names are merely those of the compilation editors, as the calculations of the numerous tables of values (and sheets of mathematical identities) required hundreds of human computers operating for years. Ironically, on publication in 1964 it was just in time to see the dawn of the electronic comp…

I still use it when testing implementations of mathematical functions. Like if all I need is a bessel function, why pull in a whole CAS to do that?

Re: How do computers calculate sine?

#154

Post by pengaru »

staplung wrote: post #94

I recently learned how Doom was ported to the SNES. It's quite impressive. The SNES hardware was nowhere near fast enough to do all the trig calculations needed for the game but cartridge based games had a trick up their sleeve: they could include actual hardware inside the cart that the game code could make use of. It was more expensive but if you expected to sell a boatload of copies, it could be worth it. However,…

imagine thinking lookup tables are innovative

Re: How do computers calculate sine?

#155

Post by jxy »

anthk wrote: post #146
jxy wrote: post #23

It's much clearer if you read one of the source code of the libm. Plan 9: https://9p.io/sources/plan9/sys/src/libc/port/sin.c Freebsd: https://cgit.freebsd.org/src/tree/lib/msun/src/k_sin.c

Does 9front keep the same sin.c implementation?

http://git.9front.org/plan9front/plan9front/HEAD/sys/src/lib...

Re: How do computers calculate sine?

#156

Post by jxy »

planede wrote: post #142
jxy wrote: post #23

It's much clearer if you read one of the source code of the libm. Plan 9: https://9p.io/sources/plan9/sys/src/libc/port/sin.c Freebsd: https://cgit.freebsd.org/src/tree/lib/msun/src/k_sin.c

Ah, I always referred to the musl implmenetation, but I just now realized that they copied the Freebsd one.

it says "Copyright (C) 1993 by Sun Microsystems, Inc. All rights reserved."

and the directory name is literally: `msun`

Re: How do computers calculate sine?

#157

Post by olooney »

eh_why_not wrote: post #90

Anyone experienced with the Remez algorithm mentioned at the end of the article? The degree-9 polynomial, said to be a thousand times better than the original Taylor approximation in maximum error, also appears to be very close to the Taylor series in the first place. Rounding the Taylor coefficients to 6 digits after the decimal: 1/3! = 0.166667 1/5! = 0.008333 1/7! = 0.000198 1/9! = 0.000027(56) The first 2 are exa…

I don't think the polynomial given in the article was calculated via Remez. Perhaps the author merely meant it as an illustration. Here is Wolfram Alpha plotting the error of equation from the article:

https://www.wolframalpha.com/input?i=plot+sin%28x%29+-+P%28x....

You'll note that the error is small near zero, and large near pi/4, which is characteristic of a Taylor series around zero, and not the characteristic "level" oscillation characteristic of Remez approximations[1]. Note also that the polynomial only includes odd terms, which is not something I would expect from Remez unless it was run on the symmetric interval [-pi/4, pi/4].

I ran Remez for the problem and after 4 iterations obtained a degree 8 polynomial with error less than 1e-9, but it didn't look anything like the polynomial given in the article.

    1.7209863008943345e-05x^8 -0.00024575124459624625x^7 +7.194649190849227e-05x^6 +0.008268794893899754x^5 +3.425379759410762e-05x^4 -0.16667692317020713x^3 +1.5422400957890642e-06x^2 +0.9999999106213322x +8.526477071446453e-10
Although of course the first few digits of the low-order matching terms will be very similar - any polynomial approximation method will agree there because they are fitting the same function, after all. But by the time we reach x^5 or x^7 the agreement is very loose, really only the first couple digits are the same.

[1]: https://en.wikipedia.org/wiki/Approximation_theory

Re: How do computers calculate sine?

#158

Post by jacobolus »

dzaima wrote: post #98
jacobolus wrote: post #69

Earlier quoted context omitted.

My understanding is that most software always uses some software implementation of sine, rather than calling a hardware instruction. Which is definitely what you should do if you care about getting the exact same results across platforms.

Software implementations can and do differ (even dynamically) based on the hardware though - e.g. glibc's sin(x) function, what C code will end up using (if not other languages relying on the C stdlib), uses FMA instructions on my CPU, and thus the exact same binary on the exact same OS with the exact same glibc should behave differently on a very old CPU without FMA where it should have a different implementation (a…

Yeah, the lack of FMA in some contexts is a serious bummer. It would be great if every popular CPU platform would figure out a way to get FMA implemented, and if programming languages would figure out better ways to help programmers use it explicitly without making their code too ugly.

Re: How do computers calculate sine?

#159

Post by lupire »

t-3 wrote: post #5

Link doesn't appear to be valid, but aren't these usually precalculated and stored in a lookup table?

Think about how big that lookup table would be for an 64bit double float.

They use a lookup table for nπ/16, and then a polynomial to approximate the difference to other values.

Re: How do computers calculate sine?

#160

Post by eh_why_not »

olooney wrote: post #157
eh_why_not wrote: post #90

Anyone experienced with the Remez algorithm mentioned at the end of the article? The degree-9 polynomial, said to be a thousand times better than the original Taylor approximation in maximum error, also appears to be very close to the Taylor series in the first place. Rounding the Taylor coefficients to 6 digits after the decimal: 1/3! = 0.166667 1/5! = 0.008333 1/7! = 0.000198 1/9! = 0.000027(56) The first 2 are exa…

I don't think the polynomial given in the article was calculated via Remez. Perhaps the author merely meant it as an illustration. Here is Wolfram Alpha plotting the error of equation from the article: https://www.wolframalpha.com/input?i=plot+sin%28x%29+-+P%28x... . You'll note that the error is small near zero, and large near pi/4, which is characteristic of a Taylor series around zero, and not the characteristic "…

> Perhaps the author merely meant it as an illustration.

Yes I too was expecting oscillations (since I saw Chebyshev polynomials mentioned on the wiki page). I'm beginning to think that the word "might" in their statement "One way to calculate is Remez’s algorithm. The results might look like this:" is doing a lot of heavy lifting.

A couple of notes about your results:

- The interval only needs to be [0, pi/16] and not [0, pi/4]; adjusting that in your wolframalpha query yields a similar bound to what the author lists: 3.5 e-9. (Although same observation about the change of behavior at the bounds as you made).

- The polynomial you obtained actually looks pretty close to the Taylor one: the even coefficients are small, and rounding to 5 or 6 digits might yield a close one, maybe if we look for a degree 9 polynomial instead of degree 8. (I don't have an implementation of Remez handy right now to try it myself).

> Although of course the first few digits of the low-order matching terms will be very similar

Makes sense.

Post reply on HN