7 ms·

Intel Underestimates Error Bounds by 1.3 quintillion (2014)

175 points by sgillen 8y ago

faragon 8y ago
Take attention to the "References" section (including references to Linus Torvalds messages in the GCC mail list, some bugs related to this issue, etc.)
- acqq 8y ago
  Yes. It obviously shows where Linus steps out of the bounds in which he is an expert. He blindly believes Intel's false documentation as early as 2001, and, if I understood correctly, the result is that glibc has bad FP sin for quite a while, since the maintainers also don't try to check anything, and: - either there was no user who seriously used it (to detect the error) - or the user who seriously used the sin and detected the error didn't pass through the maintainers' "wall blocking the casual contributions" (a major maintainer for a few years was kind of legendary for being very dismissive and hard to communicate with). - or the detector of the error remained silent. It seems that Bruce was the first managing to induce the change in glibc, and he needed to reach Intel first for that. Linus being wrong in believing the documentation instead of checking it himself: https://gcc.gnu.org/ml/gcc/2001-08/msg00679.html https://gcc.gnu.org/ml/gcc/2001-08/msg00679.html I'm curious when Java fixed their bad assumptions: https://bugs.java.com/view_bug.do?bug_id=4306749 https://bugs.java.com/view_bug.do?bug_id=4306749 It seems much faster, as already in 2005 Gosling knew the truth: https://web.archive.org/web/20110812023545/https://blogs.oracle.com/jag/entry/transcendental_meditation https://web.archive.org/web/20110812023545/https://blogs.ora... "the x87 fsin/fcos use a particular approximation to pi, which effectively means the period of the function is changed, which can lead to large errors outside [-pi/4, pi/4]." "What we do in the JVM on x86 is moderately obvious: we range check the argument, and if it's outside the range [-pi/4, pi/4]we do the precise range reduction by hand, and then call fsin." Gosling actually quotes "Joe Darcy, our local Floating Point God." Joseph D. Darcy was also a co-author of: "How Java's Floating-Point Hurts Everyone Everywhere" with W. Kahan (http://www.eecs.berkeley.edu/~wkahan/JAVAhurt.pdf http://www.eecs.berkeley.edu/~wkahan/JAVAhurt.pdf) and his master thesis was: "Borneo: Adding IEEE 754 floating point support to Java" http://sonic.net/~jddarcy/Borneo/ http://sonic.net/~jddarcy/Borneo/ "a dialect of the Java language designed to have true support for the IEEE 754 floating point standard." "Unfortunately, Java's specification creates several problems for numerical computation" ... "useful IEEE 754 features are either explicitly forbidden or omitted from the Java specification."
  - IshKebab 8y ago
    To be fair he did say "assuming they don't have an fdiv-like bug ;)"
    - acqq 8y ago
      > he did say "assuming they don't have an fdiv-like bug The actual situation was not too similar: the instruction that should speed up the calculation and returning the correct bits in the specific range, actually behaves as intended, that is, the designers of the instruction assumed the users will know the limitation of it, that is, it was originally assumed that the users were supposed to know that the function is not the "general" one and the "bug" was just in the misleading documentation. By fdiv you've had an instruction that didn't behave as intended, being wrong for some very specific inputs and not only outside of the designed range.
  - brucedawson 8y ago
    > It seems that Bruce was the first managing to induce the change in glibc glibc changed their implementation before I reported on this.
inetknght 8y ago
What's that? Floating point math strikes again? /s Let's build something better.
- stealthcat 8y ago
  Need many years ahead for IEEE interval arithmetic hardware implementations to be usable... https://standards.ieee.org/findstds/standard/1788-2015.html https://standards.ieee.org/findstds/standard/1788-2015.html
  - bsder 8y ago
    Intervals in interval arithmetic can rapidly go to infinity even when the problem is relatively well behaved (in matrix inversion, for example) and standard floating point arithmetic produces a useful answer.
