3 ms·

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

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.
- murkle 10y ago
  Chromium uses Grisu3 (C++) https://chromium.googlesource.com/v8/v8/+/f837290e142d49c9e1332841ec2c49ee2f09584a/src/grisu3.cc https://chromium.googlesource.com/v8/v8/+/f837290e142d49c9e1... as does Rhino (Java) https://github.com/mozilla/rhino/blob/master/src/org/mozilla/javascript/v8dtoa/FastDtoa.java#L439 https://github.com/mozilla/rhino/blob/master/src/org/mozilla...
deleted 10y ago
[deleted]
floitsch 10y ago
I'm the author of Grisu. (http://github.com/google/double-conversion http://github.com/google/double-conversion and http://florian.loitsch.com/publications/dtoa-pldi2010.pdf 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.

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.
murkle 10y ago
Chromium uses Grisu3 (C++) https://chromium.googlesource.com/v8/v8/+/f837290e142d49c9e1332841ec2c49ee2f09584a/src/grisu3.cc https://chromium.googlesource.com/v8/v8/+/f837290e142d49c9e1... as does Rhino (Java) https://github.com/mozilla/rhino/blob/master/src/org/mozilla/javascript/v8dtoa/FastDtoa.java#L439 https://github.com/mozilla/rhino/blob/master/src/org/mozilla...

deleted 10y ago

[deleted]

floitsch 10y ago

I'm the author of Grisu. (http://github.com/google/double-conversion http://github.com/google/double-conversion and http://florian.loitsch.com/publications/dtoa-pldi2010.pdf 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.