Slashdot Mirror
What Every Programmer Should Know About Floating-Point Arithmetic
-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."
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).
Tisha Hayes
Floating point math should be properly verified using interval arithmetic: http://en.wikipedia.org/wiki/Interval_arithmetic
Damn...Missed it! lol
You really need to talk about associativity (and the lack of it). ie a+b+c != c+b+a, and the problems this can cause when vectorizing or otherwise parallelizing code with fp.
And any talk about fp is incomplete without touching on catastrophic cancellation.
Ian Ameline
This article should mention strictfp in the section on Java.
use BCD math. With h/w support it's fast enough...
Why don't any languages except COBOL and PL/I use it?
"I don't know, therefore Aliens" Wafflebox1
"The floating-point types are float and double, which are conceptually associated with the 32-bit single-precision and 64-bit double-precision format IEEE 754 values and operations as specified in IEEE Standard for Binary Floating-Point Arithmetic , ANSI/IEEE Std. 754-1985 (IEEE, New York)."
http://java.sun.com/docs/books/jvms/second_edition/html/Overview.doc.html
Maybe in your list of solutions you could mention interval arithmetic, it's not very much used, but it gives "exact" solution.
If you think that every language except Java implements IEEE-754 to the letter, you are sadly mistakenly. That fact is Java can be used just fine for floating point work in most applications.
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.
to floating point, please, everyone should've read Everything you ever wanted to know about C types and part 2 (which explains fp too).
this will save a lot of time & questions to most beginning (and maybe mediocre) programmers.
Given the great complexity of dealing with floating point numbers properly, my first instinct, and my advice to anybody not already an expert on the subject, is to avoid them at all cost. Many algorithms can be redone in integers, similarly to Bresenham, and work without rounding errors at all. It's true that with SSE, floating point can sometimes be faster, but anyone who doesn't know what he's doing is vastly better off without it. At the very least, find a more experienced coworker and have him explain it to you before you shoot your foot off.
The article gives the impression that base 10 arithmetic is somehow "more accurate". It's not. You still get errors for, say, 1/3 + 1/3 + 1/3. It's just that the errors are different.
Rational arithmetic, where you carry along a numerator and denominator, is accurate for addition, subtraction, multiplication, and division. But the numerator and denominator tend to get very large, even if you use GCD to remove common factors from both.
It's worth noting that, while IEEE floating point has an 80-bit format, PowerPCs, IBM mainframes, Cell processors, and VAXen do not. All machines compliant with the IEEE floating point standard should get the same answers. The others won't. This is a big enough issue that, when the Macintosh went from Motorola 68xxx CPUs to PowerPC CPUs, most of the engineering applications were not converted. Getting a different answer from the old version was unacceptable.
Look, times are tough for programmers already. Knowing how to do things correctly - like proper floating point math - is one of the ways to separate the true CS professional from the wannabe new graduates. Articles like this just make everyone smarter, and make finding a job that much harder.
>>> (1.0/3)*3
1.0
Anyone who loves or hates any language, platform, or manufacturer, doesn't know what they're talking about.
I'm not sure whether that is factually true, but IEEE-754 isn't exactly perfect or without alternatives so I wouldn't base my language choice on it..
That'd be like not using Java because it doesn't represent ints using ones complement; if your code relies on the specific internal implementation of data primitives you're probably doing something wrong.
(Before I get replies: Of course sometimes these things really do matter, but not often enough to dismiss a multi-purpose langauge.)
// MD_Update(&m,buf,j);
Java have a strictfp keyword for strict IEEE-754 arithmetic.
Really, the best answer is to store all numbers on the cloud, and just use a 256-bit GUID to look them up when needed.
People interested into floating point math will find some very interesting materials and horror stories in the documents collected at the home page of professor William Kahan, the man behind IEEE754 standard.
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 textbook about digital signal processing.
Over at Evans Hall at UC/Berkeley, stroll down the 8th floor hallway. On the wall, you'll find an envelope filled with flyers titled, "Why is Floating-Point Computation so Hard to Debug whe it Goes Wrong?"
It's Prof. Kahan's challenge to the passerby - figure out what's wrong with a trivial program. His program is just 8 lines long, has no adds, subtracts, or divisions. There's no cancellation or giant intermediate results.
But Kahan's malignant code computes the absolute value of a number incorrectly on almost every computer with less than 39 significant digits.
Between seminars, I picked up a copy, and had a fascinating time working through his example. (Hint: Watch for radioactive roundoff errors near singularities!)
Moral: When things go wrong with floating point computation, it's surprisingly difficult to figure out what happened. And assigning error-bars and roundoff estimates is really challenging!
Try it yourself at:
http://www.cs.berkeley.edu/~wkahan/WrongR.pdf
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 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.
Yes, it's sarcasm. Deal with it!
It's missing the irritating cutesy "humor".
Warning: this article may contain humor, sarcasm, parody, and perhaps even irony. Read at your own risk.
Sure it can be: by starting with simple explanations fit for novices (who usually aren't actually doing serious numerical math and simply wonder how come 0.1 + 02 != 0.3) and getting into more details progressively.
And I mention the alternatives to floating-point formats and when to use what.
The illegal we do immediately. The unconstitutional takes a little longer.
--Henry Kissinger
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
Some Mathematica code:
The result: http://www.untruth.org/~josh/real-rounding.png
The code on the site for
function nearlyEqual(a,b)
contains the line
if (a==0.0){
Clearly, this should be
if (nearlyEqual(a, 0.0)){
There. What could possibly go wrong now? :)
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.
The illegal we do immediately. The unconstitutional takes a little longer.
--Henry Kissinger
Well, so much for my smug mathy reply! Amusingly, the reason it worked so well is that my "Evaluate" statement asked Mathematica to symbolically evaluate the function prior to graphing. So, the graph looked nice because Mathematica was just graphing the "Abs[x]" function!
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
You can get a more reasonable looking answer by messing with the calculation precision and accuracy...
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.
Note that the cited paper location is docs.sun.com; this version of the article has corrections and improvements from the original ACM paper. Sun has provided this to interested parties for 20odd years (I have no idea what they paid ACM for rights to distribute).
http://www.netlib.org/fdlibm/ is the Sun provided freely distributable libm that follows (in a roundabout way) from the paper.
I don't recall if K.C. Ng's terrific "infinite pi" code is included (it was in Sun's libm) which takes care of intel hw by doing the range reduction with enough bits for the particular argument to be nearly equivalent to infinite arithmetic.
Sun's floating point group did much to advance the state of the art in deployed and deployable computer arithmetic.
Kudos to the group (one hopes that Oracle will treat them with the respect they deserve)
I don't think you are correct about two numbers not being "nearly equal" when they are both close to zero, but with opposite signs. The function returns "true" in this case, no? Are you suggesting this is undesirable? I could see for some use cases that property might be undesirable, but if that's what you meant it wasn't clear. Certainly that property is desirable for some applications.
IMO this sort of thing is a good reason NOT to write a nearlyequals(a,b) function. That will just lull you into a false sense of security that the same rules are appropriate in every case.
You need to consider each case on it's own merits to decide what is meant by "nearly equals" in context.
In some cases that may be best defined in terms of absolute error, in some cases that may be best defined in terms of error relative to the value and in yet other cases it may be best defined in terms of the error relative to the current precision which is related to the value for larger numbers but becomes fixed for smaller (subnormal) numbers.
note: i'm known as plugwash most places but i screwd up registering that here somehow in the past and now can't register
Repeatability. If your code and language are standard-compliant, then you'll get the same floating-point math results as someone using another compliant language on any other platform. Not crucial for some tasks, but it certainly is for others, such as scientific work.
Wouldn't it be great if you could change a switch in your computer to change all double precision fp from 53 bit mantissa to 52 bit, and if your results are suddenly radically different then you know your first set of results couldn't be trusted?
Repeatability is highly overrated. It's no good if you get the wrong results, and a different computer system gets you identical wrong results.
That would be because 0.1 + 02 is 2.1. :-)
That's what I was thinking too. But hey, what do I know, I just work computers, I'm not a mathematician. :)
The way some folks do it,
0.1 + 02 = 0 + 2
0 + 2 = 2
There was a thread on here a few weeks ago, where I explained it in the calculation of payroll. If you're calculating fractional hours, then those decimals come in handy.
1 minute = 0.0166666666666667 hours.
Depending on how many decimal points you make it, it can really mess with your pay.
0.01 * 60 = 0.6
0.02 * 60 = 1.2
0.0166 * 60 = 0.996
0.0167 * 60 = 1.002
For hourly folks, check your paychecks. I'd bet the company is using the most advantageous rounding for their profit rather than for accuracy.
I was recently told on a something that one interval = 0.0083333 (1/120), that it should always be simply cut off (not rounded) at 1 decimal point. I tried to explain, that would make the numbers totally wrong.
1 = 0.0
10 = 0.0
10 instances of 10 would then be 0.0, rather than 0.8. They wanted "absolute" accuracy over thousands of instances, but still insisted chopping it off to one decimal place is the way they wanted it. *sigh*
I do understand why floating point numbers can induce errors, but is it necessary to make it worse by adding in sloppy math?
Serious? Seriousness is well above my pay grade.
There are some decent points there, but a lot of them aren't really related to IEEE 754 compatibility. For example, bullet point #5 on their first-page list of five "gratuitous mistakes" is that Java doesn't support operator overloading. But by that standard, C sucks too, and yet is somehow used in lots of floating-point libraries.
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
It is safe to compare to any small integer, not just zero, as long as you are checking if the the value came from an assignment. It is also safe to use small negative powers of two.
One big problem I have is with programmers who religiously add these epsilon functions and screw up algorithms. In my experience, about 99% of the == statements with floating point are explicitly testing "did the assignment to the same value earlier get executed?" Comparing the bit patterns is exactly what is wanted, stop messing it up!
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