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

61–70 of 167 posts

Re: How do computers calculate sine?

#61

Post by TylerE »

saagarjha wrote: post #58
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.

"Floats are not deterministic" is not engineering rigor, it's just wrong. They are specified precisely by IEEE-754 in how they must behave and which operations are allowed to produce which results.

IEEE 754 conforming floats conform to IEEE-754. If they actually conform. Low end devices with shitty software implementations often get the hard edge cases wrong.

Re: How do computers calculate sine?

#62

Post by saagarjha »

TylerE wrote: post #61
saagarjha wrote: post #58

Earlier quoted context omitted.

"Floats are not deterministic" is not engineering rigor, it's just wrong. They are specified precisely by IEEE-754 in how they must behave and which operations are allowed to produce which results.

IEEE 754 conforming floats conform to IEEE-754. If they actually conform. Low end devices with shitty software implementations often get the hard edge cases wrong.

Yes and when that happens it is important to know what went wrong rather than just handwaving "oh it's that float stuff again I can't trust it".

Re: How do computers calculate sine?

#63

Post by jacobolus »

TylerE wrote: post #53
saagarjha wrote: post #43

Earlier quoted context omitted.

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.

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 any floating point value "fuzzy".

Re: How do computers calculate sine?

#64

Post by jacobolus »

zokier wrote: post #32
jacobolus wrote: post #25

Earlier quoted context omitted.

Floats follow a clear specification which determines precisely how basic arithmetic should work. They should work the same on all popular modern platforms. (Whether specific software libraries are the same is a separate question.)

But transcendentals like sine are not part of the strictly defined basic arithmetic; they are intentionally defined with relaxed behavior.

If you implement sine in software using the same sequence of basic arithmetic instructions, the result should be the same across platforms. If you make two different implementations using different arithmetic, then of course you can't rely on them being the same.

Re: How do computers calculate sine?

#65

Post by gpderetta »

zokier wrote: post #38
gpderetta wrote: post #35

Earlier quoted context omitted.

GCC won't use FMA without fast-math though. Even when AVX is otherwise enabled.

Sure it will: > -ffp-contract=fast enables floating-point expression contraction such as forming of fused multiply-add operations if the target has native support for them > The default is -ffp-contract=off for C in a standards compliant mode (-std=c11 or similar), -ffp-contract=fast otherwise. https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html#ind...

Oh, wow, forgot about fp-contract. It says it is off in C by default, what about C++?

Re: How do computers calculate sine?

#66

Post by bigbillheck »

vardump wrote: post #47
bigbillheck wrote: post #44

Earlier quoted context omitted.

Why would you ever use CORDIC if you had any other option?

It's great for hardware implementations, because it's simple and you get good/excellent accuracy. I wouldn't be surprised if that's still how modern x86-64 CPUs compute sin, cos, etc. That said, last time I had to do that in software, I used Taylor series. Might not have been an optimal solution. EDIT: AMD's Zen 4 takes 50-200 cycles (latency) to compute sine. I think that strongly suggests AMD uses CORDIC. https://w…

They switched away from CORDIC at one point: https://www.intel.com/content/www/us/en/developer/articles/t...

(there doesn't seem to actually be a linked article there, just the summary)

Re: How do computers calculate sine?

#67

Post by zokier »

jacobolus wrote: post #64
zokier wrote: post #32

Earlier quoted context omitted.

But transcendentals like sine are not part of the strictly defined basic arithmetic; they are intentionally defined with relaxed behavior.

If you implement sine in software using the same sequence of basic arithmetic instructions, the result should be the same across platforms. If you make two different implementations using different arithmetic, then of course you can't rely on them being the same.

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.

Re: How do computers calculate sine?

#68

Post by zokier »

gpderetta wrote: post #65
zokier wrote: post #38

Earlier quoted context omitted.

Sure it will: > -ffp-contract=fast enables floating-point expression contraction such as forming of fused multiply-add operations if the target has native support for them > The default is -ffp-contract=off for C in a standards compliant mode (-std=c11 or similar), -ffp-contract=fast otherwise. https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html#ind...

Oh, wow, forgot about fp-contract. It says it is off in C by default, what about C++?

Read closer, it defaults to fast, not off

Re: How do computers calculate sine?

#69

Post by jacobolus »

zokier wrote: post #67
jacobolus wrote: post #64

Earlier quoted context omitted.

If you implement sine in software using the same sequence of basic arithmetic instructions, the result should be the same across platforms. If you make two different implementations using different arithmetic, then of course you can't rely on them being the same.

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.

Re: How do computers calculate sine?

#70

Post by vardump »

bigbillheck wrote: post #66
vardump wrote: post #47

Earlier quoted context omitted.

It's great for hardware implementations, because it's simple and you get good/excellent accuracy. I wouldn't be surprised if that's still how modern x86-64 CPUs compute sin, cos, etc. That said, last time I had to do that in software, I used Taylor series. Might not have been an optimal solution. EDIT: AMD's Zen 4 takes 50-200 cycles (latency) to compute sine. I think that strongly suggests AMD uses CORDIC. https://w…

They switched away from CORDIC at one point: https://www.intel.com/content/www/us/en/developer/articles/t... (there doesn't seem to actually be a linked article there, just the summary)

Pretty weird Intel's sine computation latency hasn't changed all that much over the years. Latencies have been pretty similar for 20 years.

EDIT: That's a paper for a software library, not the CPU's internal implementation. Which is probably still done with CORDIC.

Post reply on HN