8 ms·

What every computer scientist should know about floating-point arithmetic (1991) [pdf]

125 points by jbarrow 6mo ago

lifthrasiir 6mo ago
(1991). This article is also available in HTML: https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.h...
tomhow 6mo ago
What Every Computer Scientist Should Know About Floating-Point Arithmetic (1991) - https://news.ycombinator.com/item?id=23665529 https://news.ycombinator.com/item?id=23665529 - June 2020 (85 comments) What Every Computer Scientist Should Know About Floating-Point Arithmetic - https://news.ycombinator.com/item?id=3808168 https://news.ycombinator.com/item?id=3808168 - April 2012 (3 comments) What Every Computer Scientist Should Know About Floating-Point Arithmetic - https://news.ycombinator.com/item?id=1982332 https://news.ycombinator.com/item?id=1982332 - Dec 2010 (14 comments) What Every Computer Scientist Should Know About Floating-Point Arithmetic - https://news.ycombinator.com/item?id=1746797 https://news.ycombinator.com/item?id=1746797 - Oct 2010 (2 comments) Weekend project: What Every Programmer Should Know About FP Arithmetic - https://news.ycombinator.com/item?id=1257610 https://news.ycombinator.com/item?id=1257610 - April 2010 (9 comments) What every computer scientist should know about floating-point arithmetic - https://news.ycombinator.com/item?id=687604 https://news.ycombinator.com/item?id=687604 - July 2009 (2 comments)
atoav 6mo ago
One thing that really did it for me was programming something where you would normally use floats (audio/DSP) on a platform where floats were abysmally slow. This forced me to explore Fixed-Point options which in turn forced me to explore what the differences to floats are.
- KeplerBoy 6mo ago
  Also heavily used in FPGA based DSP.
- jacquesm 6mo ago
  Fixed point gave rise to the old programmers meme 'if you need floating point you don't understand your problem'. It's of course partially in jest but there is a grain of truth in it as well.
  - deleted 6mo ago
    [deleted]
  - adampunk 6mo ago
    It is quite old, attributable to VonNeumann and Goldstine in 1947. Later Goldstine joked that if rescaling for every step was easy enough for Johnny it ought to be easy for everyone else. The gag here being that perhaps that isn’t the best dividing line for programming talent.
    - jacquesm 6mo ago
      That's hilarious. It's like slicing off the top 0.0001% of mt. Everest and saying that you have evenly split the world.
      - adampunk 6mo ago
        It gets WORSE. Here's a quote from “The Birth of a Computer” in BYTE Magazine, February 1985, an interview with J.H. Wilkinson, noted numerical slouch, on the Manchester machines ca 1949 (p. 178): >They were fixed point, but one of the earliest things that I did (at Turing’s request) was to program a set of subroutines for doing floating-point arithmetic. So we ought to scale to better ourselves with self-study, meanwhile one of the first errands TURING send WILKINSON on was to rid themselves of this duty. ;)
        jacquesm 6mo ago
        The 'numerical slouch' bit had me in stitches. It's interesting how many of these things we take for granted. I'm working (and have been for a while) on something that requires both ridiculous precision and speed on a relatively puny power budget and it's been a really nice trip down memory lane regarding optimization. I discovered fixed point pretty early in my programming career when doing 3D graphics on the 6502. I never imagined that that knowledge would come in handy more than almost five decades later, but here we are.
emil-lp 6mo ago
> 0.1 + 0.1 + 0.1 == 0.3 False I always tell my students that if they (might) have a float, and are using the `==` operator, they're doing something wrong.
- magicalhippo 6mo ago
  I also like how a / b can result in infinity even if both a and b are strictly non-zero[1]. So be careful rewriting floating-point expressions. [1]: https://www.cs.uaf.edu/2011/fall/cs301/lecture/11_09_weird_floats.html https://www.cs.uaf.edu/2011/fall/cs301/lecture/11_09_weird_f... (division result matrix)
  - StilesCrisis 6mo ago
    Anything that overflows the max float turns into infinity. You can multiply very large numbers, or divide large numbers into small ones.
    - magicalhippo 6mo ago
      Sure, division might be a tad more surprising though since most don't do that on an every-day basis. The specific case we had was when a colleague had rewritten (a / b) * (c / d) * (e / f) to (a * c * e) / (b * d * f) as a performance optimization. The result of each division in the original was all roughly one due to how the variables were computed, but the latter was sometimes unstable because the products could produce denomalized numbers.
- jmalicki 6mo ago
  .125 + .375 == .5 You should be using == for floats when they're actually equal. 0.1 just isn't an actual number.
  - Sharlin 6mo ago
    > 0.1 just isn't an actual number. A finitist computer scientists only accepts those numbers as real that can be expressed exactly in finite base-two floating point?
