4 ms·

Once I wrote a library for double-to-string conversion and vice versa, which handles such roundings nicely: https://github.com/mkupchik/dconvstr https://github.

by mkup 10y ago

Once I wrote a library for double-to-string conversion and vice versa, which handles such roundings nicely: https://github.com/mkupchik/dconvstr 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.

legulere 10y ago
You might be interested in interval arithmetics: https://en.wikipedia.org/wiki/Interval_arithmetic https://en.wikipedia.org/wiki/Interval_arithmetic
jacobolus 10y ago
Python does this, for example (but likely in a more efficient way): http://bugs.python.org/issue1580 http://bugs.python.org/issue1580 See also http://www.netlib.org/fp/ http://www.netlib.org/fp/ http://web.archive.org/web/20060908072403/http://ftp.ccs.neu.edu/pub/people/will/retrospective.pdf 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.
- amelius 10y ago
  > 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 :)
  - danbruc 10y ago
    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.
    - daurnimator 10y ago
      > 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?
  - kccqzy 10y ago
    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.
- sametmax 10y ago
  But Python also warns about it in the documentation, and provide the factions (https://docs.python.org/3.1/library/fractions.html https://docs.python.org/3.1/library/fractions.html) module and the decimal module thttps://docs.python.org/3.1/library/decimal.html https://docs.python.org/3.1/library/decimal.html) in the stdlib to avoid the problem.
  - int_19h 10y ago
    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...
- FabHK 10y ago
  > 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).
dietrichepp 10y ago
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 http://www.netlib.org/fp/dtoa.c
- Avernar 10y ago
  I've long ago stopped using C's standard library floating point routines and use Gay's code. Main reason was inconsistencies between compilers.
- floitsch 10y ago
  There is also http://github.com/double-conversion http://github.com/double-conversion (of which I'm the author). It's based on http://florian.loitsch.com/publications/dtoa-pldi2010.pdf 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).
TazeTSchnitzel 10y ago
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.pdf https://cseweb.ucsd.edu/~lerner/papers/fp-printing-popl16.pd...
- willlll 10y ago
  https://github.com/marcandrysco/Errol 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.
  - TazeTSchnitzel 10y ago
    Yeah, it's unfortunately not the fastest algorithm known, despite what was originally thought, but it is still the fastest accurate one.
    - simonbyrne 10y ago
      Grisu isn't accurate?
      - floitsch 10y ago
        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 http://github.com/google/double-conversion) does exactly that. It uses the slower bignum algorithm in these cases.

by mkup 10y ago

legulere 10y ago

You might be interested in interval arithmetics: https://en.wikipedia.org/wiki/Interval_arithmetic https://en.wikipedia.org/wiki/Interval_arithmetic

jacobolus 10y ago

Python does this, for example (but likely in a more efficient way): http://bugs.python.org/issue1580 http://bugs.python.org/issue1580 See also http://www.netlib.org/fp/ http://www.netlib.org/fp/ http://web.archive.org/web/20060908072403/http://ftp.ccs.neu.edu/pub/people/will/retrospective.pdf 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.

amelius 10y ago
> 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 :)
- danbruc 10y ago
  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.
  - daurnimator 10y ago
    > 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?
- kccqzy 10y ago
  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.
sametmax 10y ago
But Python also warns about it in the documentation, and provide the factions (https://docs.python.org/3.1/library/fractions.html https://docs.python.org/3.1/library/fractions.html) module and the decimal module thttps://docs.python.org/3.1/library/decimal.html https://docs.python.org/3.1/library/decimal.html) in the stdlib to avoid the problem.
- int_19h 10y ago
  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...
FabHK 10y ago
> 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).

dietrichepp 10y ago

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 http://www.netlib.org/fp/dtoa.c

Avernar 10y ago
I've long ago stopped using C's standard library floating point routines and use Gay's code. Main reason was inconsistencies between compilers.
floitsch 10y ago
There is also http://github.com/double-conversion http://github.com/double-conversion (of which I'm the author). It's based on http://florian.loitsch.com/publications/dtoa-pldi2010.pdf 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).

TazeTSchnitzel 10y ago

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.pdf https://cseweb.ucsd.edu/~lerner/papers/fp-printing-popl16.pd...

willlll 10y ago
https://github.com/marcandrysco/Errol 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.
- TazeTSchnitzel 10y ago
  Yeah, it's unfortunately not the fastest algorithm known, despite what was originally thought, but it is still the fastest accurate one.
  - simonbyrne 10y ago
    Grisu isn't accurate?
    - floitsch 10y ago
      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 http://github.com/google/double-conversion) does exactly that. It uses the slower bignum algorithm in these cases.