What Every Programmer Should Know About Floating-Point Arithmetic 359
Posted
by
Soulskill
from the gaining-understanding-bit-by-bit dept.
from the gaining-understanding-bit-by-bit dept.
-brazil- writes "Every programmer forum gets a steady stream of novice questions about numbers not 'adding up.' Apart from repetitive explanations, SOP is to link to a paper by David Goldberg which, while very thorough, is not very accessible for novices. To alleviate this, I wrote The Floating-Point Guide, as a floating-point equivalent to Joel Spolsky's excellent introduction to Unicode. In doing so, I learned quite a few things about the intricacies of the IEEE 754 standard, and just how difficult it is to compare floating-point numbers using an epsilon. If you find any errors or omissions, you can suggest corrections."
Analog Computers (Score:3, Informative)
I seems to me that this problem would pop up any time you worked with an irrational number.
Back in the early days the analog computer was used for things like ballistic calculations. I would think that they would be less prone to this type of problem.
Linearity may still be an issue (analog systems have their own set of problems).
strictfp (Score:4, Informative)
Re:#1 Floating Point Rule (Score:3, Informative)
Re:Only scratching the surface (Score:1, Informative)
You really need to talk about associativity (and the lack of it). ie a+b+c != c+b+a
This is actually non-commutativity. Non-associativity means (a+b)+c != a+(b+c).
Re:Analog Computers (Score:5, Informative)
No, irrationality has nothing to do with it. It's a matter of numeric systems, i.e. binary vs. decimal. For example, 0.2 is a rational number. Express it in binary floating point and you'll see the problem: 2/10 is 1/5 is 1/101 in binary. Let's calculate the mantissa: 1/101=110011001100... (long division: 1/5->2/5->4/5->8/5=1,r3->6/5=1,r1->2/5->4/5->8/5...)
All numeric systems have this problem. It keeps tripping up programmers because of the conversion between them. Nobody would expect someone to write down 1/3 as a decimal number, but because people keep forgetting that computers use binary floating point numbers, they do expect them not to make rounding errors with numbers like 0.2.
Re:#1 Rule, Don't use Java (Score:3, Informative)
Actually, the linked article says exactly the opposite, and up above I posted a link to the JVM definition that verifies it. So you are 100% incorrect.
Before we get (Score:5, Informative)
this will save a lot of time & questions to most beginning (and maybe mediocre) programmers.
Not sure it belongs in an intro explanation, but (Score:5, Informative)
Re:Three one-thirds is 1, riiiiight? (Score:3, Informative)
>>> (1.0/3)*3
1.0
Re:Not sure it belongs in an intro explanation, bu (Score:1, Informative)
PLEASE stop this thread - interval arithmetic and all that has been around as a research topic for decades now.
If you did not know: there are search engines providing lots of links...
Re:#1 Floating Point Rule (Score:5, Informative)
Java have a strictfp keyword for strict IEEE-754 arithmetic.
Re:I'd just avoid it (Score:5, Informative)
The non-trivial problems with floating-point really only turn up in the kind of calculations where *any* format would have the same or worse problems (most scientific computing simply *cannot* be done in integers, as they overflow too easily).
Floating-point is an excellent tool, you just have to know what it can and cannot do.
Re:Analog Computers (Score:3, Informative)
True, but irrational numbers are those that cannot be written down exactly in *any* base
... except the irrational number's own base. ;)
Please look here (Score:5, Informative)
According to my personal experience the paper by David Goldberg cited in the post isn't that difficult after all. Plenty of interesting materials can also be found in the Oppenheim & Shafer [amazon.com] textbook about digital signal processing.
Re:Simple, effective and useful (Score:2, Informative)
And wrong. I don't know how to use Github and if he won't bother to post an email address, I won't bother to learn about Github just for this.
The comparison [floating-point-gui.de] page is wrong. Take nearlyEqual(0.0000001, 0) for example. As the author said, using Epsilon can be bad if you don't know what you are doing. The correct form of the function is:
epsilon = 0.00001;
function nearlyEqual(a,b)
{
return (Math.abs(b) < epsilon) ? (Math.abs(a) < epsilon) : (Math.abs((a-b)/b) < epsilon);
}
Also, parentheses don't hurt you and they help the reader.
Re:If you want accuracy... (Score:2, Informative)
Continued fractions are a straightforward way to implement exact computable real arithmetic. So yes, it's been used. And it's slow. But it is exact.
Re:#1 Floating Point Rule (Score:5, Informative)
I think the original poster was referring to this piece by the father of floating point, William Kahan, and Joe Darcy
"How Java's Floating-Point Hurts Everyone Everywhere"
http://www.eecs.berkeley.edu/~wkahan/JAVAhurt.pdf [berkeley.edu]
Re:Simple, effective and useful (Score:3, Informative)
In case you weren't just being funny, that == is correct, as it's meant to prevent NaN or Infinity results from the division, which can only happen with the actual "zero" values.
Oops! (Score:2, Informative)
Without the symbolic evaluation or requesting a particular precision level, the graph you actually get is this:
http://www.untruth.org/~josh/real-rounding-oops1.png [untruth.org]
You can get a more reasonable looking answer by messing with the calculation precision and accuracy...
Re:Another potential solution is Interval arithmet (Score:4, Informative)
Internal arithmetic always includes the exact solution, but only the rarest circumstances does it actually give the exact solution. For example, an acceptable interval answer for 1/3 would be [0.33,0.34]. That interval includes the exact answer, but does not express it.
Re:If you want accuracy... (Score:3, Informative)
It didn't, however, as you imply, have BCD hardware. In fact, it had no hardware at all for arithmetic. At the start of the core memory, you had two lookup tables, one for addition and one for multiplication. To add two values together, you iterated over each pair of (decimal) digits, looking up their values in the table and then storing the result somewhere. If one of the digits had the carry bit set, then you did the same thing with the result of adding the next two digits together to add the extra one.
The 1620 was nicknamed CADET by its designers for this reason - Can't Add, Doesn't Even Try. It was one of IBM's first attempts to make a cheap computer (you could buy a minimal unit for around $100,000 (paper tape instead of punch cards, only 10,000 characters of memory). It was the first computer my university ever bought, and the subject of an incredibly scathing review by Dijkstra.
Re:Another potential solution is Interval arithmet (Score:1, Informative)
Interval Arithmetic does *not* produce exact solutions, it provides upper and lower error bounds on the calculation. Most IA implementations introduce a bias on every bounds calculation to insure that the "exact" result is proven to be bounded by the interval. I think some SPARC processors had IA support.
and Ada (Score:3, Informative)
Correction: COBOL, PL/I and Ada. Ada has both fixed and floating point BCD arithmetic. And yes I too wonder why it is not in wider use. Perhaps it has to do with the ill conceived notion of "light weight languages" - most of which are not light weight at all any more once they are on the market for decade or so.
Martin