-1

What Every Computer Scientist Should Know About Floating-point Arithmetic is widely considered absolutely mandatory reading for every programmer. Why is this the case? What aspects of the article make it stand out as still being important to this day?

Upon my reading of it, I found that a lot of is was only concerned with mathematical proofs and memory-level implementations of floating-point arithmetic. Aside from the general points that floating-point arithmetic is neither precise nor associative - a pair of facts that could fit on a single page - I see little reason why the article is of significance to anyone who is programming in any language where memory management is largely not done by hand. Why would say, a Java programmer, care?

11
  • 5
    Anyone who is programming =/= computer scientist
    – Mandrill
    Commented Jan 14, 2021 at 23:59
  • 3
    You are overstating its significance. It's a very good introduction into this topic, but it's definitely not “absolutely mandatory”, despite it's somewhat grandiose title. However, this is not necessarily a very low level concern – Java has floating point numbers as well, with the same problems.
    – amon
    Commented Jan 15, 2021 at 0:12
  • 4
    Actually, "What Every Computer Scientist Should Know About Floating-point Arithmetic" is considered mandatory reading for every Computer Scientist. Or at least that's what the title says. For us mere mortals, we don't necessarily need to know all 73 printed pages of that tome, for the same reasons that you don't need to read all 500 pages of a programming language specification in order to successfully write programs in that language. Commented Jan 15, 2021 at 0:28
  • 1
    @RobertHarvey this is true. It’s also true that those who can dial a touch tone phone are programmers. Users execute their code by pressing redial. Commented Jan 15, 2021 at 3:05
  • 3
    Not sure if I'd call it mandatory, but it might have helped a number of programmers understand why when summing fractions that add to 1 they instead got 0.99999999998745, and done differently get 1.00000000010001. I think that is an understanding that applies to any approximate implementation even if its housed in Java.
    – Kain0_0
    Commented Jan 15, 2021 at 3:38

5 Answers 5

8

Why is this the case? What aspects of the article make it stand out as still being important to this day?

This part all sounds terribly opinion-based.

Upon my reading of it, I found that a lot of is was only concerned with mathematical proofs ...

It's not concerned with proofs - it's concerned with understanding the limits on floating-point accuracy. It says exactly this in the text. The proofs are there so that you can see and understand that (and how) these results are derived - and in any case they're mostly relegated to the Details section. There are only two shown in the main body of the paper.

If you find the proofs too challenging, or you're just not interested in them (and prefer to take the results on faith) - just skip them. It's easy enough to look for the next heading.

... and memory-level implementations of floating-point arithmetic ... memory management is largely not done by hand ...

It does mention the IEEE 754 floating-point formats, but it only shows their numerical ranges and the number of bits in the exponent and mantissa. This isn't the memory layout, and if it were, that would have little or nothing to do with memory management. It's bizarre to think that nobody would ever care that double has an 11-bit exponent unless they needed to malloc and free it.

Why would say, a Java programmer, care?

Looking at the outline of the paper, summarized below, I'd say a Java programmer might care if they want to perform numerical computations, understand their precision and error bounds, and understand how to analyse the cumulative error behaviour of their own code.

Anyway, careful re-reading shows that the title is What Every Computer Scientist Should Know About Floating-Point Arithmetic.

