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

121–130 of 167 posts

Re: How do computers calculate sine?

#121

Post by mads »

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.

Re: How do computers calculate sine?

#122

Post by idatum »

perihelions wrote: post #19
vardump wrote: post #13

CORDIC is how it's usually done in hardware (and FPGAs). https://en.wikipedia.org/wiki/CORDIC

CORDIC is pretty obsolete, AFAIK. Its advantage is that its hardware requirements are absolutely tiny: two (?) accumulator registers, and hardware adders and shift-ers—I think that's all. No multiplication needed, in particular. Very convenient if you're building things from discrete transistors , like the some of those earlier scientific calculators! (Also has a nice property, apparently, that CORDIC-like routines e…

I just recently came across CORDIC in a fun read I just finished, 'Empire of the Sum', by Keith Houston. It's a history of calculators, and there's a chapter on the HP-35 which used CORDIC. The author goes into some details how it was used by that constrained device.

There are a lot of references given in the book including more details on CORDIC.

Re: How do computers calculate sine?

#123

Post by inkyoto »

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

> […] 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.

Re: How do computers calculate sine?

#124

Post by aidenn0 »

jacobolus wrote: post #63
TylerE wrote: post #53

Earlier quoted context omitted.

It’s not that I don’t understand, it’s that I do. Floats are inherently lossy representations. Yes, this means the more operations you perform on a float input, the fuzzier the value is.You ignore that harsh reality at your peril. If you find engineering rigor sad, I don’t know what to tell you.

> the more operations you perform on a float input, the fuzzier the value is No, any float always precisely represents a specific number. The issue is that only a finite number of numbers are representable. Some algorithms are poorly conditioned and when implemented using floating point arithmetic will lead to a result that is different than what you would get in idealized real number arithmetic. That doesn't make an…

> No, any float always precisely represents a specific number. The issue is that only a finite number of numbers are representable.

A float always precisely represents a specific number, but that number is not always precisely the equal to the algebraic result of the operations performed (even when ignoring transcendental and irrational functions). This should be obvious since there is no limit to rational numbers, but finite floating point numbers.

If you design your algorithms very carefully, you can end up with the ratio of the output of your algorithm to the ratio of the algebraic result close to unity over a wide domain of inputs.

Re: How do computers calculate sine?

#125

Post by aidenn0 »

deepthaw wrote: post #41

Ignorant question: Given the ridiculous number of transistors and so on we can use in CPUs and GPUs nowadays how feasible is a relatively huge trig lookup table burned into rom?

A lookup table (for any function) that covered all values between 0 and 1 in single precision, would be ~4GB; there are approximately 1B values between 0 and 1, and the result of each value is 4 bytes.

Such a table for double-precision would be much, much larger.

Re: How do computers calculate sine?

#126

Post by aidenn0 »

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

TFA says they use a 32 entry LUT, then do some math on the result.

Re: How do computers calculate sine?

#127

Post by fulafel »

cogman10 wrote: post #20
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...

Well, what's fun is that (AFAIK) trigonometric functions tend not to be implemented in the newer floating point instructions, such as AVX or SSE. So while what you say is true about the x87 implementation of those functions, for anything targeting a machine built in the last 20 years it's likely the code will run consistently regardless the architecture (barring architecture floating point bugs, which aren't terribly…

What about GPU ISAs?

Re: How do computers calculate sine?

#128

Post by hakuseki »

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

> However, even using extra hardware wasn't enough in this case. So they pre-calculated lookup tables for sine, cosine, tangent etc. for every angle at the necessary precision.

Is this really the order of events? I imagine the pre-calculated route is what you'd try first, and only go for extra hardware if that failed somehow.

Re: How do computers calculate sine?

#129

Post by shzhdbi09gv8ioi »

hakuseki wrote: post #128
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,…

> However, even using extra hardware wasn't enough in this case. So they pre-calculated lookup tables for sine, cosine, tangent etc. for every angle at the necessary precision. Is this really the order of events? I imagine the pre-calculated route is what you'd try first, and only go for extra hardware if that failed somehow.

Lookup tables were commonplace in 80s-90s graphics programming. It should have been used before any consideration of custom hardware solutions.

Re: How do computers calculate sine?

#130

Post by otabdeveloper4 »

saagarjha wrote: post #43
TylerE wrote: post #16

Earlier quoted context omitted.

Safer to assume that floats are never deterministic.

This is not always a safe assumption (in certain scenarios floating point results being nondeterministic has the possibility to introduce bugs and security issues) and is also a kind of sad way to look at the world. The response to "I don't understand how this works" should not be to adopt an incorrect viewpoint, but to know the limitations of your understanding.

Irrational numbers cannot have an exact representation in digital bits. (Computers use rational numbers with modular arithmetic under the hood.)
Post reply on HN