/Drachennest

Different algorithms for converting binary to decimal floating-point numbers

Primary LanguageC++Boost Software License 1.0BSL-1.0

Build Status Build status codecov

Converting binary floating-point to decimal floating-point numbers.


Grisu / Dragon

Contains an implementation of the Grisu2 and Grisu3 algorithms as described in

The Grisu3 implementation uses the Dragon4 algorithm as a fallback.

Ryu

Contains an implementation of the Ryu algorithm as described in

The implemenation also contains a (fast!) strtod implementation, which can be used to convert decimal numbers with at most 17 significant decimal digits back into binary floating-point numbers. (Note that none of the algorithms here will ever produce more than 17 significant digits.)

Schubfach

Contains an implementation of the Schubfach algorithm as described in

The name of this algorithm "deliberately departs from a long lineage of fabulous drakes".

Dragonbox

Contains a slightly modified version the reference implementation of Junekey Jeon's Dragonbox algorithm.


Grisu3, Ryu, Schubfach, and Dragonbox are optimal, i.e. the output string

  1. rounds back to the input number when read in,
  2. is as short as possible,
  3. is as close to the input number as possible.

These algorithms (currently) assume that the input rounding algorithm uses round-to-nearest-even to break ties. Grisu2 only is optimal for ~99% of all floating point numbers, though it guarantees the first property for all of its inputs, regardless of how the input rounding mode breaks ties.


Benchmarks

Benchmarks were run on an Intel Core i7-9750H, using Visual Studio 2019 16.7.7, Clang 10.0, 64-bit.

Timings are in ns.


For this benchmark uniformly distributed random doubles in the range [1,2] have been generated. These numbers were then rounded to N significant digits and converted to decimal using the given algorithm.

BenchDigits


Uniformly distributed random numbers in the range [10^i, 10^(i+1)] for i=-12,...,12.

BenchUniform


Uniformly distributed random numbers in the range [0, 10^10]. Each benchmark is run 10 times (using different numbers each run).

BenchUniformE10


Random bit patterns. Each benchmark is run 10 times (using different numbers each run).

BenchRandom