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

91–100 of 167 posts

Re: How do computers calculate sine?

#91

Post by kens »

mhh__ wrote: post #73
TylerE wrote: post #16

Earlier quoted context omitted.

Safer to assume that floats are never deterministic.

They're always deterministic in some sense (and as long as your OS respects the rounding mode after a context switch properly). This might sound pedantic but it determines how we think about floats — the behaviour is specified quite exactly.

Curiously, early Intel 386 processors had a bug where 32-bit multiplies were genuinely nondeterministic: some answers would depend on the voltage, frequency, temperature, and manufacturing conditions. The problem was essentially analog, a layout issue, where the signal didn't always have enough margin. (This is unrelated to the famous Pentium FDIV bug.) Until Intel got the problem fixed, they would stamp bad chips with "16 BIT S/W ONLY", while good chips were labeled "ΣΣ".

Re: How do computers calculate sine?

#92

Post by quickthrower2 »

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

So you can use sin(x) for various x to tell what you are running on. Maybe even in the browser?

Re: How do computers calculate sine?

#93

Post by lifthrasiir »

quickthrower2 wrote: post #92
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...

So you can use sin(x) for various x to tell what you are running on. Maybe even in the browser?

V8 and SpiderMonkey have converged to the same underlying library (fdlibm), partly for the interoperability, so you generally can't.

Re: How do computers calculate sine?

#94

Post by staplung »

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, 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. They were helped by the fact that the game resolution in this case was fairly low.

If you're interested, you can peruse the C code that was used to generate the tables. Here's the file for sine/cosine:

https://github.com/RandalLinden/DOOM-FX/blob/master/source/m...

Re: How do computers calculate sine?

#95

Post by Const-me »

rcxdude wrote: post #84
adgjlsfhk1 wrote: post #82

Earlier quoted context omitted.

53, but that's still a lot more than the 5th degree polynomial that you need.

yeah, but 52 adds can be a lot cheaper than a few multiplies, if you're making them out of shift registers and logic gates (or LUT). in a CPU or GPU, who cares, moving around the data is 100x more expensive than the ALU operation.

> in a CPU or GPU, who cares, moving around the data is 100x more expensive than the ALU operation

Moving data is indeed expensive, but there’s another reason to not care. Modern CPUs take same time to add or multiply floats.

For example, the computer I’m using, with AMD Zen3 CPU cores, takes 3 cycles to add or multiply numbers, which applies to both 32- and 64-bit flavors of floats. See addps, mulps, addpd, mulpd SSE instructions in that table: https://www.uops.info/table.html

Re: How do computers calculate sine?

#97

Post by phkahler »

convolvatron wrote: post #8

http://steve.hollasch.net/cgindex/math/inccos.html is a great technique if you need a fast integer approximation for some some arbitrary sampling interval (i.e. motor control)

I've been doing FoC motor control for a long time and I've settled on a neat little fixed point approximation for sin/cos. I haven't been able to find the blog I got the idea from. It's accurate to 9 bits, but is very symmetric and hits 1,0,-1 exactly. It's also smooth which usually makes it better than lookup tables.

Re: How do computers calculate sine?

#98

Post by dzaima »

jacobolus wrote: post #69
zokier wrote: post #67

Earlier quoted context omitted.

Point being that IEEE 754 defines two sets of operations, the required operations (section 5) that should be produce correctly rounded results to the last digit, and recommend operations (section 9) with relaxed requirements. And sine belongs to the latter section, so IEEE 754 does not mandate reproducible results for sine.

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 (as generally things using FMA cannot be exactly ported to hardware without it without a gigantic drop in performance which'd be extremely unacceptable).

Re: How do computers calculate sine?

#99

Post by adgjlsfhk1 »

rcxdude wrote: post #84
adgjlsfhk1 wrote: post #82

Earlier quoted context omitted.

53, but that's still a lot more than the 5th degree polynomial that you need.

yeah, but 52 adds can be a lot cheaper than a few multiplies, if you're making them out of shift registers and logic gates (or LUT). in a CPU or GPU, who cares, moving around the data is 100x more expensive than the ALU operation.

> moving around the data is 100x more expensive than the ALU operation.

This is exactly the problem with CORDIC. 52 dependent adds requires moving data from a register to the ALU and back 52 times.

Re: How do computers calculate sine?

#100

Post by throwawaymaths »

retrac wrote: post #56
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...

Rounding transcendentals correctly has unknown time and space complexity. [1] Sort of brushes up against the halting problem. With limited precision, the upper limit becomes calculable but it's rather large - packages that offer correct rounding on 64-bit floating point use potentially hundreds of bytes to deal with a single floating point value. Dedicated circuitry to implement it fast would be big and complicated e…

unknown time and space complexity

True in general but for the basic datatypes sent through hardware regusters your processor architecture has fixed precision. So the time and space complexity is O(1)

Post reply on HN