randusername 6mo ago
For anyone turned off by this document and its proofs, I recommend Numerical Methods for Scientists and Engineers (Hamming). Still a math text, but more approachable. The five key ideas from that book, enumerated by the author: (1) the purpose of computing is insight, not numbers (2) study families and relationships of methods, not individual algorithms (3) roundoff error (4) truncation error (5) instability
- ses1984 6mo ago
  Can you elaborate a little on what 1 is supposed to mean?
  - anymouse123456 6mo ago
    Not the OP, but I suspect it means focus on what questions are being asked first, and even then, look for opportunities to simplify wherever you find them. So many of us spend so much time getting enamoured with technical solutions to problems that no one cares about.
  - randusername 6mo ago
    > This motto is often thought to mean that the numbers from a computing machine should be read and used, but there is much more to the motto. The choice of the particular formula, or algorithm, influences not only the computing but also how we are to understand the results when they are obtained. The way the computing progresses, the number of iterations it requires, or the spacing used by a formula, often sheds light on the problem...Thus computing is, or at least should be, intimately bound up with both the source of the problem and the use that is going to be made of the answers-- it is not a step to be taken in isolation from reality (From "An Essay on Numerical Methods" p 3 of the mentioned text; emphasis authors)
fusionadvocate 6mo ago
"Nothing brings fear to my heart more than a floating point number." Gerald Jay Sussman.
- nxobject 6mo ago
  Not-so-coincidentally, Scheme specifies an exact rational number type. [0] This does not simplify things. [1] [0] https://www-sop.inria.fr/indes/fp/Bigloo/doc/r5rs-9.html#Numbers https://www-sop.inria.fr/indes/fp/Bigloo/doc/r5rs-9.html#Num... [1] https://www.deinprogramm.de/sperber/papers/numerical-tower.pdf https://www.deinprogramm.de/sperber/papers/numerical-tower.p...
jbarrow 6mo ago
Shared this because I was having fun thinking through floating point numbers the other day. I worked through what fp6 (e3m2) would look like, doing manual additions and multiplications, showing cases where the operations are non-associative, etc. and then I wanted something more rigorous to read. For anyone interested in floating point numbers, I highly recommend working through fp6 as an activity! Felt like I truly came away with a much deeper understanding of floats. Anything less than fp6 felt too simple/constrained, and anything more than fp6 felt like too much to write out by hand. For fp6 you can enumerate all 64 possible values on a small sheet of paper. For anyone not (yet) interested in floating point numbers, I’d still recommend giving it a shot.

125 points by jbarrow 6mo ago

(1991). This article is also available in HTML: https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.h...

tomhow 6mo ago

What Every Computer Scientist Should Know About Floating-Point Arithmetic (1991) - https://news.ycombinator.com/item?id=23665529 https://news.ycombinator.com/item?id=23665529 - June 2020 (85 comments) What Every Computer Scientist Should Know About Floating-Point Arithmetic - https://news.ycombinator.com/item?id=3808168 https://news.ycombinator.com/item?id=3808168 - April 2012 (3 comments) What Every Computer Scientist Should Know About Floating-Point Arithmetic - https://news.ycombinator.com/item?id=1982332 https://news.ycombinator.com/item?id=1982332 - Dec 2010 (14 comments) What Every Computer Scientist Should Know About Floating-Point Arithmetic - https://news.ycombinator.com/item?id=1746797 https://news.ycombinator.com/item?id=1746797 - Oct 2010 (2 comments) Weekend project: What Every Programmer Should Know About FP Arithmetic - https://news.ycombinator.com/item?id=1257610 https://news.ycombinator.com/item?id=1257610 - April 2010 (9 comments) What every computer scientist should know about floating-point arithmetic - https://news.ycombinator.com/item?id=687604 https://news.ycombinator.com/item?id=687604 - July 2009 (2 comments)

atoav 6mo ago

One thing that really did it for me was programming something where you would normally use floats (audio/DSP) on a platform where floats were abysmally slow. This forced me to explore Fixed-Point options which in turn forced me to explore what the differences to floats are.

KeplerBoy 6mo ago
Also heavily used in FPGA based DSP.
jacquesm 6mo ago
Fixed point gave rise to the old programmers meme 'if you need floating point you don't understand your problem'. It's of course partially in jest but there is a grain of truth in it as well.
- deleted 6mo ago
  [deleted]
