Is it possible to remove floating point errors without resorting to arbitrary-precision datatypes?

Question

I was wondering whether, under specific conditions, it is possible to remove floating point errors without resorting to arbitrary-precision datatypes.

The problem is the usual one. The language is Ruby, but it holds in any language:

f = 1829.82
=> 1829.82

f / 12.0
=> 152.485

(f / 12.0).round(2)
=> 152.48

Why not 152.49? Because due to the finite precision of floating points:

format("%18.14f", f)
=> "1829.81999999999994"

format("%18.14f", f / 12.0)
=> "152.48499999999999"

So the rounding is correct. Now my question is: is there a way to get the answer I want anyway, given the following circumstances: there are strong limits on the (number of) operations performed using float, the precision needed is limited to two decimal places (max 8 digits in total) and a small amount of remaining 'wrongly' rounded answers is acceptable?

The situation is such that users may enter valid Ruby strings like:

"foo / 12.0"

where foo is a number provided in the context in which the string is executed, but where '12.0' is something the user enters. Imagine a spreadsheet with some free formula fields. The strings are simply evaluated as Ruby, so 12.0 becomes a Float. I could use the ruby_parser + ruby2ruby gems to build a parse tree, mangle the datatype to Bignum, Rational, something from the Flt library, decimal floating point representations or what-have-you, but that is tricky, as the actual strings can become somewhat more complex, so I prefer not to go this way. I will go that way if nothing else is possible, but this question is specifically here to see if I can avoid that path. As such, the datatype of the 12.0 is strictly Float and the outcome is strictly Float and the only thing I can do is interpret the final answer of the snippet and attempt to 'correct' it, if it rounds the 'wrong' way.

The only calculations the users do involve numbers with a precision of two decimal digits (and at most 8 digits in total). With 'simple' I mean that the floating point errors do not get a chance to accumulate: I may add two of these numbers and divide one by an integer, but then the calculation is done, the result is rounded and stored and any subsequent calculation is based on that rounded number. Usually only one floating point error will be involved, but I think the problem does not significantly alter if two can accumulate, though the residual error rate may be larger by definition.

What may first come to mind is first rounding to 3 decimal digits, then to 2. However, that doesn't work. That would lead to

152.48499999999999 => 152.485 => 152.49

but also

152.4846 => 152.485 => 152.49

which is not what you want.

What next came to my mind is adding the smallest possible increment (which, as people have pointed out, depends on the floating point value under consideration) to a float if that nudges it over the .5 border. I'm mainly wondering how often that could result in a 'false positive': a number to which the smallest increment is added, even though the fact that it was just below the .5 border was not due to a floating point error, but because it was simply the result of the calculation?

A second option is: just always add the smallest increment to numbers, as the .5 region is the only one where it matters anyway.

Edit: I just rewrote the question to incorporate part of my answers in comments, as cdiggins suggested. I awarded the bounty to Ira Baxter for his active participation in the discussion, though I'm not yet convinced he is right: Mark Ransom and Emilio M Bumachar seem to support my idea that a correction is possible that will, in practice, in possibly a relatively large majority of cases, produce the 'correct' result.

I still have to perform the experiment to see how often the result would be correct and I fully intend to, but the time I can spend on this is somewhat limited, so I haven't gotten round to it yet. The experiment is not trivial.

Answer 1

It sounds like what you want are fixed-precision decimal numbers. A good library implementing these is going to be more reliable than hacking something together yourself.

For Ruby, check out the Flt library.

Answer 2

"it is possible to remove floating point errors without resorting to infinite precision datatypes."?

No. Floating point errors are your computer's only mistakes involving number crunching. If you remove all errors, by definition your precision is infinite.

That sounded pedantic, which was not my intention. I'm trying to point out that there is a big conceptual problem underneath your apparently technical issue. You can't correctly round incorrect numbers based on what their correct values would be, unless you know their correct values (i.e. infinite precision values, or other form of carrying that information).

Your idea of adding a small number may work out statistically, but only statistically. I suggest you write a script to test a massive number of cases with random numbers of no more than two decimal places. (The script would need to also do the math with infinite precision, in order to know the right answer to compare) That way, you can measure corrections and false positives.

Answer 3

If you are can control the amount of arithmetic (especially multiplies and divides), you can try simply scaling all your floating point values by some power scale of ten (say scale=4). You'll have to change the code do input, output, and multiplies and divides.

Then scale=2 decimal fractions such as 5.10 are stored exactly as 510. Inputs need to be entered accurately; e.g., read in the string mmm.nnnn, move the decimal place scale locations in the string (e.g., for scale=2 ==> mmmnn.nn and then convert the string to float). Addition/Subtraction of such fractional numbers is exact and doesn't need any code changes. Multiplication and division loses some "decimal" precision and needs to be scaled; code that said x*y needs to be changed to x*y/scale; x/y needs to be changed to x*scale/y. You'll can round the string at the scale point and then output it.

This answer is the cheesy version of using a real decimal arithmetic package, mentioned by another poster.