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."
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.
Precision isn't that big a deal (we aren't so good at making physical things that 7 decimal digits become problematic, even on something the scale of an aircraft carrier, 6 digits is enough to place things within ~ 1 millimeter).
The bigger issue is how the errors combine when doing calculations, especially iterative calculations.
Nerd rage is the funniest rage.
"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.
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.
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.
Maybe because BCD is the worse possible way to do 'proper' decimal arithmetic, also it would absolutely be very slow.
BCD = 2 decimal digits per 8 bits (4 bits per dd). Working 'inside' the byte sucks
Instead you can put 20 decimal digits in 64bits (3.2 bits per db) and do math much more faster
Why don't any languages except COBOL and PL/I use it?
Exactly
how long until
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.
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);
also it would absolutely be very slow
Depends on the architecture. IBM's most recent POWER and System-Z chips have hardware for BCD arithmetics.
I am TheRaven on Soylent News
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
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
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.
``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.''
A problem which is exacerbated by the fact that many popular programming languages use (base 10) decimal syntax for (base 2) floating point literals. Which, first of all, puts people on the wrong foot (you would think that if "0.2" is a valid float literal, it could be represented accurately as a float), and, secondly, makes it impossible to write literals for certain values that _could_ actually be represented exactly as a float.
Please correct me if I got my facts wrong.
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. :-)
If you want accuracy, BCD is still a failure. It only does base 10 instead of base 2. A truly accurate math system would use 2 integers, one for numerator and one for denominator and thus get all rational numbers. If you need irrationals you get even more complicated. But don't pretend BCD is accurate, it fails miserably on common math problems like 1/3.
I still have more fans than freaks. WTF is wrong with you people?
Well, it would depend on what you're doing the calculations for, and how you're doing them.
Say it used diesel fired engines, and you were instructed to calculate the fuel consumption per engine revolution, and then apply that to a trip. I don't know the specifics on an aircraft carrier, so I'll just make up some numbers.
At full speed, the ship travels at 12 nautical miles per hour (knots). The engines spin at 300rpm. It burns 1275 gallons of fuel per hour.
That's 18,000 engine revolutions per hour, or 0.0708334 gallons per revolution.
1,000 miles at 12 knots = 84.3333334 hours.
If you are to travel 1,000 nautical miles, 18,000 * 83.3333334 = 1,500,000.0012 revolutino. At 0.0707334 gallons per revolution, that would be 106,100.100085 gallons.
But knowing that it burns 1,275 gallons per hour at 12 knots, and you will be traveling for 83.3333334 hours, you will require 106,250.000085 gallons. Using the measure of gallons per revolution to try to come up with a very precise number to work with, you've actually fallen short by 150 gallons for the trip. I can imagine a slight embarrassment by having your aircraft carrier run out of fuel just 7 minutes from its destination.
Using 7 decimal points of precision, when it's multiplied so many times, it can easily cause errors.
I'd be pretty sure they aren't counting gallons per revolution, I only used that as an example of where errors could happen. If you're considering the full length of the ship, 0.1 inches is more than enough to believe you have a good number. :) I believe due to expansion of the metals, the total length of the ship may change more than that depending on if it's a hot or cold day. :)
Serious? Seriousness is well above my pay grade.
Sure, you can make it a problem, but it isn't particularly insidious.
And the part where I say "The bigger issue is how the errors combine when doing calculations" is a pretty compact version of what you said.
Nerd rage is the funniest rage.