- AceJohnny2 8y ago
  IEEE 754 is one of the rare successes of computer engineering and standardization. Turns out it's just hard to implement continuous math on physical hardware. I'm curious (and a bit skeptical) about any efforts that think they can do better.
  - triska 8y ago
    John Gustafson has developed several promising alternatives, such as unums, posits and valids: https://posithub.org/about https://posithub.org/about I also recommend his book, The End of Error - Unum Computing: https://www.crcpress.com/The-End-of-Error-Unum-Computing/Gustafson/p/book/9781482239867 https://www.crcpress.com/The-End-of-Error-Unum-Computing/Gus... A transcript of a debate with William Kahan is here: http://www.johngustafson.net/pdfs/DebateTranscription.pdf http://www.johngustafson.net/pdfs/DebateTranscription.pdf
- kccqzy 8y ago
  What better thing do you have in mind? I'm not aware of any general-purpose floating point math replacement that mature enough to be embedded in billions of processors.
stilley2 8y ago
From 2014, FYI
- dang 8y ago
  Thanks, added.
jabl 8y ago
Worth noting this is for the x87 fsin instruction. For x86_64 typically a library function is called (which in turn uses SSE2 math instead of x87) rather than generating inline code.
- ajross 8y ago
  More "pervasively" than merely typically. The x87 registers still exist in a technical sense, but except for compatibility in legacy binaries those instructions are never used.
  - burfog 8y ago
    They are used by gcc on x86_64 Ubuntu when dealing with long double. I just tried it, with a trivial function that adds arguments and returns the resulting sum. I think this is true on any x86_64 platform for which sizeof(long double) exceeds 8.
    - ajross 8y ago
      Sure, because "long double" is fundamentally an x86-specific compiler extension[1] designed to exploit the 80 bit FPU precision in the 8087 architecture. Nothing for an SSE (or any other 64 bit IEEE FPU) will be using long double, except for compatibility. [1] Yeah, I think there's a software emulation layer to give you 128 bits on other platforms or somesuch. Again, not important nor relevant to a discussion abou FSIN.
- Joky 8y ago
  I’m puzzled by what you mean here: you refer to an x87 instruction, which makes me think it is assembly/binary level and then you’re saying that a library function is called. Where is the magic? Is there an x86 feature where you can instruct the CPU to jump to an address when a specific instruction is encountered? Or are you maybe using “library” for microcode in the CPU itself? Edit: or are you referring to fsin at the C language level (in which case the x87 is hard to relate)
  - 8y ago
bsder 8y ago
Um, it was known at least as far back as the AMD K5 (which has something like 300+ bits of Pi) that argument reduction on x86 didn't have enough bits of Pi.
- londons_explore 8y ago
  You need a lot of bits of pi if you want to have an even vaguely accurate result when you do sin(MAX_DOUBLE)
Dylan16807 8y ago
So is it wrong to me to interpret this as an imprecision of a partial ULP on the input number, thereby making the accuracy of the output just fine? Is there a use case for such a numerically unstable function use except as a party trick to get pi?
- brucedawson 8y ago
  The input number is, unavoidably, not a perfect representation of pi. However the fsin instruction's job is to calculate the sin of the actual input number, not try to guess what input was intended. So it doesn't make sense to interpret this as an imprecision of the input number - the fsin instruction failed to give a result which was as accurate as its documentation promised. The documentation has been fixed now. I don't know how often this actually matters, but it's worth nothing that library implementations of sin() don't use fsin anymore, and I think that is partially because of this flaw.
  - Dylan16807 8y ago
    > However the fsin instruction's job is to calculate the sin of the actual input number, not try to guess what input was intended. Not guessing what was 'intended', just treating a number like "1.234567" as "any number that could have rounded to 1.234567000, whatever is most convenient". Does it cause any practical problems to do this? How often do people actually expect/need a double to be treated as having infinite precision, rather than 53 bits or slightly more than 53 bits of precision?
