22
$\begingroup$

When I first started working with floating point arithmetic, issues like the one illustrated in the sample below both frustrated and confused me:

scala> (1f/3)*3d // admittedly a bit contrived using 1f
res0: Double = 1.0000000298023224
scala> res0 == 1.0
res1: Boolean = false

I was used to mathematics, and a calculator which used fixed point arithmetic - an environment in which the answers were always "right" (to a given number of decimal places)! The way most programming languages handled decimal numbers felt broken and almost certainly useless for storing monetary values or for use in scientific code. I didn't appreciate the trade-off being made in terms of speed and space by taking the approach IEEE 754 did until much later on when I looked at the specification in detail and the analogy with standard scientific form was brought up.

At what stage should students be introduced to how floating point numbers are stored, and (more importantly) how can the motivations for this approach be properly conveyed?

$\endgroup$
  • 2
    $\begingroup$ Here are some fun SMBC cartoons on the topic. smbc-comics.com/comic/2008-03-16 smbc-comics.com/?id=2999 $\endgroup$ – Ellen Spertus Jun 26 '17 at 0:17
  • 1
    $\begingroup$ Here is a YouTube video that gives an incredible explanation of floats: youtube.com/watch?v=9hdFG2GcNuA It's a speedrunner playing Super Mario 64 in an emulator, going into detail about how floating point numbers give rise to some unusual glitches in the game. The video is both educational and genuinely fascinating. $\endgroup$ – Kevin Jun 26 '17 at 15:39
  • $\begingroup$ I realize that this doesn't change the fact that you need to explain float behavior to students but you should also consider the way BigDecimal works--it shouldn't have the same type of binary rounding problems because it bypasses the whole thing by using Integers for all decimal calculations. $\endgroup$ – Bill K Jun 26 '17 at 17:56
  • $\begingroup$ @BillK the example in the question won't be better with BigDecimal. (Depending on how the division is done, you might get an exception there. But 1/3 is not representable exactly as a decimal number either.) $\endgroup$ – Paŭlo Ebermann Jun 26 '17 at 19:09
  • 1
    $\begingroup$ How do you teach them the analogous integer problem (here, in C): int i = 1/3; i = 3 * i; printf("%d\n", i); -- surprise, the result is 0. $\endgroup$ – Pete Becker Jun 26 '17 at 19:36
24
$\begingroup$

If your students can understand why:

$$\frac{1}{3} = 0.\dot{3}$$

then you can explain simply why floating point calculations are "broken".

When you divide one by three on a simple calculator, you can observe that it usually shows 0.333333333... until it runs out of digits (unless you have a more advanced calculator that can show recurring digits like this).

You can explain that the phenomenon observed here is because of the same thing: one third in floating point is an infinitely repeating sequence:

$$ \frac{1}{3} = 0.0\overline{10}_2$$

If we could store that fully, then multiplying it by three would indeed give us one, as expected. But, like our naive calculator, we don't store all the bits in the sequence, so you end up with a slight inaccuracy. Pointing out that $ 0.333333333 \times 3 = 0.999999999$ should be enough to illustrate the point that with an infinitely repeating decimal, you will not get the correct answer unless all the digits are taken account of (and you'll always be ever so slightly off the correct value, no matter which approximation you use).

It should then be clear to them that unless you use the exact value of $\frac{1}{3}$ in the binary representation, you will also get inaccuracies.

Something to note is that a finite decimal may be a repeating binary fraction (a significant example is $\frac{1}{10}$, which is $0.1_{10}$, but $0.0\overline{0011}_2$), but not vice versa. Clearly, because of this, seemingly finite decimal numbers added together can lead to an infinite binary fraction, and hence an imprecise answer.

If your students are also familiar with scientific notation, then explaining the floating point system of a significant and mantissa should also be relatively painless. Since floating point can represent both very small and very large numbers, representing numbers as $\text{significand} \times 2^{\text{exponent}}$ is the most flexible option. You need not elaborate much further than that, though, I don't think. As Ben I. mentions, a functional knowledge of floating point is needed, but the internals are probably not needed at this stage.

I don't see any reason why you shouldn't introduce the reason why floating point numbers are inaccurate to them quite early on — it's probably worse not to tell them, and leave them to be very confused when their program doesn't work because of the tiny inaccuracies ruining comparisons.

I think floating-point-gui.de does a great job at explaining, very concisely, without any implementation details (and you can read on about the details if you want). Using that as a resource may be helpful to find the right level to teach.

If you want to give your students something to play around with and get an understanding of the format of IEEE 754 floating point, you could try this floating point number converter which will show the representation of any number you enter.

It might also be wise to introduce a strategy to solve this problem—epsilon values. It should be relatively straightforward to explain that you just compare if a number is 'close' to what you expected with a floating point operation, rather than exactly equal; there are plenty of resources available that explain epsilon values further if necessary.

