8 ms·

This made me realize that trigonometric functions are not deterministic across different CPU architectures, OS, and programming languages (floating point precis

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-functions-reproducibility-on-different-cpus https://stackoverflow.com/questions/74074312/standard-math-f...

TylerE 3y ago
Safer to assume that floats are never deterministic.
- jacobolus 3y ago
  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.)
  - zokier 3y ago
    But transcendentals like sine are not part of the strictly defined basic arithmetic; they are intentionally defined with relaxed behavior.
    - gpderetta 3y ago
      Even there many standard libraries provide very good precision at least within sane domain.
      - TylerE 3y ago
        Yeah, that’s kind of my point. 99% consistent isn’t.
    - jacobolus 3y ago
      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.
      - zokier 3y ago
        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.
        jacobolus 3y ago
        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.
        dzaima 3y ago
        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).
        jacobolus 3y ago
        Yeah, the lack of FMA in some contexts is a serious bummer. It would be great if every popular CPU platform would figure out a way to get FMA implemented, and if programming languages would figure out better ways to help programmers use it explicitly without making their code too ugly.
- aardvark179 3y ago
  Floats are well defined, and it is perfectly possible to reason about how algorithms based on them should behave. Few languages specify the accuracy of things like trig functions, so relying on them can be tricky, and JavaScript is particularly bad in that respect.
- saagarjha 3y ago
  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.
  - otabdeveloper4 3y ago
    Irrational numbers cannot have an exact representation in digital bits. (Computers use rational numbers with modular arithmetic under the hood.)
    - saagarjha 3y ago
      Yes I am aware of this fact
  - TylerE 3y ago
    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.
    - saagarjha 3y ago
      "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.
      - TylerE 3y ago
        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.
- mhh__ 3y ago
  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.
  - TylerE 3y ago
    What I mean is that the same code running on different hardware/os may not always give the same answer. It’ll be close, but you can’t always expect bit for bit identical.
  - ducttapecrown 3y ago
    They're always deterministic, just as long as physics is.
  - kens 3y ago
    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 "ΣΣ".
- contravariant 3y ago
  I don't think that's safe at all. Catastrophic cancellation would be quite a lot less catastrophic if rounding errors were random but accurate on average.
- throwway120385 3y ago
  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.
  - Jyaif 3y ago
    > constrained to one chip and one platform and constrained to one compiler at a precise version, and one set of compiler options
- charlieyu1 3y ago
  But why? We all know 0.1+0.2 won’t give 0.3 with floats but at least we should expect deterministic result for same numbers and same operations and same order, no?
adgjlsfhk1 3y ago
some languages (e.g. Julia) provide their own math library do that you get the same results across across operating systems.
cogman10 3y ago
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 uncommon in the less significant bits and when overclocking comes into play). x86 compilers won't use x87 instructions when SSE2 and later are available. x87 is just a really weird and funky instruction set that's best left in the gutter of history.
- deleted 3y ago
  [deleted]
- bnprks 3y ago
  Sadly even SSE vs. AVX is enough to often give different results, as SSE doesn't have support for fused multiply-add instructions which allow calculation of a*b + c with guaranteed correct rounding. Even though this should allow CPUs from 2013 and later to all use FMA, gcc/clang don't enable AVX by default for the x86-64 targets. And even if they did, results are only guaranteed identical if implementations have chosen the exact same polynomial approximation method and no compiler optimizations alter the instruction sequence. Unfortunately, floating point results will probably continue to differ across platforms for the foreseeable future.
  - cogman10 3y ago
    That's a bit of a different problem IMO. Barring someone doing a "check if AVX is available" check inside their code, binaries are generally compiled targeting either SSE or AVX and not both. You can reasonably expect that the same binary thrown against multiple architectures will have the same output. This, of course, doesn't apply if we are talking about a JIT. All bets are off if you are talking about javascript or the JVM. That is to say, you can expect that a C++ binary blob from the Ubuntu repo is going to get the same numbers regardless the machine since they generally will target fairly old architectures.
aardvark179 3y ago
Somewhat annoyingly the ascribe standard only specifies that various math functions return an approximation but does not set any bounds on that approximation. So for many functions you could just return NaN and still be compliant.
- layer8 3y ago
  Isn’t NaN the one value that can’t possibly count as an approximation, because it’s not a number and unordered? ;)
  - aardvark179 3y ago
    You might think so, but if it’s not specified in the standard…
    - zardo 3y ago
      It is the worst possible approximation though.
    - layer8 3y ago
      I was submitting an interpretation of the standard.
deleted 3y ago
[deleted]
retrac 3y ago
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 even by today's standards. https://en.wikipedia.org/wiki/Rounding#Table-maker's_dilemma https://en.wikipedia.org/wiki/Rounding#Table-maker's_dilemma
- ImHereToVote 3y ago
  We should just use analog circuit for this sort of thing where the exact precision doesn't matter.
- lifthrasiir 3y ago
  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/ https://core-math.gitlabpages.inria.fr/
- throwawaymaths 3y ago
  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)
quickthrower2 3y ago
So you can use sin(x) for various x to tell what you are running on. Maybe even in the browser?
- Karliss 3y ago
  There is a shader which uses similar idea to detect what kind of GPU you have https://www.shadertoy.com/view/slySWV https://www.shadertoy.com/view/slySWV
- lifthrasiir 3y ago
  V8 and SpiderMonkey have converged to the same underlying library (fdlibm), partly for the interoperability, so you generally can't.