aurelien 8y ago
"Not so much!" ~Intel motto
known 8y ago
Floating Point Math http://0.30000000000000004.com/ http://0.30000000000000004.com/

175 points by sgillen 8y ago

Take attention to the "References" section (including references to Linus Torvalds messages in the GCC mail list, some bugs related to this issue, etc.)

acqq 8y ago
Yes. It obviously shows where Linus steps out of the bounds in which he is an expert. He blindly believes Intel's false documentation as early as 2001, and, if I understood correctly, the result is that glibc has bad FP sin for quite a while, since the maintainers also don't try to check anything, and: - either there was no user who seriously used it (to detect the error) - or the user who seriously used the sin and detected the error didn't pass through the maintainers' "wall blocking the casual contributions" (a major maintainer for a few years was kind of legendary for being very dismissive and hard to communicate with). - or the detector of the error remained silent. It seems that Bruce was the first managing to induce the change in glibc, and he needed to reach Intel first for that. Linus being wrong in believing the documentation instead of checking it himself: https://gcc.gnu.org/ml/gcc/2001-08/msg00679.html https://gcc.gnu.org/ml/gcc/2001-08/msg00679.html I'm curious when Java fixed their bad assumptions: https://bugs.java.com/view_bug.do?bug_id=4306749 https://bugs.java.com/view_bug.do?bug_id=4306749 It seems much faster, as already in 2005 Gosling knew the truth: https://web.archive.org/web/20110812023545/https://blogs.oracle.com/jag/entry/transcendental_meditation https://web.archive.org/web/20110812023545/https://blogs.ora... "the x87 fsin/fcos use a particular approximation to pi, which effectively means the period of the function is changed, which can lead to large errors outside [-pi/4, pi/4]." "What we do in the JVM on x86 is moderately obvious: we range check the argument, and if it's outside the range [-pi/4, pi/4]we do the precise range reduction by hand, and then call fsin." Gosling actually quotes "Joe Darcy, our local Floating Point God." Joseph D. Darcy was also a co-author of: "How Java's Floating-Point Hurts Everyone Everywhere" with W. Kahan (http://www.eecs.berkeley.edu/~wkahan/JAVAhurt.pdf http://www.eecs.berkeley.edu/~wkahan/JAVAhurt.pdf) and his master thesis was: "Borneo: Adding IEEE 754 floating point support to Java" http://sonic.net/~jddarcy/Borneo/ http://sonic.net/~jddarcy/Borneo/ "a dialect of the Java language designed to have true support for the IEEE 754 floating point standard." "Unfortunately, Java's specification creates several problems for numerical computation" ... "useful IEEE 754 features are either explicitly forbidden or omitted from the Java specification."
- IshKebab 8y ago
  To be fair he did say "assuming they don't have an fdiv-like bug ;)"
  - acqq 8y ago
    > he did say "assuming they don't have an fdiv-like bug The actual situation was not too similar: the instruction that should speed up the calculation and returning the correct bits in the specific range, actually behaves as intended, that is, the designers of the instruction assumed the users will know the limitation of it, that is, it was originally assumed that the users were supposed to know that the function is not the "general" one and the "bug" was just in the misleading documentation. By fdiv you've had an instruction that didn't behave as intended, being wrong for some very specific inputs and not only outside of the designed range.
- brucedawson 8y ago
  > It seems that Bruce was the first managing to induce the change in glibc glibc changed their implementation before I reported on this.

inetknght 8y ago

What's that? Floating point math strikes again? /s Let's build something better.

stealthcat 8y ago
Need many years ahead for IEEE interval arithmetic hardware implementations to be usable... https://standards.ieee.org/findstds/standard/1788-2015.html https://standards.ieee.org/findstds/standard/1788-2015.html
- bsder 8y ago
  Intervals in interval arithmetic can rapidly go to infinity even when the problem is relatively well behaved (in matrix inversion, for example) and standard floating point arithmetic produces a useful answer.