$\endgroup$
  • 3
    $\begingroup$ @Giles It's a very long time since I first met recurring decimals, but I don't recall too many fellow students not getting it. $\endgroup$ – TripeHound Jun 26 '17 at 8:15
  • 7
    $\begingroup$ Once you've shown the problem with 1/3, it might be better to show 1/10 in binary. Although, as noted above, I could "get" recurring decimals, there's a danger of people thinking it's something peculiar about one third. Seeing the same problem happening with a "safe" number like one tenth drove the point home for binary representations. $\endgroup$ – TripeHound Jun 26 '17 at 8:19
  • 3
    $\begingroup$ +1, comment by @TripeHound about the dangers of "safe"/not-periodic numbers like 1/10 should be added to the answer. Also, the problem with subtraction $\endgroup$ – xDaizu Jun 26 '17 at 12:52
  • 3
    $\begingroup$ "a finite decimal may be a repeating binary fraction and vice versa" – Actually, a finite binary fraction will always convert to a finite decimal fraction (with at most the same number of digits). $\endgroup$ – Paŭlo Ebermann Jun 26 '17 at 19:11
  • 3
    $\begingroup$ @RobertCartaino I do not understand your objection here. 1.0 + 1.0 does equal 2.0 in common floating-point systems. The problem is instead with 1.0 / 10.0 * 10.0, which rounds well in decimal but not in binary, and this answer explains why. Were you commenting on an earlier edit? $\endgroup$ – Bradd Szonye Jun 26 '17 at 19:41
19
$\begingroup$

In my experience, the most confusing aspect here is not that there are rounding errors. Students should already have an understanding that there are physical limits that keep us from calculating with infinite precision all the time. What is confusing though is that these rounding errors occur in cases that might seem trivial to students.

What is important to understand here is that there are real numbers which do have a finite representation in decimal, but lead to an infinite representation when being converted to binary. 0.1 is probably the canonical example here. Students are used to thinking in base 10, so the most surprising rounding errors are those, where the operation still stays within the number of a couple of significant decimal digits, and therefore looks completely harmless when writing it down on paper, but still blows up because the numbers cannot be represented exactly in binary. Think: $0.1 + 0.2 - 0.3 \neq 0$.

Hammering this single point home should be enough to convince students that floats can lead to surprising rounding errors. The more challenging task is then to restore their faith in floats by explaining that the behavior of floats is still completely deterministic and one can actually give exact bounds for the expected rounding errors produced by a specific calculation.

For instance, many programming languages these days have support for hex float literals, which allow specifying float literals in base 16, eliminating potential rounding errors when converting the base 10 numbers from the source code to the base 2 numbers used by the machine. You still can get rounding errors on each calculation, but knowing what the numbers look like to the machine makes it much more predictable when to expect such rounding errors. Also, most of these calculation rounding errors are actually not due to the machine being unable to calculate exactly, but rather the fact that the result of the calculation can not be represented exactly in float. So the result is often really the closest to the correct result that you can possibly achieve with the chosen representation.

$\endgroup$
  • 1
    $\begingroup$ Firstly, I'd like to welcome you to Computer Science Educators! Secondly, this answer is superb, I do hope we will be hearing more from you. $\endgroup$ – ItamarG3 Jun 26 '17 at 9:31
  • 3
    $\begingroup$ I joined CSE just to up-vote this... $\endgroup$ – WLGfx Jun 26 '17 at 13:49
  • $\begingroup$ If you need accuracy beyond the float standard, use integer math or a data type like Decimal. $\endgroup$ – Cees Timmerman Jun 27 '17 at 9:47
9
$\begingroup$

Even fairly early coders need to understand some limited form of why

    double a = 1.000001;
    double b = 0.000001;
    System.out.println((a-b)==1.0);

ultimately prints false, and how to avoid this problem.

However, a more serious understanding of IEEE 754 can wait. I have my kids implement this standard (just the number representation, no arithmetic) as an elective after they have already learned about two's complement, big and little endian, and how a logical-gate 8-bit adder works. Before they've had some time to live with and understand how binary numbers work, they won't have much of a chance of appreciating how floating point is dealt with on any serious level.

$\endgroup$
9
$\begingroup$

A few points:

  • Do not call the discrepancies rounding errors
  • Do not confuse students with epsilon math
  • Do not obsess on teaching them exactly how IEEE floats are stored
  • Do not show them examples of the problem without explaining why things happened the way they did

Teach them this:

Floats are confusing precisely because the way they are stored and the way they are represented is incompatible. The values don't always translate 1 to 1. Some values that are easy to represent can't be stored faithfully with finite memory. So they are converted (not rounded) to the closest storable value available. Sometimes this goes completely unnoticed because when that stored value is converted (not rounded) back to a representation it ends up being the same representation it had before it went in. However, if math is done on this value then it's done on the stored value. The new stored value might get lucky and convert back to the correct representation. It might not. It's this "might" thing that makes this so hard. I can run tests on numbers thinking I got back what I put in so it must store exactly only to have my heart broken when I do math with it.