Arelius 3y ago
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.
paulddraper 3y ago
> deterministic I would use the word "consistent." Non-determinism implies randomness.

TylerE 3y ago

Safer to assume that floats are never deterministic.

jacobolus 3y ago
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.)
- zokier 3y ago
  But transcendentals like sine are not part of the strictly defined basic arithmetic; they are intentionally defined with relaxed behavior.
  - gpderetta 3y ago
    Even there many standard libraries provide very good precision at least within sane domain.
    - TylerE 3y ago
      Yeah, that’s kind of my point. 99% consistent isn’t.
  - jacobolus 3y ago
    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.
    - zokier 3y ago
      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.
      - jacobolus 3y ago
        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.
        dzaima 3y ago
        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).
        jacobolus 3y ago
        Yeah, the lack of FMA in some contexts is a serious bummer. It would be great if every popular CPU platform would figure out a way to get FMA implemented, and if programming languages would figure out better ways to help programmers use it explicitly without making their code too ugly.
aardvark179 3y ago
Floats are well defined, and it is perfectly possible to reason about how algorithms based on them should behave. Few languages specify the accuracy of things like trig functions, so relying on them can be tricky, and JavaScript is particularly bad in that respect.
saagarjha 3y ago
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.
- otabdeveloper4 3y ago
  Irrational numbers cannot have an exact representation in digital bits. (Computers use rational numbers with modular arithmetic under the hood.)
  - saagarjha 3y ago
    Yes I am aware of this fact
- TylerE 3y ago
  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.
  - saagarjha 3y ago
    "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.
    - TylerE 3y ago
      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.
mhh__ 3y ago
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.
- TylerE 3y ago
  What I mean is that the same code running on different hardware/os may not always give the same answer. It’ll be close, but you can’t always expect bit for bit identical.
- ducttapecrown 3y ago
  They're always deterministic, just as long as physics is.
- kens 3y ago
  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 "ΣΣ".
contravariant 3y ago
I don't think that's safe at all. Catastrophic cancellation would be quite a lot less catastrophic if rounding errors were random but accurate on average.
throwway120385 3y ago
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.
- Jyaif 3y ago
  > constrained to one chip and one platform and constrained to one compiler at a precise version, and one set of compiler options
charlieyu1 3y ago
But why? We all know 0.1+0.2 won’t give 0.3 with floats but at least we should expect deterministic result for same numbers and same operations and same order, no?

adgjlsfhk1 3y ago

some languages (e.g. Julia) provide their own math library do that you get the same results across across operating systems.

cogman10 3y ago

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 uncommon in the less significant bits and when overclocking comes into play). x86 compilers won't use x87 instructions when SSE2 and later are available. x87 is just a really weird and funky instruction set that's best left in the gutter of history.

deleted 3y ago
[deleted]
bnprks 3y ago
Sadly even SSE vs. AVX is enough to often give different results, as SSE doesn't have support for fused multiply-add instructions which allow calculation of a*b + c with guaranteed correct rounding. Even though this should allow CPUs from 2013 and later to all use FMA, gcc/clang don't enable AVX by default for the x86-64 targets. And even if they did, results are only guaranteed identical if implementations have chosen the exact same polynomial approximation method and no compiler optimizations alter the instruction sequence. Unfortunately, floating point results will probably continue to differ across platforms for the foreseeable future.
- cogman10 3y ago
  That's a bit of a different problem IMO. Barring someone doing a "check if AVX is available" check inside their code, binaries are generally compiled targeting either SSE or AVX and not both. You can reasonably expect that the same binary thrown against multiple architectures will have the same output. This, of course, doesn't apply if we are talking about a JIT. All bets are off if you are talking about javascript or the JVM. That is to say, you can expect that a C++ binary blob from the Ubuntu repo is going to get the same numbers regardless the machine since they generally will target fairly old architectures.

aardvark179 3y ago

Somewhat annoyingly the ascribe standard only specifies that various math functions return an approximation but does not set any bounds on that approximation. So for many functions you could just return NaN and still be compliant.

layer8 3y ago
Isn’t NaN the one value that can’t possibly count as an approximation, because it’s not a number and unordered? ;)
- aardvark179 3y ago
  You might think so, but if it’s not specified in the standard…
  - zardo 3y ago
    It is the worst possible approximation though.
  - layer8 3y ago
    I was submitting an interpretation of the standard.

deleted 3y ago

[deleted]

retrac 3y ago

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 even by today's standards. https://en.wikipedia.org/wiki/Rounding#Table-maker's_dilemma https://en.wikipedia.org/wiki/Rounding#Table-maker's_dilemma

ImHereToVote 3y ago
We should just use analog circuit for this sort of thing where the exact precision doesn't matter.
lifthrasiir 3y ago
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/ https://core-math.gitlabpages.inria.fr/
throwawaymaths 3y ago
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)

quickthrower2 3y ago

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

Karliss 3y ago
There is a shader which uses similar idea to detect what kind of GPU you have https://www.shadertoy.com/view/slySWV https://www.shadertoy.com/view/slySWV
lifthrasiir 3y ago
V8 and SpiderMonkey have converged to the same underlying library (fdlibm), partly for the interoperability, so you generally can't.

Arelius 3y ago

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.

paulddraper 3y ago

> deterministic I would use the word "consistent." Non-determinism implies randomness.