If your only interest is programming in Java (and you don't even care to recognize the distinction between memory layout and memory management) - perhaps you don't consider yourself to be a computer scientist. If you don't want to take a scientific approach or care about numerical accuracy, then perhaps this paper really isn't relevant to you. The number of questions from programmers confused by floating-point imprecision on StackOverflow suggest that it is relevant to many other people.

Anyway, that summary:

  • Rounding Error

    ... The correct answer is .17, so the computed difference is off by 30 ulps and is wrong in every digit! How bad can the error be?

    • Theorem 1 ... the relative error of the result can be as large as ...

      establishes an initial upper bound on the error for subtraction

    • Theorem 2 ... then the relative rounding error in the result is less than 2ε

      tightens the upper bound on the error for subtraction

    • Theorems 3 & 4 establish error bounds for compound expressions involving logs and square roots

    • Theorem 5 just shows how "round to even" accumulates errors differently than the more obvious rounding style

    • Theorem 6 & 7 address the behaviour of multiplication and subtraction

    We are now in a position to answer the question, Does it matter if the basic arithmetic operations introduce a little more rounding error than necessary? The answer is that it does matter, because accurate basic operations enable us to prove that formulas are "correct" in the sense they have a small relative error.

    ... But accurate operations are useful even in the face of inexact data, because they enable us to establish exact relationships like those discussed in Theorems 6 and 7. These are useful even if every floating-point variable is only an approximation to some actual value.

    It even tells you why (and when) you should care about these results. You should care about them whenever you use floating-point computations and care about their accuracy. Yes, even when you don't require manual memory management.

  • The IEEE Standard

    It's the most common implementation, and has some particular characteristics (single- and double-precision, special NaN and infinity values etc.) that are relevant when using this implementation.

  • System Aspects

    Discusses various implementation details, many for systems that aren't Java and you presumably don't care about.

    • Theorem 8 (Kahan Summation Formula)

      It's a useful formula, which can could be affected by the sort of optimizations discussed just above. At least, you should know that there's a reason for optimizers not to use the algebraic identities you might naively expect.

  • The Details

    This just goes back and fills in the proofs and missing rigour from the first half. You can skip it entirely if you want, and that leaves only two proofs in the first section.

1
  • Exactly. Programmers might very well prefer the various strongly opinionated papers by W. Kahan and J. Gustafson; they both generally write about pros/cons of computer floating point, how it relates to numerical accuracy, how you use it to get the right results, and so on. (And in the case of Gustafson, flaws with IEEE 754 and suggested alternatives.)
    – davidbak
    Commented Oct 16, 2022 at 1:02
5

Really an oversize comment:

While the proving part is overkill for people who are simply programming the concepts are critically important.

An incident from the stone age (before that article!) comes to mind: The teacher (a BASIC 1xx class) had assigned a problem for the students that had two fairly obvious approaches--neither was actually correct but the brute force approach made the same error on both paths and actually worked given the limits of the inputs. The intelligent approach made different errors and wouldn't work. I was a lab assistant in the computer lab they were using--my job description didn't include any programming skills but I had been doing it for some years at that point. The students trying the intelligent approach got stuck and after talking with several of them I figured out the teacher had not taught them anything about floating point roundoff. Since the bug was beyond their education I fixed several of the programs and left a comment in the code for the teacher to come to me if he had a problem as I wasn't supposed to help on that assignment.

Next semester I end up writing a trivial program for the whole department:

10 X = 3000000
20 X = X + 1
30 if X + 1 > X goto 20
40 Print "X = X + 1"

Everybody insisted it would never terminate--but it actually terminated pretty quickly. (The 3,000,000 seed value is simply to speed things up--the system in question could only do about 1000 loops/second.)

Since then I've seen every programmer I've worked with professionally (admittedly, not many) burned by roundoff.

4

Say you need to implement some sort of mathematical expression using floating point numbers. How much error is introduced? How many bits do you need in order to reduce the error below a certain threshold? Does it matter in what order you perform the operations? What simplifications of the expression might adversely affect the amount of error and what won't?

It's not always a matter of choosing whether or not to use floating point.

4

Because it disabuses the reader of the assumption that floating point numbers are the same as the every day numbers your learnt about in school.

4
  • 4
    You don't need 70 pages for that.
    – J. Mini
    Commented Jan 15, 2021 at 0:47
  • 2
    @J.Mini You might. It's amazing how long it can take to convince someone of the limitations and gotchas of floating point. But 70 pages is certainly not the preferred format for non-computer scientists. Maybe if we're lucky. there's a Kurzgesagt about it.
    – joshp
    Commented Jan 15, 2021 at 5:23
  • 1
    @joshp At least we have Computerphile: youtube.com/watch?v=PZRI1IfStY0
    – Theraot
    Commented Jan 15, 2021 at 7:04
  • if you tell people its essential though they will think its super complex and it will have done the job
    – Ewan
    Commented Jan 15, 2021 at 9:09
3

Because many programmers make horrible mistakes as they don't understand how floating point numbers work. The fact that the precision of float numbers is limited has far-reaching consequences that you have to be aware of.

E.g. many programmers write code that assumes

a + b != a

holds true. With floats, it may not. If a is huge and b is tiny, it may be false (adding a tiny value to a huge value will not change the huge value). Or they assume that

a + b - a == b

holds true. With floats, it may not, as there can be rounding errors. All of this holds true for integer values but not for floating point values. How often do you see code like this:

float f;
// ... calculations
if (f == 0) { ...

This is stupid, as f may never be zero in reality because of rounding errors. Code like this is fundamentally wrong and code and assumptions as shown above has already led to serious bugs in the past.

And every time code uses floats to represent money, an angel loses its wings. That's a very terrible idea.

Floating point numbers are fast but if you require precision, you need arbitrary-precision numbers. As already the Wikipedia says:

In computing, floating-point arithmetic (FP) is arithmetic using formulaic representation of real numbers as an approximation to support a trade-off between range and precision.

The keyword here is "trade-off"!

Not the answer you're looking for? Browse other questions tagged or ask your own question.