When people wonder why floating point calculations sometimes don't perfectly match the expectations of a "correct" answer[1], inevitably people will often respond with the famous paper, "What Every Computer Scientist Should Know About Floating-Point Arithmetic"[2].
Unfortunately, the people who suggest that paper don't realize that it's a very technical treatise and not an appropriate introduction for the types of programmers who ask the question.
I've always thought a better answer was to have the programmer "construct" a toy floating point format (e.g. 8 bits instead of 32-bit-or 64-bits). The programmer would then notice that he has a finite representation of 256 possible "states" to represent -inf to 0 to +inf. The programmer would have to pick a range and a precision to "squeeze" the Real Numbers into that representation of 8 bits.
Design choice 1: I'll have my 256 possible states represent -1billion to +1billion. Well, since you can't overlay 256 states/values across 2 billion unique values, you will have huge "gaps" between numbers.
Design choice 2: I'll have my 256 possible states represent -10 to +10. With a smaller range, you can now increase the precision and represent fractional numbers with digits after the decimal point. But the range is very small. Also, you still have "gaps" where you can't represent most[3] fractional numbers.
The programmer would quickly notice that he'd run into some contradictions. No matter what he does, there will always be gaps. The lightbulb would then go on and then he'd immediately scale up the limitations inherent in 8bit floating point all the way to 64bit floating point and know exactly why 0.3333 * 3.0 does not exactly equal 1.0.
It had been on my vague "todo" list to write such a tutorial but your blog post already gets that "construction of floating point" idea nicely. The programmer can then explore more advanced topics of "normalization" and "bias" in designing a floating point format.
> Unfortunately, the people who suggest that paper don't realize that it's a very technical treatise and not an appropriate introduction for the types of programmers who ask the question.
Programmers of the 'types' (whatever those are) that ask such questions are exactly the target audience of that paper, technical treatment of a technical subject is a-ok.
If you need floating point you don't actually understand your problem used to be a common mantra back when floating point computation still incurred a significant speed penalty. We have come a long way since then but every computer programmer should read that paper and understand it if they want their programs to work properly when using floating point.
You can't really use a tool that you do not understand and using floating point has plenty of pitfalls.
Programmers tend to use floating point casually, either because their language of choice will switch to it when not told otherwise, because they think it is a magic solution to some kind of problem that they have (say counting beyond some arbitrary number), because they are lazy or because they need fractional representation of some number in a well defined range.
If the chain of computation is long enough, if the number of input variables is large enough and if the operations are varied enough this will lead to hard-to-diagnose bugs and problems if not enough understanding is used when implementing the code. FP is a powerful tool, but like any powerful tool it can hurt you if you don't understand it.
I recently came across this blog post [1] with the same title as that famous paper. But they switched out "scientist" for "programmer" and use a more graphical, less technical approach. It's probably better for this purpose.
EDIT: To clarify I mean "better than the famous paper". The blog post linked in this story is also very good, I'd say these two posts complement each other nicely.
> Unfortunately, the people who suggest that paper don't realize that it's a very technical treatise and not an appropriate introduction for the types of programmers who ask the question.
I think the main value of that paper for newbie programmers is not to learn all the nitty gritty details about floats (which would be futile), but instead get the idea that floats can, and will, behave unintuitively, and that they are not just decimal numbers like many beginner materials propose.
That would be great if they did, but I suspect that many programmers would look at the style and wave it away as boffin stuff they don't really need to worry about.
"No matter what he does, there will always be gaps."
Here is how to do this [1]: keep a fixed-size array of every number seen, and store numbers as index into the array. When or if [2] the array fills up, garbage collect by finding a number in the array that is fairly close and hasn't been used recently, and updating it to contain the value you need _now_. Yes, that may change values computed some time ago, but who cares? Your unit tests will run fine, it teaches you to defend your code against bits flipping in RAM, and it is not as if you remember that that fish you caught months ago was 1.8 meters long and not sqrt(3) meter.
[1] if you like designing esoteric languages.
[2] it wouldn't terribly surprise me to learn that many programs do not need that many different float values to survive long.
I'm missing something here. Is the point of this system to use the same floating point value in several different places without storing it in several different places? Why not just use a pointer? If the array is fixed-size, where are you storing e.g. the fact that 01110010 is actually 3.79017423523459?
The best introduction I had was the back of my ZX Spectrum manual, which offered a very lucid and correct explanation of how maths really works on a binary chip.
Here is a nice challenge: Just like we have arbitrary precision integers (allocating more memory as needed) and arbitrary precision "fractional numbers", design a library providing arbitrary precision "computable numbers".
An obvious representation is a convergent stream of fractions. This will also quickly drive home why you cannot implement equality.
The other obvious representation is that of first order formulae over the theory of real fields, but then you need to check equivalence of arbitrary formulae. You ultimately need a limit operation to be included and now you're sunk. You'll also probably wish you were implementing the complex numbers instead pretty quickly.
Programs written in programming languages aren't guaranteed to terminate. Computable numbers, however, are all real numbers that can be represented to arbitrary precision by a computation that terminates. Wouldn't that mean we don't need a fully fledged programming language to have the capability to represent all computable numbers?
Somewhere in there is the idea we just need a program that determines whether an arbitrary program terminates or not...
I can't tell how much of this is a joke, but, yes, it turns out you can't write such a programming language for exactly the reason you allude to: you can't tell whether a given number is computable in finite time, as you don't know whether your program will terminate.
Floating point numbers can be justified by two criteria:
1) The distribution of typical numbers
2) The desired precision across a distribution
1: Floating point numbers suggest an exponential distribution, which comes up very often in science, engineering, etc. Very rarely we have real data neatly packet in a small [-a,a] range.
2: Floating point satisfy the following error metric approximately uniformly: for any -max < x < max, Error = float(x)/x; that is, the relative error is small. This again agrees with real world requirements for data, where we tolerate larger errors for larger numbers.
I think the easiest answer to that question is that there's rounding happening in almost every step where you do something with them. This also includes parsing from decimal floats in textual representation and outputting as decimal floats in textual representation.
The funny thing is that if you work with decimal floating points you usually don't get any of those effects because you often stay inside the accuracy/precision that the float can hold. Yet they're seen as useless.
When people wonder why floating point calculations sometimes don't perfectly match the expectations of a "correct" answer[1], inevitably people will often respond with the famous paper, "What Every Computer Scientist Should Know About Floating-Point Arithmetic"[2].
Unfortunately, the people who suggest that paper don't realize that it's a very technical treatise and not an appropriate introduction for the types of programmers who ask the question.
I've always thought a better answer was to have the programmer "construct" a toy floating point format (e.g. 8 bits instead of 32-bit-or 64-bits). The programmer would then notice that he has a finite representation of 256 possible "states" to represent -inf to 0 to +inf. The programmer would have to pick a range and a precision to "squeeze" the Real Numbers into that representation of 8 bits.
Design choice 1: I'll have my 256 possible states represent -1billion to +1billion. Well, since you can't overlay 256 states/values across 2 billion unique values, you will have huge "gaps" between numbers.
Design choice 2: I'll have my 256 possible states represent -10 to +10. With a smaller range, you can now increase the precision and represent fractional numbers with digits after the decimal point. But the range is very small. Also, you still have "gaps" where you can't represent most[3] fractional numbers.
The programmer would quickly notice that he'd run into some contradictions. No matter what he does, there will always be gaps. The lightbulb would then go on and then he'd immediately scale up the limitations inherent in 8bit floating point all the way to 64bit floating point and know exactly why 0.3333 * 3.0 does not exactly equal 1.0.
It had been on my vague "todo" list to write such a tutorial but your blog post already gets that "construction of floating point" idea nicely. The programmer can then explore more advanced topics of "normalization" and "bias" in designing a floating point format.
[1] http://stackoverflow.com/questions/588004/is-floating-point-...
[2] http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.ht...
[3]http://math.stackexchange.com/questions/474415/intuitive-exp...