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?"

Comments

Decimal Arithmetic

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

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?

Re:Decimal Arithmetic

[Anonymous Coward]

This is not newsworthy. This is computer science 101.

Re:Decimal Arithmetic

[SageMusings]

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.

Re:Decimal Arithmetic

[Bender0x7D1]

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]

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

[Fordiman]

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.

Re:Decimal Arithmetic

[innosent]

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

[Eivind]

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.

Re:Decimal Arithmetic

[StressedEd]

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]

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]

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.

decNumber libary from IBM

[Not The Real Me]

This is why I use the decNumber library from IBM.

http://www2.hursley.ibm.com/decimal/decnumber.html 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).

I am Intel of Borg

[www.sorehands.com]

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]

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.

Not news.

[SJasperson]

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]

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...

science; business

[bcrowell]

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?

Numbers and bases

[Todd Knarr]

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.

It used to be much worse. Kahan fixed it.

[Animats]

Due to the efforts of Willam Kahan 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]

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.

Bah. Author doesn't understand arithmetic.

[swillden]

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.

Comp Sci 101

[syousef]

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).

Re:A good example of the evils of math.

[codegen]

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.

The problem is using floating point improperly

[Myria]

GIMPS looks for Mersenne primes. 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.

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