Repository files navigation

This project contains routines to convert IEEE-754 floating-point numbers todecimal strings using shortest, fixed%f, and scientific%eformatting. The primary implementation is in C, and there is a port of theshortest conversion to Java. All algorithms have been published inpeer-reviewed publications. At the time of this writing, these are the fastestknown float-to-string conversion algorithms. The fixed, and scientificconversion routines are several times faster than the usual implementationsof sprintf (we compared against glibc, Apple's libc, MSVC, and others).

Generating scientific and fixed output format for 16 and 32 bit IEEE floatingpoint numbers can be implemented by converting to 64 bit, and then using the64 bit routines. Note that there is no 128 bit implementation at this time.

When converting to shortest, DO NOT CAST; shortest conversion is based on theprecision of the source type, and casting to a different type will not returnthe expected output. There are highly optimized 32 and 64 bit implementationsas well as a generic 128 bit implementation that can handle any IEEE formatup to 128 bits.

These are the supported conversion modes for the C implementation:

The code is continuously tested on Ubuntu 18.04, MacOS High Sierra, and WindowsServer version 1803.

All code outside of third_party/ is copyrighted by Ulf Adams and contributors,and may be used freely in accordance with the Apache 2.0 license.Alternatively, the files in the ryu/ directory may be used freely in accordancewith the Boost 1.0 license.

All contributions are required to maintain these licenses.

Ryu generates the shortest decimal representation of a floating point numberthat maintains round-trip safety. That is, a correct parser can recover theexact original number. For example, consider the binary 32-bit floating pointnumber00111110100110011001100110011010. The stored value is exactly0.300000011920928955078125. However, this floating point number is alsothe closest number to the decimal number0.3, so that is what Ryuoutputs.

This problem of generating the shortest possible representation was originallyposed by White and Steele [1], for which they described an algorithm called"Dragon". It was subsequently improved upon with algorithms that also haddragon-themed names. I followed in the same vein using the japanese word fordragon, Ryu. In general, all these algorithms should produce identical outputgiven identical input, and this is checked when running the benchmark program.

The C implementation of Ryu is in the ryu/ directory. The Java implementationsare RyuFloat and RyuDouble under src/main/java/. Both cover 32 and 64-bitfloating point numbers.

In addition, there is an experimental C implementation that can handle inputsof any size up to 128-bit, albeit with lower performance than the highlyoptimized 32-bit and 64-bit implementations. Furthermore, there is anexperimental low-level C API that returns the decimal floating-pointrepresentation as a struct, allowing clients to implement their own formatting.These are still subject to change.

Note: The Java implementation differs from the output ofDouble.toString[2] in some cases: sometimes the output is shorter (which is arguably moreaccurate) and sometimes the output may differ in the precise digits output(e.g., see#83).

Note: While the Java specification requires outputting at least 2 digits,other specifications, such as for JavaScript, always require the shortest output.We may change the Java implementation in the future to support both.

My PLDI'18 paper includes a complete correctness proof of the algorithm:https://dl.acm.org/citation.cfm?doid=3296979.3192369

Other implementations of Ryu:

Since Ryu generates the shortest decimal representation, it is not immediatelysuitable for use in languages that have printf-like facilities. In mostimplementations, printf provides three floating-point specific formatters,%f,%e, and%g:

• The%f format prints the full decimal part of the given floating pointnumber, and then appends as many digits of the fractional part as specifiedusing the precision parameter.

• The%e format prints the decimal number in scientific notation with asmany digits after the initial digit as specified using the precisionparameter.

• The%g format prints either%f or%e format, whichever isshorter.

Ryu Printf implements %f and %e formatting in a way that should be drop-incompatible with most implementations of printf, although it currently does notimplement any formatting flags other than precision. The benchmark programverifies that the output matches exactly, and outputs a warning if not. Anyunexpected output from the benchmark indicates a difference in output.

Note that old versions of MSVC ship with a printf implementation that has aconfirmed bug: it does not always round the last digit correctly.

Note that msys cuts off the output after ~17 digits, and therefore generallydiffers from Ryu Printf output for precision values larger than 17.

Note that the output for NaN values can differ between implementations; we useifdefs in an attempt to match platform output.

According to our benchmarks, Ryu Printf compares favorably with the followingimplementations of printf for precision parameters 1, 10, 100, and 1000:

In addition, Ryu Printf has a more predictable performance profile. In theory,an implementation that performs particularly badly for some subset of numberscould be exploited as a denial-of-service attack vector.

My OOPSLA'2019 paper provides a correctness proof:https://dl.acm.org/citation.cfm?doid=3366395.3360595

We use the Bazel build system (https://bazel.build) 0.14 or later, although werecommend using the latest release. You also need to install Jdk 8 (or later)to build and run the Java code, and/or a C/C++ compiler (gcc or clang on Ubuntu,XCode on MacOS, or MSVC on Windows) to build the C/C++ code.

To build Ryu, run

$ bazel build //ryu

To build Ryu Printf, run

$ bazel build //ryu:ryu_printf

The C implementations should work on big-endian architectures provided that thefloating point type and the corresponding integer type use the same endianness.

There are no concerns around endianness for the Java implementation.

You can select a custom C++ compiler by setting the CC environment variable,e.g., use these steps to build with clang-4.0 on Ubuntu:

$ export CC=clang-4.0$ bazel build //ryu

Building Ryu Printf against musl and msys requires installing the correspondingpackages. We only tested against the musl Debian package that installs a gccwrapper and is enabled by settingCC. However, building against msysrequires manually adjusting Bazel's compiler configuration files.

You can run both C and Java tests with

$ bazel test //ryu/... //src/...

The code given by Jaffer in the original paper does not come with a licensedeclaration. Instead, we're using code found on GitHub3, which contains alicense declaration by Jaffer. Compared to the original code, thisimplementation no longer outputs incorrect values for negative numbers.

We provide a binary to find differences between Ryu and the Jaffer / Jdkimplementations:

$ bazel run //src/main/java/info/adams/ryu/analysis:FindDifferences --

Add the-mode=csv option to get all the discovered differences as a CSV. Use-mode=latex instead to get a latex snippet of the first 20. Use-mode=summary to only print the number of discovered differences (this is thedefault mode).

You can compute the required lookup table sizes with:

$ bazel run //src/main/java/info/adams/ryu/analysis:ComputeTableSizes --

Add-v to get slightly more verbose output.

You can compute the required bit sizes with:

$ bazel run //src/main/java/info/adams/ryu/analysis:ComputeRequiredBitSizes --

Add the-128 and-256 flags to also cover 128- and 256-bit numbers. Thiscould take a while - 128-bit takes ~20 seconds on my machine while 256-bit takesa few hours. Add-v to get very verbose output.

You can check the slow vs. the fast implementation for all 32-bit floating pointnumbers using:

$ bazel run //src/main/java/info/adams/ryu/analysis:ExhaustiveFloatComparison

This takes ~60 hours to run to completion on anIntel(R) Core(TM) i7-4770K with 3.50GHz.

You can check the slow vs. the fast implementation for all 64-bit floating pointnumbers using:

$ bazel run //src/main/java/info/adams/ryu/analysis:ExtensiveDoubleComparison

This takes approximately forever, so you will need to interrupt the program.

We provide both C and Java benchmark programs.

Enable optimization by adding "-c opt" on the command line:

$ bazel run -c opt //ryu/benchmark:ryu_benchmark --    Average & Stddev Ryu  Average & Stddev Grisu332:   22.515    1.578       90.981   41.45564:   27.545    1.677       98.981   80.797

For the Java benchmark, run:

$ bazel run //src/main/java/info/adams/ryu/benchmark --    Average & Stddev Ryu  Average & Stddev Jdk  Average & Stddev Jaffer32:   56.680    9.127       254.903  170.09964:   89.751   13.442      1085.596  302.371     1089.535  309.245

Additional parameters can be passed to the benchmark after the-- parameter:

  -32           only run the 32-bit benchmark  -64           only run the 64-bit benchmark  -samples=n    run n pseudo-randomly selected numbers  -iterations=n run each number n times  -ryu          run Ryu only, no comparison  -v            generate verbose output in CSV format

If you have gnuplot installed, you can generate plots from the benchmark datawith:

$ bazel build -c opt --jobs=1 //scripts:shortest-{c,java}-{float,double}.pdf

The resulting files arebazel-genfiles/scripts/shortest-{c,java}-{float,double}.pdf.

We provide a C++ benchmark program that runs against the implementation ofsnprintf bundled with the selected C++ compiler. You need to enableoptimization using "-c opt" on the command line:

$ bazel run -c opt //ryu/benchmark:ryu_printf_benchmark --    Average & Stddev Ryu  Average & Stddev snprintf%f:  116.359  130.992     3983.251 5331.505%e:   40.853   10.872      210.648   36.779

Additional parameters can be passed to the benchmark after the-- parameter:

  -f            only run the %f benchmark  -e            only run the %e benchmark  -precision=n  run with precision n (default is 6)  -samples=n    run n pseudo-randomly selected numbers  -iterations=n run each number n times  -ryu          run Ryu Printf only, no comparison  -v            generate verbose output in CSV format

See above for selecting a different compiler. Note that msys C++ compilationdoes not work out of the box.

We also provide a simplified C benchmark for platforms that do not support C++compilation, butnote that pure C compilation is not natively supported byBazel:

$ bazel run -c opt //ryu/benchmark:ryu_printf_benchmark_c --

If you have gnuplot installed, you can generate plots from the benchmark datawith:

$ bazel build -c opt --jobs=1 //scripts:{f,e}-c-double-{1,10,100,1000}.pdf

The resulting files arebazel-genfiles/scripts/{f,e}-c-double-{1,10,100,1000}.pdf.