News for hackers. Stuff that matters.
Re:0.30000000000000004 by mkup on Sunday April 02, 2017 @03:49PM (#14018677)
Once I wrote a library for double-to-string conversion and vice versa, which handles such roundings nicely: https://github.com/mkupchik/dconvstr

Key idea is not just to map binary floating point value X to a decimal floating point value Y, but instead (in extended precision, with 64-bit mantissa) compute an interval of decimal floating point values [Y1, Y2] which maps back to X (in standard precision, with 53-bit mantissa). Then choose such Y from [Y1, Y2] that Y has the shortest decimal representation.

Re:0.30000000000000004 by TazeTSchnitzel on Sunday April 02, 2017 @06:04PM (#14019298)
The state-of-the-art is the Errol algorithm of Adrysco, Jhala and Lerner (2016), which is proven to be always correct: https://cseweb.ucsd.edu/~lerner/papers/fp-printing-popl16.pd...
Re:0.30000000000000004 by floitsch on Monday April 03, 2017 @07:58AM (#14022105)
I'm the author of Grisu. (http://github.com/google/double-conversion and http://florian.loitsch.com/publications/dtoa-pldi2010.pdf)

Grisu is also proven to be always correct. As mentioned in another comment: you have to define "correct". Grisu is always accurate, but may bail out if you need the shortest or closest result.

Basically: Grisu will always print a number that reads back to the input. However, it may not be able to print the shortest or closest number (when two decimal outputs have the same shortest length). In that case, it knows this, though, and can tell the user.

I would say that the combination of Grisu and Errol is currently the state of the art.

Errol is not the fastest, nor is it (afaik) proven to always return the closest result.

However, combining Grisu with Errol (as fallback) would probably yield the fastest complete algorithm.

Re:0.30000000000000004 by willlll on Sunday April 02, 2017 @07:23PM (#14019620)
https://github.com/marcandrysco/Errol

> Our original evaluation of Errol against the prior work of Grisu3 was erroneous. The evaluation indicates a 2x speed improvement over Grisu3. However, corrected performance measurements show a 2x speed loss to Grisu3.

Re:0.30000000000000004 by TazeTSchnitzel on Sunday April 02, 2017 @08:18PM (#14019832)
Yeah, it's unfortunately not the fastest algorithm known, despite what was originally thought, but it is still the fastest accurate one.
Re:0.30000000000000004 by simonbyrne on Monday April 03, 2017 @02:02AM (#14020883)
Grisu isn't accurate?
Re:0.30000000000000004 by floitsch on Monday April 03, 2017 @07:52AM (#14022083)
Author here.

Grisu is accurate, but not always optimal. However, it figures out when that happens and lets you bail out to a slower algorithm when that happens. If you want full speed you should use Grisu, and then use Errol as a bailout.

A bit more context: there are 3 important properties when printing floating-point numbers.

- accurateness: you want the printed number to read back to the same number.

- shortness: often you want the shortest decimal representation: "0.3" and not "0.2999999999999999889". The latter is more precise, but reads back to the same number as "0.3".

- closeness: given two decimal representations of the same length, you prefer the one that is closer to the actual number.

I call the combination of these three properties "optimal".

Note that shortness and closeness are not always crucial. For example, a json-encoder could easily drop those, if the encoding is faster without them. Also, some languages drop shortness in favor of printing something closer to the input.

Grisu always produces accurate results. However, it sometimes can't tell if it already has the shortest and closest number. However (by being conservative) it can tell the user when that happens. In that case, one can fall back to another complete algorithm.

The double-conversion library (http://github.com/google/double-conversion) does exactly that. It uses the slower bignum algorithm in these cases.

Re:0.30000000000000004 by murkle on Monday April 03, 2017 @04:19AM (#14021315)
Re:0.30000000000000004 by jacobolus on Sunday April 02, 2017 @03:56PM (#14018718)
Python does this, for example (but likely in a more efficient way): http://bugs.python.org/issue1580

See also http://www.netlib.org/fp/ http://web.archive.org/web/20060908072403/http://ftp.ccs.neu...

So for instance 0.29999999999999993 + 0.00000000000000003 -> 0.3, but 0.30000000000000002 -> 0.30000000000000004

Note that this will still not solve the 0.1 + 0.2 problem from the OP, since the nearest float to 0.3 is not actually the same as the nearest float to 0.1 + 0.2.

Re:0.30000000000000004 by amelius on Sunday April 02, 2017 @04:42PM (#14018939)
> Note that this will still not solve the 0.1 + 0.2 problem from the OP, since the nearest float to 0.3 is not actually the same as the nearest float to 0.1 + 0.2.

Interval arithmetic can be used, although that requires double the storage for all the intermediate results, and extra work.

For example, .1 can be represented by x=[x0, x1], where x0 and x1 are floating point values bracketing .1, and similarly .2 can be represented by y=[y0, y1].

Then z=[z0, z1] can be computed by "z=x+y", where the interval z respects the sum of both intervals x and y.

When printing, you can determine the smallest representation within the interval z.

I'm not sure if it's worth all the trouble though :)

Re:0.30000000000000004 by kccqzy on Sunday April 02, 2017 @10:36PM (#14020238)
Interval arithmetic is far from trivial. 1/(1/x+1/y) is not the same as xy/(x+y). It breaks things more than normal floating point math does.
Re:0.30000000000000004 by danbruc on Sunday April 02, 2017 @06:02PM (#14019289)
This unfortunately breaks with something like [+1, +1] / [-1, +1] which yields (-∞, -1] and [+1, +∞), the result falls into two separate intervals. Now you can either turn this into (-∞, +∞) or use sets of intervals instead of single intervals. The first option gives pretty useless results, the second one can become really slow and consume a lot of memory. You can make this work, but you have to be really careful what you are calculating and how you are doing it.
Re:0.30000000000000004 by daurnimator on Sunday April 02, 2017 @08:41PM (#14019892)
> The first option gives pretty useless results

Does it though? Wouldn't a result of `(-∞, +∞)` be a solid indication to go and reduce the range of your input parameters?

Re:0.30000000000000004 by sametmax on Monday April 03, 2017 @03:17AM (#14021122)
But Python also warns about it in the documentation, and provide the factions (https://docs.python.org/3.1/library/fractions.html) module and the decimal module thttps://docs.python.org/3.1/library/decimal.html) in the stdlib to avoid the problem.
Re:0.30000000000000004 by int_19h on Monday April 03, 2017 @05:26PM (#14027316)
One thing I really wish Python had is decimal literals. I mean, it does have imaginary literals, which is arguably more of a corner case...
Re:0.30000000000000004 by FabHK on Monday April 03, 2017 @01:44PM (#14025137)
> the nearest float to 0.3 is not actually the same as the nearest float to 0.1 + 0.2.

Or even more precisely, the nearest float to 0.3 is not actually the same as the nearest float to (the nearest float to 0.1) + (the nearest float to 0.2).

Re:0.30000000000000004 by dietrichepp on Sunday April 02, 2017 @03:57PM (#14018721)
That's basically how Gay's dtoa works, and you'll find it copied into many projects—Python, for example, uses it for repr().

http://www.netlib.org/fp/dtoa.c

Re:0.30000000000000004 by Avernar on Sunday April 02, 2017 @07:51PM (#14019742)
I've long ago stopped using C's standard library floating point routines and use Gay's code. Main reason was inconsistencies between compilers.
Re:0.30000000000000004 by floitsch on Monday April 03, 2017 @08:04AM (#14022129)
There is also http://github.com/double-conversion (of which I'm the author).

It's based on http://florian.loitsch.com/publications/dtoa-pldi2010.pdf

I'm obviously biased, but I think the API is easier, and the algorithm is faster.

However, it's in C++ (which might not suit your needs), and it requires more code (especially with the precomputed constants).

Re:0.30000000000000004 by legulere on Sunday April 02, 2017 @03:55PM (#14018715)
You might be interested in interval arithmetics: https://en.wikipedia.org/wiki/Interval_arithmetic