For example:

1.03 - .42

gives

0.6100000000000001

On their own 1.03 and .42 convert in and out of memory fine despite not being perfectly stored. Their difference is ALMOST right. It just doesn't happen to convert the way we hoped. Other math can put us at this same stored value that expects exactly this representation. There's no perfect way to round it. We simply don't know any more at this point than what was stored.

Yet:

.01 - .02

gives a perfect

-0.01

Why? Because we got lucky. The information that was lost in conversion just happened to not be enough to matter once it was converted back.

I hate problems that are hard to diagnose because I keep getting "lucky".

Now you can throw a lot of math and diagrams at this problem trying to explain how floats are stored but the thing to teach is how to know which numbers can't be stored perfectly. Because the computer isn't going to tell you.

It's the students expectation of how floats will behave that you want to cultivate. They shouldn't expect them to behave like calculators. They shouldn't expect them to be useless. They should expect if you can't get to a number by addition and dividing by 2 that the numbers are going to be fuzzy. That's fine for scientific measurements that just want to be close. Not good for accounting that cares as much about pennies as dollars. A base 10 currency won't always store precisely. Though if you can find a currency that is always divided by 2 then floats will keep your accountant happy.

ruler with inches

Show them a ruler with inches on it. Floats can store inch fractions perfectly. This should debunk the myth that floats have rounding errors. Entering these into a computer and doing math on them is a good exercise because it forces the student to do the conversion by hand. These conversions will all happen without discrepancies. You can even challenge the students to try to catch the computer doing inch fraction math wrong.

I used to teach this with drafting rulers. You can get one that has decimal inches. Put the decimal inch ruler next to the fraction inch ruler. Show them how some numbers match up but others don't. The decimal inch ruler represents what you see and what you type. The fraction inch ruler represents what is stored.

enter image description here

You can even get students to reproduce the same kinds of errors by having them take measurements of values from the decimal ruler on the fraction ruler and trying to convert back. They'll quickly notice that some convert back easily while others don't. Well, as long as you don't let them simply remember how the story started.

You can find links to other resources in my earlier posts here.

$\endgroup$
  • $\begingroup$ I like how you stress the difference between rounding and conversion. However, your use of terminology is slightly incorrect compared to IEEE754. Conversion is the process of switching between decimal and float. In some cases, switching back and forth will not lose information. However, there is usually still rounding taking place in those conversions, possibly even if after converting back you end up with the same result (the two roundings simply cancelled out in that case). I would be hesitant to oversimplify things here, as that might do more harm than good in the long run. $\endgroup$ – ComicSansMS Jun 27 '17 at 7:24
  • 2
    $\begingroup$ @ComicSansMS I'm trying to get away from the myth that the discrepancies in floats are just rounding errors. I've seen to many students turn in code that attempts to correct the problem with their own rounding code. That's the oversimplification to avoid. $\endgroup$ – candied_orange Jun 27 '17 at 8:24
  • 1
    $\begingroup$ The decimal inch ruler is perfect here. $\endgroup$ – Sean Houlihane Jun 27 '17 at 13:45
4
$\begingroup$

Here are a few more ideas:

Point out that that only $2^{32}$ values can be represented in 32 bits (or $2^{64}$ values in 64 bits), while there are an infinite number of real numbers. Therefore, not all real numbers can be represented exactly. For example, if you take the smallest positive number that can be represented exactly and divide it by 2, you can't represent it exactly (by definition).

Explain that floating-point numbers are represented as the sum of powers of 2. Have them compute relatively easy values, such as $1\frac{3}{4} = 1 + \frac{1}{2} + \frac{1}{4}$. Ask them to represent $\frac{1}{3}$ as the sum of powers of 2. They will not be able to.

$\endgroup$
2
$\begingroup$

As a student myself, I had a course about how processing and encoding works where we had a detailed part about operations in different bases and how floats and doubles differ from one another by the number of bytes allocated, and how the computer's different ways of encoding floating numbers can be done by hand to get a grasp of it, but this wasn't until my third year, after having a first introduction to operations in different bases during my second year.

Only basic understanding of numbers in different bases and knowledge of the fact that floats are coded on a given number of bits is necessary to understand why it may be a problem, you could use the example of scientific calculations, where precision is important to make students get the stakes. But if you want students to really understand it fully, I think training operations in different bases and making them try by hand floating numbers coding and rounding may be necessary to get how frequent approximations are and how trivial calculations can give an answer different than what's expected, but more time consuming.

Also, if you want a playful and yet well explained way to teach students how those imprecisions work and how it may affect programs, here is a 10 min long video about floating numbers imprecision in mario 64 that's really well explained : https://www.youtube.com/watch?v=9hdFG2GcNuA

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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