Floating Point Programming, Today? 111
An anonymous reader asks: "I'm rather new with programming and stumbled across these twe articles: The Perils of Floating Point from 1996 and What Every Computer Scientist Should Know About Floating-Point Arithmetic from 1991. I tried some of the examples in these articles with Intel's Fortran Compiler and g77 and noted that some of those issue reported no longer seem valid whereas quite a few still very much are around. Could someone, please, give me a pointer to some newer thoughts and/or new facts surrounding floating point programming. What has been improved since those articles were written? What is still the same? How is the future, especially with the new platforms IA64 and AMD64? I am most interested in the x86 and x86-64 architectures. Thank you for your kind help."
The articles are quite up-to-date (Score:5, Informative)
Re:The articles are quite up-to-date (Score:3, Informative)
If you want to avoid the error,
Re:The articles are quite up-to-date (Score:3)
Don't worry (Score:5, Funny)
Nooooooooo! (Score:4, Funny)
It's past 1am and some **** is throwing inexact representations and fuzzy logic at me.... This must be a nightmare... Must... wake... up... Aaaaaargh!
Unsolvable problem (Score:5, Informative)
Much the same problem as you have with decimals. Many fractions cannot be evaluated evenly in certain bases. It will always cause you headaches if you don't realize this.
Try writing a bunch of numbers in hex but then do all of your calculations in decimal. you'll have the same problem.
Re:Unsolvable problem (Score:5, Informative)
Think about tan(89.99) versus tan(89.991) (which is very ill-conditioned around 90). Both numbers are not terribly truncated by floating point, but the results are different by about 1,000. Try it and you'll see floating point error isn't as dangerous as things like cancellation, ill-conditioning and the like.
Re:Unsolvable problem (Score:1)
tan(89.99) and tan(89.991) are *supposed* to be different by about 1000. This is not a good example of floating point instability.
Maybe I misunderstood; maybe you were trying to say that the uncertainty in the angle is likely to be larger than 0.001 degree (or even a tenth of that), so you shouldn't be taking tan() a
Re:Unsolvable problem (Score:4, Informative)
tan(89.990) = -2.0460
tan(89.991) = -2.0408
perhaps you're thinking of
tan(1.571) = -4909.8
and
tan(1.578) = -138.8
Re:Unsolvable problem (Score:1, Informative)
tan(89.991) = -2.0408
perhaps you're thinking of
tan(1.571) = -4909.8
and
tan(1.578) = -138.8
...or perhaps he's thinking of angles in degrees.
Re:Unsolvable problem (Score:1)
Re:Unsolvable problem (Score:1)
Re:Unsolvable problem (Score:2)
Re:Unsolvable problem (Score:5, Insightful)
Basic rule of thumb, determine what accuracy you need, then pick your number representation.
Re:Unsolvable problem (Score:2, Informative)
Quite useful if you're adding integer numbers together on a 32 bit machine in C and you want the carry bit, for instance (and you're too lazy to write the code entirely in integer arithmetic): you can't easily find the sum and carry bit if you're using 32 bit ints, but it's trivial if you have a large
Re:Unsolvable problem (Score:4, Funny)
Re:Unsolvable problem (Score:1)
> of 10. Hell, that's how many I type with anyway.
If we just didn't use our thumbs for counting, that would be octal.
I personally think it would be interesting if we had two thumbs
plus six other fingers on _each hand_, so then we could work in hex.
I do favour place value over two's complement for the representation
of fractional parts, though. Either that or rational notation. I
am not fond of two's complement.
Re:Unsolvable problem (Score:1)
(before you say I'm crazy, remember that I'm just talking about building a machine, whereas you're talking about altering millions of years of evolution and thousands of years of a particular though pattern..
Re:Unsolvable problem (Score:1)
to actually (gasp) add. Then we could work in hex even though we
only have ten fingers. It would sure make a lot of things easier.
And in the process we could obsolete that dang metric system and
replace it with something decent based on powers of two.
What about BCD (Score:1)
Re:What about BCD (Score:1)
Re:What about BCD (Score:2, Interesting)
Re:What about BCD (Score:1)
Oh, there is some other language than common lisp and emacs-lisp?
Re:Unsolvable problem (Score:4, Informative)
Actually, you won't. You would the other way though.
The problem occurs when you try to represent a (properly reduced) fraction whos denominator has one or more prime factors not in common with your number base.
You can represent one tenth in base 10 because all the prime factors in the denominator (10: 5,2) are found within the factorization of the base (also 10: 5,2). You can not represent one sixth in base 10 because one of the factors of 6 is not found in the factorization of 10 (3). Likewise, you cannot represent one tenth in base 2, because the denominator (10) is a multiple of 5, which is a prime not found in the factorization of the base (2).
Because the factorization of 16 contains only primes that are in the factorization of 10 (2) all fractions that can be represented in hexadecimal can be represented in decimal. The reverse is not true, because 10 is the product of a prime (5) that is not found in the factorization of 16. So there is no way to get the "fifths" aspect of a decimal number into a hexadecimal number.
Re:Unsolvable problem (Score:1)
Well ok, but only if accuracy is infinitely more important than space and time. A fixed-point format that can handle from 10^-308 to 10^308 with at least 53 bits of precision wouldn't be terribly useful.
You need to understand how much accuracy you have and not expect to get any more out of the calculations.
Platform and all (Score:5, Informative)
Re:Platform and all (Score:5, Insightful)
With gcc you can force the floating point calculations in the sse registers by -mfpmath=sse.
Re:Platform and all (Score:3, Informative)
It also screws royally with your numerics. Take, for example:
This assertion can fail on Intel hardware, because by the time the assert comes around, x may equal y as one or both of them have been truncated from 80 bits to 32.
Re:Platform and all (Score:2, Interesting)
FWIW, but the Intel Numeric Coprocessors have always done their math in 80-bit floats since their introduction, what was it about 20 years ago ?
Re:Platform and all (Score:1)
Common mistake (Score:5, Informative)
The solution is to count pennies instead, or if you need values bigger than 22 million dollars, use a BCD library. BCD is Binary Coded Decimal.
Re:Common mistake (Score:2)
Re:Common mistake (Score:3, Informative)
float subtotal;
long subtotal_pennies;
And, if you're at a gas station, you need to represent money like this:
long subtotal_mils;
The calculations that you perform on the money are a completely different story. There's no point in worrying about 4 decimal places of percentages if you don't start from the r
Re:Common mistake (Score:3, Informative)
Re:Common mistake (Score:1)
Floats are never the answer for storing money values. Sometimes you might have to use floating point math, but every effort to avoid it should be taken.
Look at this [omnimark.com]
Re:Common mistake (Score:2)
Re:Common mistake (Score:2)
However, they require that accuracy regardless of the magnitude of the number, so floating point is still the wrong solution. The right answer is to use fixed-point BCD with five decimals and round to four for display.
(I used to write business finance software.)
Re:Common mistake (Score:2)
Re:Common mistake (Score:5, Funny)
But that's the point! And you transfer those fractions of cents (that just get rounded off anyway) into an account you control!
"back up in your ass with the resurrection...."
Re:Common mistake (Score:2)
Yep, like in Cobol. I think that's the main reason that financial institutions keep a whole lot of Cobol code and associated hardware around. The closest language that I have found up to now to handle such numbers is Oracle pl/SQL. Ada does have the possibility to specify the precision of a number, but I am not sure that it reverts to BCD based library to do arithmetic with those.
Any one who knows other language with the same capabilities in Cobol ?
Btw., about Intel Coprocessors again, you can use BCD n
Re:Common mistake (Score:1)
Re:Common mistake (Score:1)
x86 has instructions for BCD addition/subtraction (and conversion, IIRC), dating back to the 8086 w/o an FPU coprocessor. The 6502 (apple II, commodore, Nintendo) had a setting for if math (add subtract) was BCD or normal.
Re:Common mistake (Score:2)
It has the ability to use fixed point decimal numbers.
about Intel Coprocessors again, you can use BCD numbers
Actually, x86-64 doesn't support the old BCD instructions in 64 bit mode, reusing those codes for other things.
Re:Common mistake (Score:3)
Your very first college lesson on float data types should have explicitly stated that they should never be used with the equality comparison operator, so even a completely-wet-behind the-ears rookie should know it.
Re:Common mistake (Score:1)
If "everyone" (and just who is everyone exactly) knows about floating point money values, then why am I working on code right now (owned by someone who should know better - think New York finance house) that has all sorts of float money values? Seems to me that this increasingly hypothetical "everyone" that you speak of missed class that day.
Re:Common mistake (Score:2)
Re:Common mistake (Score:1)
Re:Common mistake (Score:1)
And it's not about the equality comparison operator either (which, by the way, is just fine if you use it right). It's because there is no finite binary representation for 0.01, so all your dollars-and-cents values will have rounding error, as will your percent-interest values, and all the other things that use decimal fractions.
Re:Common mistake (Score:2)
Hey that's crazy talk. I can't let that go unchallenged!
The only way to use the equality comparison operator is to calculate everything at a precision level way beyond where you will truncate the result before doing the comparison. The question of just how much extra precision you need to throw away really depends on how many arithmetical operations you'll be doing on it before you get to the comp
Re:Common mistake (Score:1)
If you do IEEE 754 math with fractions with power-of-two denominators (like 13/256 + 7/64), and you stay within the mantissa's range, then you'll get exact results, and equality comparison will work. In practical terms, this never happens, so yes, you can't rely on the equality operator.
Maybe it would be nice if FP computations came with built-in error bars, and equality were defined with
Counting money (Score:1)
Re:Common mistake (Score:1)
- what to do if it's an odd number of nibbles (left 0 ? left F ? right 0 ? right F ?)
- what to do if it's too small or too big for the buffer you're writing into (error ? 0 ? 0-fill ? F-fill ? )
- when reading an odd numbe
Here's an important one. (Score:5, Informative)
If you need more precision... (Score:4, Informative)
Floating point operations are not that bad. (Score:5, Insightful)
extend mantissa so there is enough overlap - usually involves some kind of multiple precision libraries like mentioned in other post GNU MP and many others. I've implemented one for my own use, too. Generally means lots of overhead since there will be less than 5% of operations actually benefitting from greater precision.
postpone such operations until there is overlap - store such numbers together and do operations on them together, too. Sometimes additions in loops will add up small parts so actually there will be overlap with big part and additions can be done with enough precision.
On a side, interesting thing is that in computers multiplications and divisions are better (that is more accurate) than additions and subtractions because of logarithmic format.
I know that Sun was working on a variable precision floating-point CPU. I'm not sure how that project is going and what the end effect is, but I remember it being an interesting idea.
Multiple precision libraries are usually decent with only one problem, they are always slower by a couple orders of magnitude than regular CPU operations, so using them is just such a pain.
Re:Floating point operations are not that bad. (Score:2)
This works because most problems in applied science and engineere are rather good behaving.
If some numerical analyst comes up with a counter example, one can often deem that as a pathological case, without having too much a bad conscience.
I would really like to know, if there are real world engineering examples, where simulations produced dangerous products, because the simulation was inadequate because of numerical errors. Perhaps i
Real world and catastrophic failures (Score:5, Interesting)
I've worked on a couple of projects where this is very important. One was writing control software for metrology equipment, industrial strength QA kit that measured manufactured parts down to fractions of a micron or even nanometres to make sure they were in spec. Another was a geometric modelling tool used in CAD applications and the like.
In neither case am I aware of any physical real world failure caused by a problem with the floating point calculations. You do have to be really careful with manipulating the numbers, though.
For example, the loss of significance when you subtract can be horrible if you've got two position vectors close together, and you're trying to calculate a translation vector from one to the other. The error in that translation vector can be enormous if the points you started with were very close: you might get only one or two significant figures, when the rest of your values have 15 or more. If you're interested in the direction of the vector, that can give you errors of +/- several degrees!
Inevitably, there are always going to be bugs in complex mathematical software, and I've seen plenty of wrong answers from programs like the above. Fortunately, it's normally possible to have checks and balances that at least identify and highlight inconsistencies so, in the worst case, at least nobody relies on them. You can also use ruthless automated testing procedures, which run zillions of calculations every night and flag the smallest changes in the results, so no-one accidentally breaks a verified algorithm with a change later. The combination makes it reasonably unlikely that any algorithm would fail catastrophically with the sort of consequences you're talking about.
The possibility is always there, of course, because programming is subject to human error. However, FWIW, I've worked on software that's used to design cars, and software that controls the QA machinery to make sure they're put together right, and I still drive one. :-)
Python-specific, but contains useful info for all. (Score:4, Informative)
Intervall Analysis (Score:4, Informative)
On the other hand it is clear that a finite representation of real numbers has tradeoffs. But only few seem to care about the cumulated errors.
My experience in engineering (simulation of casted turbine blades) was that people know that bad things can occur during complex floating point calculations but the matter was too complicated to be investigated.
Example: if during finite element simulation a timestep did not end up with a valid solution (the iterative/approximative solver of the large linear systems did not converge or even crash) just some control parameters were varied (time step, perhaps material curves) until the calculation seemed to produce some valid looking result. Needless to say, that that only obvious errors can be spotted that way.
The strange thing about all that is, that in the last years the mathematical discipline of interval analyis has been developed. Here every number is represented with its interval of known error bounds. These error intervall are kept and updated during calculations. Thus at the end of a large complex calculation, you know the error. That is a very valuable property.
More, in fact what one does so in many cases is not only a standard calculation but rather machine proof of error bounds.
This offers some unique properties, e.g. for rigorous global searches.
So we have far better technology available. Why is this stuff not used more widely?
As far as I know, only SUN puts interval analysis enabled data types in its FORTRAN and C/C++ compilers. But I have not seen that stuff in gcc, which would have a big impact.
Very strange.
To whom is interested, here is a homepage of the intervals community [utep.edu].
Regards,
Marc
Re:Intervall Analysis (Score:2)
Re:Intervall Analysis (Score:3, Insightful)
But how is that achieved, if?
I guess one would go and hunt for some arbitrary precision library for integers or some intervals lib for exact error bounds.
Think for a moment that compilers came just with integer data types and you had a to get a floating point arithmetics library every time you want to use floating point arithmetics! (I can only remember old Apple ][ integer
Re:Intervall Analysis (Score:3, Informative)
I'm sure I've read about a language where there's basically one integer type, which normally maps to a typical 32- or 64-bit value on current machines, but is subject to over/underflow tests and switches to an arbitrary precision mode dynamically. As I recall, its efficiency was comparable to an average compiled language today unless it flipped over, and obviously after flipping it got the right answe
Re:Intervall Analysis (Score:3, Informative)
Theoretically one could do the same for real numbers but it's not as easy as you think. I'm not sure a library that was both practical and fully general could be produced; reals are nasty little buggers.
In fact my intuition (normally pretty good at these things) is poking me and suggesting that it may be provable that such a library
Re:Intervall Analysis (Score:3, Interesting)
Yes, this is pretty typical in most lisp or scheme implementations (it should have been in Python too, but for some reason isn't). Testing for overflow on e.g. x86 can be done by simply testing the overflow flag. Some 20 years ago, that might have been conceived
Re:Intervall Analysis (Score:2)
Second, we need no just maintain this calculated precision value. We also need to monitor it all the time. This adds a lot of if-tests, slowing down the calculation even more.
Finally, if precision is too bad, we need to be able to rollback the current calculation. Because, if we do a calculation, and find that precision is lost beyond what is acceptable, then we need to redo the whole calculation, not just the last step. I have no idea what this will cost, but it will most likely be very expensive, and ce
Re:Intervall Analysis (Score:3, Informative)
That is exactly why you need rollback. I never intended this to be interpreted as rollback of the current opcode, it was intended to mean rollback as far as you really needed. But I agree that I didn't write it clearly. And I should have thought more about it before writing. With side-effects, such rollbacks would soon become very tricky to implement correctly. But if you want to increase precisio
Re:Intervall Analysis (Score:2)
The reason for the #define is so that you can turn the use of this library off and on without changing any code. I usually call my floats Real with a typedef so that I can change their underlying representation without a define, but you can't count on this in everyone's code.
This makes no sense. If you
Re:Intervall Analysis (Score:2)
Well, lisp is not java :-)
Are exceptions part of LISP now though?
What do you mean?
Scheme was first created in 1975. Given that scheme had continuations from the start, I think it is quite likely that people in the lisp community had at least dabbled with exception-handling mechanisms earlier. Continuations is of course the ultimate generalization of that.
I would be very surprised to hear that either Ma
Overloading...(Re:Intervall Analysis) (Score:2)
Overloading only makes sense in statically typed languages. When you have dynamic typing, the compiler can't statically determine the types of the arguments, this needs to be done at runtime (at least in the worst case, see below). The "+" function in lisp is just that, a function (although the compiler will typically inline parts of it). And you can override it (well, many implementations would disallow that for reasons of speed, but you can always
Re:Intervall Analysis (Score:2)
I would already like to brace my code with some
use_reliable_calculation {
// old code
}
declaration, or flip some compiler switch, and with minimal changes to the code have the same stuff calculated slow but safe.
After that I would like to co
Re:Intervall Analysis (Score:1)
> of the intervals community.
Both replies to "What is interval arithmetic?" gave a 404. Perhaps this answers your question: "Why is this stuff not used more widely?"
Re:Intervall Analysis (Score:2)
The world is not all float (Score:4, Insightful)
PDA level mobile FPUs are very rare indeed. In practice, devices using the ARM family processors have no hardware float support. It's thus very important for developers to understand floating point intimately, so that they won't be left at the mercy of awful compiler-emulated floating point code. Of course, in those cases most code tends to orient itself for fixed point arithmetic. Fixed point calculations are much better suited for the integer crunching power of, say, the Intel XScale.
There are also good tradeoffs developers can make between floats and fixed point, for example by using block floating point (BFP) formats, where a whole block of values shares the same common exponent.
Now that 3D is really coming [khronos.org] to mobile devices, plenty of people will get first-hand experience of emulating floating point for the first time since the 80's. :-)
Jouni
Re:The world is not all float (Score:1)
Now that 3D is really coming to mobile devices, plenty of people will get first-hand experience of emulating floating point for the first time since the 80's. :-)
I don't think so. Enough research has been done into using 3D hardware as an general purpose FPU that the next generation of PDA display chips will probably take care of this anyway (if needed at all). If the choice is between an FPU for software 3D vs real hardware 3D, PC history has shown that the better answer is the latter.
Any collegel level engineering numerical methods (Score:4, Insightful)
Hell, any decent numerical methods book should cover stuff like that as well.
Lahey on inexactness (Score:2, Informative)
Francois.
Re:Lahey on inexactness (Score:1)
Francois.
Huh? (Score:5, Insightful)
Would you mind tell us what those "issues" where. Because the articles hardly deal with "issues" at all. What they deal with is the theoretic limitations that must exist in floating point, due to the fact that we have finite hardware, while real analysis assumes infinite precision. This should not have changed between 1991 and now (especially, since we have all standardized on IEEE floating point formats, but even if the article was from 1960, you should easily be able to "translate" it to your favourite floating point format (which is probably IEEE)).
Could someone, please, give me a pointer to some newer thoughts and/or new facts surrounding floating point programming.
There are very few new thoughts with regards to floating point programming, just as there are very few new thoughts on the use of "if-then-else"-branches or "while"-loops. Floating point programming is basically a solved problem. The only problem with it is that it sometimes flies in the face of intuition, and most programmers are ignorant about it. This has not changed since 1991 either.
The articles you mentioned are very good articles for understanding issues surrounding floating point. Just make sure you read them with your brain, instead of just feeding your favourite compiler with any examples you see.
What has been improved since those articles were written?
Speed. Computers have become faster. (It's possible that there also have been some minor software improvements such as an ISO C addendum clarifying tricky areas with rounding modes, or something like that.)
What is still the same?
Essentially, nothing have changed.
How is the future, especially with the new platforms IA64 and AMD64?
Very predictable. Nothing will change there either. Non-IEEE floating point vector instructions, or "multimedia" instruction sets will probably continue to be unstandardized and platform-dependent.
I am most interested in the x86 and x86-64 architectures
There is nothing special about those architectures with respect to floating point (well, the x86 reuses its floating point registers for MMX instructions, but you shouldn't need to know that unless you use assembler).
picking nits (Score:1)
Great post, though. You're absolutely correct.
--
Re:Huh? (Score:2, Informative)
Re:Huh? (Score:2)
Well there is one thing that may be a nasty surprise: The fact that x86 processors use registers with 80 bit precisions can mean that two absolutely identical looking computations, when compiled (e.g.) with an optimizing C compiler, can lead to non-identical results. That's because just storing a result from register to memory changes the result (truncating it).
(If using GCC, you
Re:Huh? (Score:1)
This shouldn't worry you on x86 since 3DNow!, SSE and SSE2 all conform to the IEEE spec.
Re:Huh? (Score:2)
"640 K ought to be enough for anybody." -- Bill Gates, 1981
Arbitrary length (Score:2, Interesting)
Re:Arbitrary length (Score:2)
Floating point is basically a convenience for people who don't know (or don't care to work out) how accurate they need the answer to be or what the range of input will be. It was also convenient years ago when computers lacked the power to deal with multiword numeric representations. These days, unless you're doing *really* heavy number crunching, there's not much point using floats.
In fact, real numbers are a mathematical abstraction of questionable r
Re:Arbitrary length (Score:1)
News Flash: Go To considered harmful (Score:5, Funny)
IEEE FP is the peril (Score:3, Interesting)
Unfortunately, IEEE 754, the most widely used floating point standard, fixes none of the complexities of using floating point but creates many completely unnecessary complexities of its own. Many CPUs just give up and throw any kind of specialized IEEE features into software, making them nominally compliant but unusable. And many programming languages refuse to implement the inane and broken semantics specified for IEEE comparison operators.
The only good thing that can be said about IEEE 754 is that even a lousy standard is better than nothing at all. And, on the bright side, you can usually put CPUs and compilers into modes where they behave somewhat sanely (no denormalized numbers, sane comparisons, no NaNs).
It's all still true. (Score:3, Insightful)
So long as a float is still 32 bits and a double 64, you'll get about that degree of precision. It's not that the hardware is inaccurate - they all do pretty much the best they can with the information provided.
Roundoff errors and other evils of floating point representations are here to stay.
However, you can't just automatically decide to punt and use fixed point arithmetic. There is a 'tension' between dynamic range and precision. If you want reliable precision, you can't have large dynamic ranges for your numbers and vice-versa.
The biggest and best improvement we've seen since the early '90s is that doing your work in double precision is much less of a penalty than it used to be (when compared to working in single precision or integers).
With 64 bit machines, we should expect that penalty to become yet smaller.
So if speed is an issue, modern machines can be more precise - but if speed was not an issue, machines of the early '90s were every bit as precise as the latest wizz-bang 64 bit CPU. IEEE math hasn't changed much (at all?) in that time.