The Trouble With Rounding Floats

lukfil writes "We all know of floating point numbers, so much so that we reach for them each time we write code that does math. But do we ever stop to think what goes on inside that floating point unit and whether we can really trust it?"

Decimal Arithmetic

[(1+-sqrt(5))*(2**-1) (868173)]

From TFA:

Example 1: showing approximation error.

// some code to print a floating point number to a lot of
// decimal places
int main()
{
float f = .37;
printf("%.20f\n", f);
}

The main problem with that example, I take it, is that single-precision datatypes are only guaranteed for roughly seven decimal places; using double, of course, only defers the problem.

What about encoding floats as a pair of ints or longs: one to express the numerical value, and the other its tenth power; id est, decimal arithmetic [ibm.com]?

Re:Decimal Arithmetic

[by Anonymous Coward]

This is not newsworthy. This is computer science 101.

Re:Decimal Arithmetic

[Duhavid (677874)]

It is a little newsworthy.

I bothered to ask the question of what to use for monitary
usage at a financial institution in my recent past. I was
a bit ( pardon the pun ) suprised to get a blank stare, to
have to explain what I was talking about. Floats where good
enough. Course, I had a problem in .net with iterating thru
a list of values ( testing, each was .1, for 10% ), and the
sum wasnt 1.0. Had to do a bunch of

decimal.parse(value.ToString())

to get things to sum up correctly.

Re:Decimal Arithmetic

[modeless (978411)]

Floats where [sic] good enough. [...] Had to do a bunch of

decimal.parse(value.ToString())

to get things to sum up correctly.

Oh god. Please tell us which financial institution you worked for so we can all avoid it like the plague.

Re:Decimal Arithmetic

[innosent (618233)]

For the uneducated, the reason that this is stupid is that IEEE-754 floating point numbers cannot REPRESENT all values, they APPROXIMATE them. There is no way to properly represent the value 0.01 as a float (0.01 is best approximated by 3C23D70A, or 9.9999998e-3). So, for instance, if you were to add up 100 pennies, you would have 99.999998 cents, not 100. Repetitive additions (like credits and debits from an account) or multiplications (interest calculations, amortizations, etc.) simply make the problem worse, which is why floats should NEVER be used to track money. A fixed decimal system should always be used for financial systems.

Re:Decimal Arithmetic

[DeadChobi (740395)]

I believe that we solved that problem in my first Computer Science course by using Integers and long integers. Essentially we took the monetary value, turned it from dollars into cents for calculation, then back into dollars for output. The only error would be in our method of using division for conversion, which could have been remedied by some other methods I can think of which are probably solved by much better people than I.

Re:Decimal Arithmetic

[innosent (618233)]

no, although a double or larger increases the precision, all floating point-style numbers suffer from this problem. You might get away with it for a larger number, but you are wasting bits, and stil cannot guarantee that the number is always going to be accurate. In addition, as the number gets larger, more precision is lost. For instance, 782533.37 as a float is 493F0C55, or 782533.31, and as a rounded float is 493F0C56, or 782533.38. Neither would be acceptable, and even a double will lose precision at about 16 significant digits, which could be a problem for daily interest calculations or another high-precision calculation. What should be used is a packed decimal (BCD) or fixed decimal (int or long and an associated scale factor). The whole point is that for a financial institution, there is likely a fixed precision level that is acceptable, but floats, doubles, etc., cannot guarantee that any given precision will be maintained, as it depends upon all of the factors involved (value and size of each number in the calculation). For the same reasons, floating point numbers should never be used in program flow control, either, as doing a for(float x = 0.0; x 1.0; x = x + 0.01) will iterate 101 times, since the first time x is not less than 1.0 is when it reaches 1.00999..., and if you are looking for a specific value, it may never reach it (like for(x = 0.0; x != 1.0; x = x + 0.01)). If you instead assume that you will always deal with 2 decimal places (or 3, or whatever), you can guarantee that your addition or multiplication will be accurate, and can scale the answer later if necessary.

Re:Decimal Arithmetic

[Eivind (15695)]

There's other funkyness too, besides the precision. For example, if you're adding up a lot of floating-point numbers, it makes a difference what sequence you do the additions in.

For example, if your input consist of one large number, and tons of small ones, then rounding-errors mean that starting with the large number gives a much smaller result than starting with the small ones.

If I scale it down to smaller numbers, you see why:

