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

81–90 of 167 posts

Re: How do computers calculate sine?

#81

Post by throwway120385 »

TylerE wrote: post #16
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...

Safer to assume that floats are never deterministic.

It depends. If you're constrained to one chip and one platform you can characterize or you can estimate the characteristics of a float that matter in your application. In some applications like embedded that's actually totally fine, and modern embedded chips can often do floating point as fast or faster than they can emulate fixed point to work around floating point's drawbacks. On one project I worked on they originally wrote everything fixed point out of fear that floating point would introduce some deleterious effect. But in the end they rewrote parts of the project using floating point to no ill effect and great performance improvement. And there were features of the product that they had to strike because the rewrite needed to support them couldn't touch certain sensitive areas of the code that had been tested extensively in the 2 or 3 years of development. It would have been much better to evaluate the assumption that floats are bad early on in the project and make the decision based on real information. The heuristic they were applying ended up costing part of the product that was strategically important.

Re: How do computers calculate sine?

#82

Post by adgjlsfhk1 »

f1shy wrote: post #48
adgjlsfhk1 wrote: post #15

Earlier quoted context omitted.

no it's not. cordic has awful convergence of 1 bit per iteration. pretty much everyone uses power series.

That is 64 iterations for a double, that is nothing!

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

Re: How do computers calculate sine?

#83

Post by rcxdude »

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…

CORDIC doesn't make sense if multiplies have a similar cost to adds. If you have cheap multiplications then a successive approximation is faster. If multiplications are expensive relative to adds then CORDIC can still generally win. Basically this is only the case nowadays if you are doing ASICs or FPGAs.

Re: How do computers calculate sine?

#84

Post by rcxdude »

adgjlsfhk1 wrote: post #82
f1shy wrote: post #48

Earlier quoted context omitted.

That is 64 iterations for a double, that is nothing!

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.

Re: How do computers calculate sine?

#85

Post by Jyaif »

throwway120385 wrote: post #81
TylerE wrote: post #16

Earlier quoted context omitted.

Safer to assume that floats are never deterministic.

It depends. If you're constrained to one chip and one platform you can characterize or you can estimate the characteristics of a float that matter in your application. In some applications like embedded that's actually totally fine, and modern embedded chips can often do floating point as fast or faster than they can emulate fixed point to work around floating point's drawbacks. On one project I worked on they origin…

> constrained to one chip and one platform

and constrained to one compiler at a precise version, and one set of compiler options

Re: How do computers calculate sine?

#86

Post by ducttapecrown »

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.

They're always deterministic, just as long as physics is.

Re: How do computers calculate sine?

#88

Post by lifthrasiir »

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…

True in general, almost false for binary64. Important univariate functions have been thoroughly mapped for known hard-to-round cases, which resulted in the fact that we only need at most triple-double format to do the correct rounding. (Bivariate functions like `pow` are much harder, and not yet fully mapped as of this writing.) As a result we now have a mathematical library that almost ensures correct rounding [1], and a further optimization is currently in progress.

[1] https://core-math.gitlabpages.inria.fr/

Re: How do computers calculate sine?

#89

Post by lifthrasiir »

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

FreeBSD code is missing the range reduction step (it's named a "kernel" for the reason): https://cgit.freebsd.org/src/tree/lib/msun/src/e_rem_pio2.c

Re: How do computers calculate sine?

#90

Post by eh_why_not »

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 exact, the third is 5 digits only (so 0.000190), and the fourth is more different starting from the 6th digit (0.000026019).

The delta in the 9-th order is expected if you were to truncate the Taylor series starting from the 11th order to infinity (+ x^11 / 11! - x^13/13! ...).

Post reply on HN