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

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

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.

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

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