1.0*10^5 + 1.0*10^1 = 1.0*10^5

So, adding a "small" number to a "large" number gives you simply the large number.

If you repeat this, a million times, your result is still simply the large number.

So you could end up concluding that 1.0*10^5 + (1.0*10^1 + 1.0*10^1 ..[1000000 times]...) = 1.0*10^5

That is an order of magnitude wrong. The correct result is 1.1*10^6

Practical result ? You need to think about your input. If it *may* look like this, you need to add up by repeatedly adding the two smallest numbers. Easy to do with a priority-tree. pseudocode like this:

• Insert all numbers in priority-tree.
• Extract two smallest numbers from tree.
• Add the two numbers, producing a new number.
• Push this single new number into the tree.
• Repeat from step 2 until you're left with a single number.

MS-Excel, by the way, does *NOT* do this in it's SUM() function, if you feed it a "large" number and *many* "small" numbers, you get horrendously wrong results. Because of the relatively high precision of floats and doubles though, you need to use larger numbers than in my example here.

Error diffusion is another way.

[DrYak (748999)]

On solution as you put, is to priority sort your operations.

Another solution, is the Kahan summation algorithm [wikipedia.org].
Wich, grosso-modo, keeps track of the error at each step, and injects it back at the next.
In your example, in each iteration, the algorithme notice that tha 1.0e1 is missing from the sum and carries it to the next addition. A few iterations later, the carry is big enough to be added to the result.

The advantages are : you don't need to first load all components in a tree, then itteratively sort them and process them all until you're done. In fact you can even use this algorithme in a streaming fashion, were you don't enven need to know how much value will come.

