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

101–110 of 167 posts

Re: How do computers calculate sine?

#101

Post by Someone »

demondemidi wrote: post #87

I thought modern CPUs since the late 1980's used a lookup table for trig/transcendental functions. Is the LUT just an expansion of the polynomial? I never really understood how FPUs worked...

That would take way too much room. A full lookup table would have 2^64 entries of 64 bits each, at 2^70 bits of ROM.

For comparison:

- Apple’s M2 Ultra has about 134 billion transistors. That’s about 2^38.

- Avogadro’s number is about 2^79.

Reducing the argument to a small range around zero decreases that a lot, but not enough by a far stretch. There are 2^52 doubles in [0.5, 1.0), 2^52 more in [0.25, 0.5], 2^52 more in [0.125, 0.25], etc. so you’d still easily need 2^52 entries or 2^58 bits (likely way, way more)

Re: How do computers calculate sine?

#102

Post by lifthrasiir »

demondemidi wrote: post #87

I thought modern CPUs since the late 1980's used a lookup table for trig/transcendental functions. Is the LUT just an expansion of the polynomial? I never really understood how FPUs worked...

Older CPUs generally have used CORDIC (which does use LUT but that's only a part of the algorithm) due to its simplicity and compactness, while later CPUs with extensive microcode support would do the same thing as software implementations.

Re: How do computers calculate sine?

#103

Post by stephencanon »

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…

https://en.wikipedia.org/wiki/Remez_algorithm

It’s a very simple iterative algorithm, essentially the dumbest thing that could possibly work (like most good algorithms). It fails to converge for functions that have poles nearby unless you have a very good initial guess (the Chebyshev or Carathéodory-Fejér approximants are ~always good starting points and easily computed). In practice you want to optimize a weighted L-inf norm rather than absolute, because floating-point errors are measured in a relative norm.

Re: How do computers calculate sine?

#104

Post by simonblack »

The same way you can eat an elephant: one byte at a time.

Any calculating job can be undertaken by a proper Turing machine. You just have to keep in mind the old triangle of usage: Cost, capability and speed.

If a human can calculate a sine, so can any full-blown computer.

Re: How do computers calculate sine?

#105

Post by demondemidi »

Someone wrote: post #101
demondemidi wrote: post #87

I thought modern CPUs since the late 1980's used a lookup table for trig/transcendental functions. Is the LUT just an expansion of the polynomial? I never really understood how FPUs worked...

That would take way too much room. A full lookup table would have 2^64 entries of 64 bits each, at 2^70 bits of ROM. For comparison: - Apple’s M2 Ultra has about 134 billion transistors. That’s about 2^38. - Avogadro’s number is about 2^79. Reducing the argument to a small range around zero decreases that a lot, but not enough by a far stretch. There are 2^52 doubles in [0.5, 1.0), 2^52 more in [0.25, 0.5], 2^52 more…

They DO use a lookup table because that’s what the FDIV but came from:

https://en.m.wikipedia.org/wiki/Pentium_FDIV_bug

“It is implemented using a programmable logic array with 2,048 cells, of which 1,066 cells should have been populated with one of five values: −2, −1, 0, +1, +2.”

Not sure what you’re trying to demonstrate, they wouldn’t store every single float!! I hope don’t program. ;)

Re: How do computers calculate sine?

#106

Post by Arelius »

warpech wrote: post #10

This made me realize that trigonometric functions are not deterministic across different CPU architectures, OS, and programming languages (floating point precision aside). E.g. I would assume that Math.sin(x) returns the same thing in NodeJS on Windows and Mac/M1, but it turns out it is necessarily so. https://stackoverflow.com/questions/74074312/standard-math-f...

Yeah, but you'd be surprised at how frequently they appear to be the same. I once worked on a HTML5 game that that relied on deterministic simulation for networking. And it wasn't untill pretty late in development that a build of Chrome shipped on some platform that finally triggered a desync in our extensive cross-platform test suite.

We implemented a deterministic approximation, and moved on. But I learned something important about trig functions that day.

Re: How do computers calculate sine?

#107

Post by pillusmany »

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

Games targetting pre-Pentium PCs also used precomputed trig tables.

Pentium was fast enough that it didn't matter as much.

Just a few years later it was slower to read a trig precomputed table.

Re: How do computers calculate sine?

#108

Post by mettamage »

What’s the best way to calculate it by hand?

I’m brushing up my math basics (I graduated CS while dodging the math requirements) and it frustrates me that in trig I need to remember values at all. The values such as sqrt(2)/2 make sense but how hard is it to calculate sin(5 degrees) by hand?

Re: How do computers calculate sine?

#109

Post by zgs »

paulpauper wrote: post #2

sine is easy because the series is globally convergent and fast converging

It would also be extremely inaccurate. The x^n numerators grow very quickly and digits get lost because unlimited precision isn't available. Likewise, the n! denominators also grow rapidly. Then the series is alternating which means cancellation is happening for every added term.

If you don't believe me try for x=10.

Re: How do computers calculate sine?

#110

Post by HenryPrickett »

mettamage wrote: post #108

What’s the best way to calculate it by hand? I’m brushing up my math basics (I graduated CS while dodging the math requirements) and it frustrates me that in trig I need to remember values at all. The values such as sqrt(2)/2 make sense but how hard is it to calculate sin(5 degrees) by hand?

Use a Taylor series with a four function calculator.

0 is a decent approximation of sin near 0.

x is a better one.

x - x^3/6 is an even better one.

x - x^3/6 + x^5/120 ...

Note that x here is in radians rather than degrees so convert (degrees * pi/180) first. Repeat until you're satisfied with how many stable digits you get

Post reply on HN