AceJohnny2 8y ago
IEEE 754 is one of the rare successes of computer engineering and standardization. Turns out it's just hard to implement continuous math on physical hardware. I'm curious (and a bit skeptical) about any efforts that think they can do better.
- triska 8y ago
  John Gustafson has developed several promising alternatives, such as unums, posits and valids: https://posithub.org/about https://posithub.org/about I also recommend his book, The End of Error - Unum Computing: https://www.crcpress.com/The-End-of-Error-Unum-Computing/Gustafson/p/book/9781482239867 https://www.crcpress.com/The-End-of-Error-Unum-Computing/Gus... A transcript of a debate with William Kahan is here: http://www.johngustafson.net/pdfs/DebateTranscription.pdf http://www.johngustafson.net/pdfs/DebateTranscription.pdf
kccqzy 8y ago
What better thing do you have in mind? I'm not aware of any general-purpose floating point math replacement that mature enough to be embedded in billions of processors.

stilley2 8y ago

From 2014, FYI

dang 8y ago
Thanks, added.

jabl 8y ago

Worth noting this is for the x87 fsin instruction. For x86_64 typically a library function is called (which in turn uses SSE2 math instead of x87) rather than generating inline code.

ajross 8y ago
More "pervasively" than merely typically. The x87 registers still exist in a technical sense, but except for compatibility in legacy binaries those instructions are never used.
- burfog 8y ago
  They are used by gcc on x86_64 Ubuntu when dealing with long double. I just tried it, with a trivial function that adds arguments and returns the resulting sum. I think this is true on any x86_64 platform for which sizeof(long double) exceeds 8.
  - ajross 8y ago
    Sure, because "long double" is fundamentally an x86-specific compiler extension[1] designed to exploit the 80 bit FPU precision in the 8087 architecture. Nothing for an SSE (or any other 64 bit IEEE FPU) will be using long double, except for compatibility. [1] Yeah, I think there's a software emulation layer to give you 128 bits on other platforms or somesuch. Again, not important nor relevant to a discussion abou FSIN.
Joky 8y ago
I’m puzzled by what you mean here: you refer to an x87 instruction, which makes me think it is assembly/binary level and then you’re saying that a library function is called. Where is the magic? Is there an x86 feature where you can instruct the CPU to jump to an address when a specific instruction is encountered? Or are you maybe using “library” for microcode in the CPU itself? Edit: or are you referring to fsin at the C language level (in which case the x87 is hard to relate)
- 8y ago

bsder 8y ago

Um, it was known at least as far back as the AMD K5 (which has something like 300+ bits of Pi) that argument reduction on x86 didn't have enough bits of Pi.

londons_explore 8y ago
You need a lot of bits of pi if you want to have an even vaguely accurate result when you do sin(MAX_DOUBLE)

Dylan16807 8y ago

So is it wrong to me to interpret this as an imprecision of a partial ULP on the input number, thereby making the accuracy of the output just fine? Is there a use case for such a numerically unstable function use except as a party trick to get pi?

brucedawson 8y ago
The input number is, unavoidably, not a perfect representation of pi. However the fsin instruction's job is to calculate the sin of the actual input number, not try to guess what input was intended. So it doesn't make sense to interpret this as an imprecision of the input number - the fsin instruction failed to give a result which was as accurate as its documentation promised. The documentation has been fixed now. I don't know how often this actually matters, but it's worth nothing that library implementations of sin() don't use fsin anymore, and I think that is partially because of this flaw.
- Dylan16807 8y ago
  > However the fsin instruction's job is to calculate the sin of the actual input number, not try to guess what input was intended. Not guessing what was 'intended', just treating a number like "1.234567" as "any number that could have rounded to 1.234567000, whatever is most convenient". Does it cause any practical problems to do this? How often do people actually expect/need a double to be treated as having infinite precision, rather than 53 bits or slightly more than 53 bits of precision?

aurelien 8y ago

"Not so much!" ~Intel motto

known 8y ago

Floating Point Math http://0.30000000000000004.com/ http://0.30000000000000004.com/