- adampunk 6mo ago
  It is quite old, attributable to VonNeumann and Goldstine in 1947. Later Goldstine joked that if rescaling for every step was easy enough for Johnny it ought to be easy for everyone else. The gag here being that perhaps that isn’t the best dividing line for programming talent.
  - jacquesm 6mo ago
    That's hilarious. It's like slicing off the top 0.0001% of mt. Everest and saying that you have evenly split the world.
    - adampunk 6mo ago
      It gets WORSE. Here's a quote from “The Birth of a Computer” in BYTE Magazine, February 1985, an interview with J.H. Wilkinson, noted numerical slouch, on the Manchester machines ca 1949 (p. 178): >They were fixed point, but one of the earliest things that I did (at Turing’s request) was to program a set of subroutines for doing floating-point arithmetic. So we ought to scale to better ourselves with self-study, meanwhile one of the first errands TURING send WILKINSON on was to rid themselves of this duty. ;)
      - jacquesm 6mo ago
        The 'numerical slouch' bit had me in stitches. It's interesting how many of these things we take for granted. I'm working (and have been for a while) on something that requires both ridiculous precision and speed on a relatively puny power budget and it's been a really nice trip down memory lane regarding optimization. I discovered fixed point pretty early in my programming career when doing 3D graphics on the 6502. I never imagined that that knowledge would come in handy more than almost five decades later, but here we are.

emil-lp 6mo ago

> 0.1 + 0.1 + 0.1 == 0.3 False I always tell my students that if they (might) have a float, and are using the `==` operator, they're doing something wrong.

magicalhippo 6mo ago
I also like how a / b can result in infinity even if both a and b are strictly non-zero[1]. So be careful rewriting floating-point expressions. [1]: https://www.cs.uaf.edu/2011/fall/cs301/lecture/11_09_weird_floats.html https://www.cs.uaf.edu/2011/fall/cs301/lecture/11_09_weird_f... (division result matrix)
- StilesCrisis 6mo ago
  Anything that overflows the max float turns into infinity. You can multiply very large numbers, or divide large numbers into small ones.
  - magicalhippo 6mo ago
    Sure, division might be a tad more surprising though since most don't do that on an every-day basis. The specific case we had was when a colleague had rewritten (a / b) * (c / d) * (e / f) to (a * c * e) / (b * d * f) as a performance optimization. The result of each division in the original was all roughly one due to how the variables were computed, but the latter was sometimes unstable because the products could produce denomalized numbers.
jmalicki 6mo ago
.125 + .375 == .5 You should be using == for floats when they're actually equal. 0.1 just isn't an actual number.
- Sharlin 6mo ago
  > 0.1 just isn't an actual number. A finitist computer scientists only accepts those numbers as real that can be expressed exactly in finite base-two floating point?

randusername 6mo ago

For anyone turned off by this document and its proofs, I recommend Numerical Methods for Scientists and Engineers (Hamming). Still a math text, but more approachable. The five key ideas from that book, enumerated by the author: (1) the purpose of computing is insight, not numbers (2) study families and relationships of methods, not individual algorithms (3) roundoff error (4) truncation error (5) instability

ses1984 6mo ago
Can you elaborate a little on what 1 is supposed to mean?
- anymouse123456 6mo ago
  Not the OP, but I suspect it means focus on what questions are being asked first, and even then, look for opportunities to simplify wherever you find them. So many of us spend so much time getting enamoured with technical solutions to problems that no one cares about.
- randusername 6mo ago
  > This motto is often thought to mean that the numbers from a computing machine should be read and used, but there is much more to the motto. The choice of the particular formula, or algorithm, influences not only the computing but also how we are to understand the results when they are obtained. The way the computing progresses, the number of iterations it requires, or the spacing used by a formula, often sheds light on the problem...Thus computing is, or at least should be, intimately bound up with both the source of the problem and the use that is going to be made of the answers-- it is not a step to be taken in isolation from reality (From "An Essay on Numerical Methods" p 3 of the mentioned text; emphasis authors)

fusionadvocate 6mo ago

"Nothing brings fear to my heart more than a floating point number." Gerald Jay Sussman.

nxobject 6mo ago
Not-so-coincidentally, Scheme specifies an exact rational number type. [0] This does not simplify things. [1] [0] https://www-sop.inria.fr/indes/fp/Bigloo/doc/r5rs-9.html#Numbers https://www-sop.inria.fr/indes/fp/Bigloo/doc/r5rs-9.html#Num... [1] https://www.deinprogramm.de/sperber/papers/numerical-tower.pdf https://www.deinprogramm.de/sperber/papers/numerical-tower.p...

jbarrow 6mo ago

Shared this because I was having fun thinking through floating point numbers the other day. I worked through what fp6 (e3m2) would look like, doing manual additions and multiplications, showing cases where the operations are non-associative, etc. and then I wanted something more rigorous to read. For anyone interested in floating point numbers, I highly recommend working through fp6 as an activity! Felt like I truly came away with a much deeper understanding of floats. Anything less than fp6 felt too simple/constrained, and anything more than fp6 felt like too much to write out by hand. For fp6 you can enumerate all 64 possible values on a small sheet of paper. For anyone not (yet) interested in floating point numbers, I’d still recommend giving it a shot.