The disadvantages are : some compilers are able to guess that the carry "should mathematically be 0" (actually true in a perfect world with infinite precision numbers) and could "optimise" the code back to a plain normal sum function bypassing the algorithm (and won't subsequently use any other sum-correction algorithm).

Re:Decimal Arithmetic

[StressedEd (308123)]

I suspect you will end up having to avoid most of them.

Friends of mine went off to work "In The City", when I quizzed them about their use of numbers for stock prices etc they were equally dismayed that things were being passed around as doubles. Often encoded as ASCII text in data streams as well, requiring different people to write their own ASCII->DOUBLE conversion depending on the representation of the stock tick. I think this kind of madness is quite prevelant.

As someone else pointed out, if you want to do things properly you can end up needing very big integers.

Perhaps the best option is to make sure people can only by and sell equities etc in numbers that can be exactly represented as doubles on a computer. It sounds crazy, but it's not as crazy as it looks. One of the reasons stocks etc are quoted as they are is probably due to the ease of the mental arithmetic.

Kudos to the parent of your post. At least he knows what he is having to do is dodgy and cares enough to check!

Re:Decimal Arithmetic

[johnw (3725)]

Friends of mine went off to work "In The City", when I quizzed them about their use of numbers for stock prices etc they were equally dismayed that things were being passed around as doubles.

I'd be not only dismayed but very surprised to find anything which interfaces to the London Stock Exchange passing stock prices around as doubles, or as any other kind of floating point number.

The LSE feeds all use 18 digits for values, with the first 10 being implicitly before the decimal point and the remaining eight being after the implicit decimal point. This is very handy because it means all the values can be manipulated using 64 bit integers. The LSE rules also state very precisely how rounding must be handled. If you try to submit a multi-million pound deal and your calculation of the consideration is out by just one penny then the deal will be rejected.

No-one with the slightest clue about how to code would use floating point maths in any kind of financial program, particularly not one where they're working with the LSE.

Re:Decimal Arithmetic

[johnw (3725)]

Are there any people in financial institutions that can comment (anonymously) on this?

I'm happy to comment on it without being anonymous. I designed and oversaw the implementation of the LSE feeds (to and from) for the stockbroking part of a large UK high street bank which shall be NatW^H^Hmeless. If you tried to implement the internals using floating point arithmetic it would be pretty much impossible to get it to pass the LSE's conformance tests, which all assume you will use integer arithmetic and explicit rounding according to their rules.

Re:Decimal Arithmetic

[Bender0x7D1 (536254)]

Exactly. Unfortunately, there are too many people out there who are programmers, even good ones, who don't know, or understand, the basics. While I'm not claiming that formal education is the only way to get the knowledge you need, it is a good way to avoid gaps in your knowledge. I hated some of the computer science classes I had to take, but I did learn something important in each and every one of them.

Another advantage in the formal classes is you get the theory that allows you to make decisions on what data types to use and when. Sometimes you need the precision of BigNum systems, (crypto for example), and sometimes the accuracy of float is enough. For example, in a lot of financial applications, float would be good enough since 2 decimal places is enough. If you need performance, float will beat any BigNum system hands down. However, if you are dealing with decimals on top of decimals, (such as calculating someone's dividend from a mutual fund where they own partial shares), you might need BigNum. Either way, with the proper theory and good understanding of the formats, you can make these decisions.

These situations are why I am a big supporter of actual software engineering instead of programming. Sure, standard programming is great for a lot of situations, but serious applications need to use software engineering practices. You wouldn't build a bridge without an engineer, so why build an application that handles billions of dollars without applying the same rules and principles?

Re:Decimal Arithmetic

[gweihir (88907)]

These situations are why I am a big supporter of actual software engineering instead of programming. Sure, standard programming is great for a lot of situations, but serious applications need to use software engineering practices. You wouldn't build a bridge without an engineer, so why build an application that handles billions of dollars without applying the same rules and principles?

I could not agree more. The issue is not to get it done fast or cheap. The issue is that the person designing the solution d

Re:Decimal Arithmetic

[tomstdenis (446163)]

My college taught "numerical analysis" in the software comp.eng side. You learn the format of IEEE types, the range, accuracy, precision issues, etc.

We had assignments to not only perform matrix ops but also give the expected error, etc.

Maybe the author of the article should either go to a better school or pay more attention to the classes.

Tom

Re:not really

[Anonymous Brave Guy (457657)]

The first paper recommended for learning more about floating point arithmetic is usually Goldberg's famous What Every Computer Scientist Should Know About Floating-Point Arithmetic [sun.com].

I can't remember whether the paper specifically discusses the failure of floating point arithmetic to obey the mathematical laws of arithmetic, but even if not, the background it provides is probably enough for you to understand the reasoning yourself.

Re:Decimal Arithmetic

[Anomie-ous Cow-ard (18944)]

Since these are computers, and they deal primarily with binary internally, why not store the numerical value and the 2nd power instead? Oh, and since we generally need more bits of accuracy in the numerical value than the exponent (do you often deal with numbers 2**(2**32)?), why not allocate a "reasonable" number of bits to the exponent and leave more for the numerical value.

Uh oh, we just re-invented floating point. Oh well, nice try.

If you were just trying to get better accuracy by using base 10 rather t

Re:Decimal Arithmetic

[gstoddart (321705)]

Since these are computers, and they deal primarily with binary internally

Last I checked, they use binary internally exclusively, not primarily. ;-)

Unless things have changed and nobody told me. :-P

Cheers

Re:Decimal Arithmetic

[SageMusings (463344)]

Okay,

Show of hands: Who did not already understand that floats are approximations? Anyone? I didn't think so. I've gotta wonder why this story ever made it into Slashdot. This is more worthy of Time magazine where it can be spun as a startling new revelation into the dirtier corners of computer science and foisting a lie on the public.

Why I only use decimal values

[eliot1785 (987810)]

This is why I use DECIMAL and not FLOAT in MySQL. Problem solved. I'm not a big fan of floats, the extreme precision that they seem to have is mostly an illusion.

Re:Decimal Arithmetic

[gweihir (88907)]

Is there any fundamental reason why decimal arithmetic in a computer should be more accurate than binary arithmetic in a computer?

No, no, the problem is not with the precision! The problem is that when input and output is decimal, but the calculation is binary, then you get additional errors from the conversion that badly educated programmers do not expect.

Re:Decimal Arithmetic

[k8to (9046)]

It's worse than that. In some kinds of calculations, the error can be so large that the result is entirely meaningless. That is, for example when doing a subtraction between two nearly equal floating point values, both of which were approximated, the result may have more noise than signal. This isn't the usual case, but when writing general code that cares about precise values, you can code yourself a beartrap that only springs in rare circumstances.

There is an excellent article about all of this detail, linked from TFA at sun: http://docs.sun.com/source/806-3568/ncg_goldberg.h tml [sun.com]

Granted, I have never written any code where this matters, but I had never realized really just how bad some of the implications are in some cases.

Re:Decimal Arithmetic

[Fordiman (689627)]

No, C will automatically recast a number as needed in cases like the above.

The issue is actually a pretty commonly understood situation when going from decimal floating point numbers to binary IEEE floats (I have another comment on here describing how they're stored), and it basically comes down to this:

Floats of any sort are stored as an int with an int shift (a.aa x b^c). As such, there will be aliasing problems based on the prime components of b. A known percentage of divisors will produce repeating numbers. For example, any division of 3,5,7,11.... in base 2 will be repeating. Any division of 3,7,11,13... in base 10 will be repeating.

No, there's nothing you can do about it. Use higher precision if needed, and otherwise get over it.

decNumber libary from IBM

[Not The Real Me (538784)]

This is why I use the decNumber library from IBM.

http://www2.hursley.ibm.com/decimal/decnumber.html [ibm.com] The decNumber library implements the General Decimal Arithmetic Specification[1] in ANSI C. This specification defines a decimal arithmetic which meets the requirements of commercial, financial, and human-oriented applications.

The library fully implements the specification, and hence supports integer, fixed-point, and floating-point decimal numbers directly, including infinite, NaN (Not a Number), and subnormal values.

The code is optimized and tunable for common values (tens of digits) but can be used without alteration for up to a billion digits of precision and 9-digit exponents. It also provides functions for conversions between concrete representations of decimal numbers, including Packed Decimal (4-bit Binary Coded Decimal) and three compressed formats of decimal floating-point (4-, 8-, and 16-byte).

Re:decNumber libary from IBM

[piranha(jpl) (229201)]

Rational number arithmetic is a more general solution. Any number that can be expressed in decimal or floating-point notation is rational; any rational number can be expressed as (n/d), where n and d are integers. We have "bigints;" unbounded-magnitude integers constrained only by the memory of the computer they are stored on. Rational numeric data types pair two bigints together to give you unbounded magnitude and precision, and have been implemented for decades.

They probably aren't directly supported in your favorite programming language because they are slow to work with when you need very high precision; after each calculation, the rational number needs to be reduced to its lowest terms. This involves factoring, which takes time proportional to the the terms themselves.

Consider the use of integers, floats, or decimals only as an optimization when it has been shown that an application is suffering a serious performance hit because of rational arithmetic, and when you can use a faster data type knowing that your program will perform within accuracy goals.

For 90% of computing problems, monetary calculations included, you shouldn't even have to worry about what numeric type you're using. Your language should assume rationals unless told otherwise. Common Lisp, Scheme, and Nickle do exactly that.

C developers can use GMP [swox.com]. Other developers can use one of many bindings to GMP.

I am Intel of Borg

[www.sorehands.com (142825)]

I am Intel of Borg, you will be approximated.

There have been many examples, such as the original pentium bug. Of course, there was a bug in Windows Calc, it was 2.01 - 2.0 = 0 (If I remember correctly).

The author is seriously confused

[mlyle (148697)]

Apparently the author of the article didn't read the stories in RISKS that he cited. In particular, the 'pensioners being shortchanged' one talks about them not being paid interest on 'float'-- cash flow on transactions in progress. This has little to do with floating point numbers.

Similarly, the spacecraft problem mentioned is one of an errant cast, not because of dilution of precision in floating point calculations.

The author could really pick his examples better-- as mistakes in numerical programming happen often and are often of great import.

Re:The author is seriously confused

[mlyle (148697)]

Sources for the above:

Pensioners shortchanged of 'float' [ncl.ac.uk]

Ariane casting problem (float -> 16 bit int) [ncl.ac.uk]

Re:A good example of the evils of math.

[codegen (103601)]

Part of the problem there was that the missile's clock values were such that they would not convert to base 2 (and hence to float) accurately and so the tracking was off

Actually the problem was that they used a float to store the system time (time since power on) in the ground radar unit. It allowed the clock to be used in calculations without a conversion. A float will store an integer just fine (and accurately) until the number gets too large and then the units part drops off the bottom of the precision and the increment operator no longer makes any sense. This was a design decision that made sense for the role for which the missle platform was originally designed. The patriot was originally designed to be used in the European Theater (if the cold war ever turned hot) and as such would never remain in one location for more than a very few days.The clock is reset everytime they move the battery (they power off the ground tracking radar when they move). The use in the gulf war was in a strategic role (not tactical) which kept them continuously operating in a single location for long periods of time, and the shortcut they used came back to haunt them (as usual). If they had reset the system every few days, the problem would not have occured.

Not news.

[SJasperson (811166)]

This is not a new problem. Or an unsolved one. Is there any modern programming language that does not supply a data type or library with exact decimal arithmetic support? Using a float to represent monetary amounts and expecting them to be free of rounding errors is as stupid as using integers to store zip codes and wondering where the leading zeros went from all the addresses in New England. If you can't be arsed to choose the right data type get out of the business.

Re:Not news.

[mcrbids (148650)]

Using a float to represent monetary amounts and expecting them to be free of rounding errors is as stupid as using integers to store zip codes and wondering where the leading zeros went from all the addresses in New England.

Hrrmm, well...

That would explain our lack of customer response in New England...

Re:Not news.

[Jerry Coffin (824726)]

If you're dealing with amounts of cents that could possibly start overflowing even a 32-bit int (that is, billions of cents, or tens of millions of dollars), then the application's important enough to be worth the cost of further research on the matter.

...especially when you can find roughly 10 gazillion alternative for about $1 worth of research time.

Unfortunately, most of the obvious alternatives are either somewhat restrictive, or have relatively poor performance. For example, on a 64-bit machine

science; business

[bcrowell (177657)]

He talks about scientific applications, but actually very few scientific calculations are sensitive to rounding error. Remember, they sent astronauts to the moon using slide rules. Generally for scientific applications, you just don't want to roll your own crappy subroutines for stuff like matrix inversion; use routines written by people who know what they're doing. (And know the limitations of the algorithm you're using. For example, there are certain goofy matrices that will make a lot of matrix inversion algorithms blow chunks.)

For business apps, the classic solution was to use BCD arithmetic. But today, is it more practical (and simple) just to use a language like Ruby, that has arbitrary-precision integers, so you can just store everything in units of cents? A lot of machines used to have special BCD instructions; do those exist on modern CPUs?

Re:science; business

[Jeremi (14640)]

But today, is it more practical (and simple) just to use a language like Ruby, that has arbitrary-precision integers, so you can just store everything in units of cents?

Hmm.... if you use integers of any given finite precision, aren't you still subjecting yourself to round-off error? (e.g. ((int)4)/((int)3) == 1!!) On the other hand, if you use a string-based infinite-precision datatype, what happens when you try to compute an non-terminating number (e.g. 1.0/3.0)? Perhaps your program crashes after tr

This is not a "problem" per se

[Null Nihils (965047)]

float (and the big brother double) is inaccurate. Its no surprise. A 32-bit Float is but a single simple tool in a programming language. If anyone is surprised by how Floats behave then they are, most likely, inexperienced.

You don't start addressing a problem in software just by assuming Float or Double will magically fill every need. An experienced programmer needs to have a knowledge of how to use, and how not to use, the programming tools at hand. TFA about floating point numbers is very introductory (at the end it mentions that the next article will tell us how to "avoid the problem"... I assume it will go on to cover some basic idioms.) In a way it misses the point: Floating-point rounding is not a "problem". Floats and Doubles always do their job, but you have to know what that job is! The behaviour of floating point numbers should not be a big surprise to a seasoned coder.

For example: You can't use float or double to store the numerical result of a 160-bit SHA-1 hash... you have to use the full 160 bits. (Duh, right?) So, if you use a mere 32 bits (float) or 64 bits (double) to store that number, you are going to sacrifice a lot of accuracy!

Re:This is not a "problem" per se

[Wonko the Sane (25252)]

A much better article is linked from this one near the bottom: what every computer scientist should know about floating-point arithmetic [sun.com]

Numbers and bases

[Todd Knarr (15451)]

We have the same problem in everyday numbers. Try representing 1/3 in any finite number of digits. You can't. The big thing about floating-point numbers that trips people up is that we're used to thinking in base 10. Floating-point numbers in computers typically aren't in base 10, they're in base 2. The rounding problem he describes is simply us getting confused and wondering why a fraction with an exact representation in base 10 doesn't have an exact representation in base 2. The obvious solution is the one he alludes to at the end: don't use base 2. Computers have had base-10 arithmetic in them for decades, in fact the x86 family has base-10 arithmetic instructions built in (the packed-BCD instructions). COBOL has used packed-BCD since it's beginning, which is why you don't find this sort of calculation error in ancient COBOL financial packages running on mainframes.

Re:Numbers and bases

[tawhaki (750181)]

Try representing 1/3 in any finite number of digits.

0.3. All you need is base 9 :)

Re:Numbers and bases

[flibbajobber (949499)]

Try representing 1/3 in any finite number of digits. You can't.

"1/3"

You can. I just did. So did you. In base-10, even. In fact, the answer is the same for base-4 or higher. Using only two digits, "1" and "3". Any rational number can be represented using a finite number of digits, using... (wait for it) a RATIO.

(Represent one-third in Base 2? why that would be "1/11". One-third in Base 3 would be "1/10".)

It used to be much worse. Kahan fixed it.

[Animats (122034)]

Due to the efforts of Willam Kahan [berkeley.edu] at U.C. Berkeley, IEEE 754 floating point, which is what we have today on almost everything, is far, far better than earlier implementations.

Just for starters, IEEE floating point guarantees that, for integer values that fit in the mantissa, addition, subtraction, and multiplication will give the correct integer result. Some earlier FPUs would give results like 2+2 = 3.99999. IEEE 754 also guarantees exact equality for integer results; you're guaranteed that 6*9 == 9*6. Fixing that made spreadsheets acceptable to people who haven't studied numerical analysis.

The "not a number" feature of IEEE floating point handles annoying cases, like division by zero. Underflow is handled well. Overflow works. 80-bit floating point is supported (except on PowerPC, which broke many engineering apps when Apple went to PowerPC.)

Those of us who do serious number crunching have to deal with this all the time. It's a big deal for game physics engines, many of which have to run on the somewhat lame FPUs of game consoles.

This is why you would choose...

[jd (1658)]

One of the many many solutions:

• Fixed-point numbers
  
• Berkeley MP or Gnu MP arbritary-length floating-point
  
• Co-processors with truly massive internal registers (I refuse to use less than 80-bit)
  
• Delayed calculation (ie: actually process a calculation at the end, storing the inputs and operators until you absolutely need the value - eliminates intermediate rounding errors and if the value is never needed, you don't waste the clock cycles)
  
• Don't use real numbers - apply a scaler or a transform such that ALL components of any scaled/transformed calculations must be integer, then only transform back for display purposes
  

The use of transforms for handling numerical calculations is an old trick. It is probably best-known in its use as a very quick way to multiply or divide using logarithms and a slide-rule, prior to the advent of widely-available scientific calculators and computers. Nonetheless, devices based on logarithmic calculations (such as the mechanical CURTA calculator) can wipe the floor with most floating-point maths units - this despite the fact that the CURTA dates back to the mid 1940s.

Re:This is why you would choose...

[philipgar (595691)]

logarithmic number systems (LNS) for computers were first proposed by Marasa and Matula in 1973, as a "better" approximation of numbers than floating point units. This paper compared the cumulative error from different floating point standards with LNS standards. LNS offers some advantages over floating point, however it's performance degrades significantly as you add more bits of precision.

LNS can be effective to around 24bits of precision, and then the hardware requirements for the LNS unit's adder/subtracter become too overwhelming. This is because multiplications and divisions are fast on LNS units (with minimal hardware) as just require an adder, however handling subtraction is much more difficult. The simplest (naive) methods of making an adder and subtractor involve using large ROM lookup tables. Fancier, more efficient units using smaller roms and small multipliers to help get better values (I don't remember all the details offhand). Sometimes they'll even trade precision for faster performance. This can result in chips with single cycle multiplies and divides, but multi-cycle additions and subtractions. For low precision calculations requiring many divides and multiplies LNS processors can often achieve the best performance. However for many applications an efficient LNS unit with sufficient precision just isn't practical.

Phil

Bah. Author doesn't understand arithmetic.

[swillden (191260)]

The author goes on and on about how floating point numbers are inaccurate, and unable to precisely represent represent real values, like this is something new, or even something different from the number approximations we normally use.

The reason the examples the author cites can't be represented precisely is that floating point numbers are ultimately represented as base-2 fractions, and there are a bunch of finite-length base-10 fractions that don't have a non-repeating base-2 representation. Guess what? We have *exactly* the same problem with the base-10 fractions that everyone uses all the time. Show me how you write 1/3 as a decimal!

The problem isn't that floating point numbers are inherently problematic, the problem is that we typically use them by converting base-10 numbers to them, doing a bunch of calculations and then converting them back to base 10. Floating point rounding isn't an unsolved problem -- floating point rounding works perfectly, and always has. It's just that the approximations you get when you round in base 2 don't match the approximations you get when you round in base 10.

Bottom line: If you care about getting the same results you'd get in base 10, do your work in base 10. This is why financial applications should not use floating point numbers.

Must read floating-point articles

[emarkp (67813)]

What every computer scientist should know about floating point numbers (HTML [sun.com], PDF [loria.fr]).

and

When bad things happen to good numbers [petebecker.com] (as well as Becker's other floating-point columns on that same page)

Comp Sci 101

[syousef (465911)]

Welcome to a very poor article on what's been taught in early Comp Sci for many many years.

Any serious developer of business software knows all about this and avoids floating point at all cost for financial calculations. Scientists however do use them carefully since the math they do is usually much more performance (speed) sensitive and the calculations are a little more complex than what tends to be done on the business side (ie _most_ business calcs are relatively simple).

Old news, but an unsolved problem

[Opportunist (166417)]

And I'm not sure if it can be solved altogether. When you spend a little time meditating over the IEEE 754, you notice a few flaws. The first and most obvious is, of course, that, no matter how precise you want to make it, somewhere there's a cutoff. And, especially when you multiply with floats, that error grows as well. But there's another problem. Two actually.

The first one is the one mentioned in the article, and something everyone who didn't sleep through his IT classes should know: Computers calculate binary, and converting floats from binary to decimal isn't possible without error. There is no way to represent 0.37 in binary, in IEEE754. No matter how many bits you spend on the mantissa. Now, you can argue that, if you make it "big enough", it doesn't matter anymore since it's well within the error margin and when you round it to, say, 5 after decimal, the error vanishes. True. But when you start calculating, when you multiply or, worse, exponentiate, the error grows in big leaps.

Another, less obvious, problem is hidden underneath the way the IEEE754 works: Your error grows as your numbers grow. This might seem obvious, but it is interesting how many people overlook this flaw and problem in everyday life. Since according to the IEEE754 standard, real numbers are stored as exponent and mantissa, if you're dealing with BIG numbers, a fair deal of your mantissa is spent on the "pre-comma" part of your number, so you're losing precision. You can't reliably say that "a double is good for 5 behind dot, no matter what", you have to take into account how many of those precious mantissa bits are spent before you even get to ponder what's left for your precision.

This isn't so much a problem of processors. It's a problem of people understanding how their processors work.

The problem is using floating point improperly

[Myria (562655)]

GIMPS [mersenne.org] looks for Mersenne primes. This is clearly an exact integer operation. However, for speed, they use Fast Fourier Transforms [wikipedia.org] to do the big squaring operation with floating point. Obviously, they need an exact result.

The trick is to carefully calculate exactly how much error each operation can generate. It is possible to know exactly how many bits of your result contain valid information. If you need more accuracy, you can split it into multiple operations. As long as the final accumulated error in their result is less than .5, you have the integer answer they need. Note that it's basically impossible to do this without using assembly language, because the order of operations and subexpression elimination definitely matter.

Another interesting problem occurs with floating point results. You cannot expect the complete answer to be exactly identical on all machines. Even on the same machine, compiler settings affect the answer: x87 differs significantly from SSE. If you are doing something that needs bitwise identical results on all machines, you need to either implement it with integer math, or do what GIMPS does and do error tracking.

Melissa

Re:The problem is using floating point improperly

[ponos (122721)]

This is clearly an exact integer operation. However, for speed, they use Fast Fourier Transforms to do the big squaring operation with floating point. Obviously, they need an exact result.

All serious bignum libraries use (or should use!) the FFT to multiply very big numbers. This has been studied extensively (see Knuth The Art of Programming vol 2, for example) and is the fastest way to multiply. The general idea is that after the transform you can multiply in O(N), which is much faster than the naive O(N*N) one would expect from a simplistic digit-by-digit approach.

P.

rounding algorithms

[trb (8509)]

If you're interested in rounding (and who isn't?) you might want to read An introduction to different rounding algorithms. [pldesignline.com]

Re:Obligatory

[andrewman327 (635952)]

You beat me to it. I was just thinking about how much better TFA would be if they explained the specifics of how the Office Space team ripped off the banking system.