Converting Binary Floating-Point Numbers to Shortest Decimal Strings: An Experimental Review

This paper presents an empirical review comparing binary floating-point to decimal string conversion algorithms, highlighting that modern techniques like Schubfach and Dragonbox offer significant speedups over legacy methods like Dragon4, though many implementations still fail to consistently generate the shortest possible decimal strings.

The Gist

Imagine you have a massive library of secret codes written in a language only computers understand: Binary Floating-Point Numbers. These are the numbers your phone, laptop, and the internet use to do math (like $3.14159$or$0.000001$).

But humans can't read that secret code. We need them translated into Decimal Strings (like "3.14" or "0.000001") so we can read logs, see prices on a screen, or save data to a text file.

This paper is a race report comparing different "translators" (algorithms) to see which one does the job fastest, most accurately, and with the least amount of wasted space.

Here is the breakdown of the study using simple analogies:

1. The Problem: The "Heavy Luggage" of Translation

Converting a computer number to a human number isn't just a simple swap. It's like trying to translate a complex poem into a different language while ensuring:

• Accuracy: The translation must be perfect. If you translate "3.14159" and then translate it back, you must get the exact original code.
• Brevity: You want the shortest possible sentence. "3.14" is better than "3.1400000000000001" because it's shorter and easier to read.

For decades, the standard translator (called Dragon4) was like an old, slow-moving truck. It got the job done, but it took thousands of steps (instructions) to translate a single number. If you had to translate a billion numbers (which happens in big data), that truck would clog the highway.

2. The New Contenders: The "Sports Cars"

The researchers tested a lineup of modern translators, including Dragonbox, Schubfach, and Ryū.

• The Result: These new translators are like Formula 1 cars. They are 10 times faster than the old truck.
• The Analogy: The old truck took 1,500 to 5,000 steps to translate one number. The new sports cars do it in as few as 210 steps. That is a massive speedup.

3. The Surprise: Fast Doesn't Always Mean "Shortest"

Here is the twist in the story. The researchers found that while the new sports cars are incredibly fast, they don't always produce the shortest possible string.

• The Metaphor: Imagine you are packing for a trip.
  • Goal A (Minimal Significand): You pack the absolute minimum amount of clothes needed to survive.
  • Goal B (Minimal String): You pack the clothes in the smallest suitcase possible.
  • The Issue: Some algorithms are great at Goal A (they calculate the perfect number), but they are bad at Goal B (they put the clothes in a bulky, awkward suitcase).
  • Real-world Example: The number 0.00011 could be written as 1.1e-4 (6 characters). But some standard libraries write it as 0.00011 (7 characters). It's only one character longer, but if you are translating billions of numbers, that extra character adds up to gigabytes of wasted space and slower transmission speeds.

The study found that even the fastest algorithms often produce strings 20% to 30% longer than they need to be. They are fast, but they aren't "packing efficiently."

4. The Hardware Test: Does the Car Need a Better Road?

The researchers tested these translators on different "roads" (computer chips):

• The Roads: They used everything from old Intel chips to the newest Apple M4 chips and Amazon's cloud servers.
• The Finding: The "Sports Cars" (Dragonbox/Schubfach) were fast on all roads.
• The Surprising Detail: You might think these super-fast algorithms would use special "super-highways" (advanced CPU instructions like SIMD) to go even faster. But they don't! They are so efficient with their basic steps that adding fancy hardware features barely helps. They are already driving so well that the road upgrades don't make much difference.

5. The Verdict: What Should We Do?

The paper concludes with two main takeaways for the future:

1. Speed is Solved (mostly): We have found translators that are incredibly fast. We don't need to worry about the math part anymore.
2. The "Packing" Problem is Unsolved: The final step—turning the calculated number into a string of text—is still too clumsy.
   • The Fix: We need to build "smart suitcases." We need algorithms that not only calculate the number quickly but also know exactly how to format it to use the fewest characters possible, without wasting space on unnecessary zeros or signs.

Summary in One Sentence

We found that modern computer translators are 10 times faster than the old ones, but they still leave a lot of "dead space" in the text they produce, and fixing that inefficiency is the next big challenge for software engineers.

Technical Summary

1. Problem Definition

The paper addresses the conversion of IEEE 754 binary floating-point numbers (32-bit float and 64-bit double) into their shortest possible decimal string representations. This process is critical for data serialization (JSON, CSV), logging, and user interfaces.

The authors distinguish between two related but distinct objectives:

1. Minimal Decimal Significand: Finding the shortest integer $w$ such that $w \times 10^q$ round-trips to the original binary value. Most modern algorithms focus on this.
2. Minimal Printed String: Finding the shortest character string that round-trips. This involves optimizing the choice between fixed-point and scientific notation, the placement of the decimal point, and the formatting of exponents (e.g., 1.2e4 vs 1.2e+04).

The paper highlights that while many algorithms guarantee the first objective, few consistently achieve the second, often producing strings up to 30% longer than the theoretical minimum due to legacy formatting rules (e.g., mandatory positive signs or two-digit exponents in C standards).

2. Methodology

The authors conducted a comprehensive empirical study designed to overcome limitations in prior benchmarks (which often used synthetic data, limited hardware, or ignored output string lengths).

• Hardware: Experiments were run on a diverse range of architectures, including:
  • x86-64: Intel (Skylake, Ice Lake, Sapphire Ridge) and AMD (Zen 2, Zen 3, Zen 4, Zen 5).
  • ARM/AArch64: Apple M4 Max, AWS Graviton (Neoverse N1, V1, V2).
• Datasets:
  • Core Datasets: mesh (3D coordinates, many integers), canada (GIS data, high precision), and unit (uniformly distributed synthetic data).
  • Real-World Datasets: Financial (Bitcoin), Marine Robotics, Machine Learning (MobileNet weights), Astronomy (Gaia), and Meteorology (NOAA).
• Algorithms Evaluated:
  • Historical: Dragon4 (Steele & White, 1990).
  • Modern Exact: Grisu3, Grisu-Exact, Schubfach, Dragonbox, Ryū.
  • Libraries: Google double-conversion, C++ std::to_chars, fmt, and Swift's SwiftDtoa.
• Metrics:
  • Performance: Nanoseconds per float (ns/f).
  • Instruction Count: Instructions per float (ins/f) and Instructions per Cycle (ins/c) to isolate algorithmic efficiency from microarchitectural throughput.
  • Output Quality: Average character length of the generated strings compared to the theoretical minimum.

3. Key Contributions

1. Systematic Empirical Evaluation: The first unified benchmark covering both major CPU families (x86-64 and ARM) and a mix of synthetic and real-world datasets.
2. Output Length Characterization: The study is the first to quantify end-to-end string lengths at scale, revealing that "shortest significand" does not equate to "shortest string."
3. Instruction-Level Analysis: Moving beyond wall-clock time, the authors analyze instruction counts to separate algorithmic complexity from hardware-specific optimizations.
4. Reassessment of Benchmarks: The paper identifies methodological flaws in existing benchmarks, such as the lack of 32-bit testing, reliance on synthetic data, and failure to measure output string length.

4. Key Results

A. Performance (Speed)

• Modern vs. Legacy: Cutting-edge algorithms (Schubfach and Dragonbox) are up to 10x faster than the classic Dragon4 algorithm.
  • Dragon4: Requires 1,500–5,000 instructions per conversion.
  • Schubfach/Dragonbox: Require as few as 210–310 instructions per conversion.
• Algorithm Ranking:
  • Fastest: Schubfach and Dragonbox consistently lead across all datasets and architectures.
  • Intermediate: Ryū, Grisu-Exact, and std::to_chars.
  • Slowest: Dragon4 and legacy library implementations.
• Hardware Impact: While CPU architecture affects absolute speed (e.g., Apple M4 Max and AMD Zen 5 are faster than older Neoverse cores), the algorithm choice is the dominant factor. The instruction count difference between algorithms (e.g., 240 vs. 5000) far outweighs the performance variance caused by compiler or CPU differences.
• Instruction Sets: Enabling advanced instruction sets (AVX-512, FMA) yields marginal to no performance gains for single-value conversion, suggesting current algorithms do not effectively utilize vectorization for this specific task.

B. Output Quality (String Length)

• Suboptimal Lengths: None of the surveyed implementations consistently produce the shortest possible string.
  • Standard library implementations (e.g., C++ std::to_chars, Swift) often produce strings 20–30% longer than optimal.
  • This is largely due to formatting rules (e.g., forcing 1.2e+04 instead of 1.2e4 or 12000 instead of 1.2e4).
• Trade-offs: Algorithms like Ryū and Dragonbox prioritize correctness and speed but often generate longer strings (e.g., preferring scientific notation even when fixed-point is shorter). Conversely, std::to_chars and Dragon4 often produce shorter strings but at a significant performance cost.

C. 32-bit vs. 64-bit

• 32-bit conversions are generally faster than 64-bit due to shorter output strings. However, some algorithms (like std::to_chars and Dragonbox) show minimal performance difference between the two, suggesting their bottlenecks are fixed overheads rather than string length.
• Interestingly, while fewer 64-bit numbers are processed per second, the character throughput (bytes generated per second) is often higher for 64-bit due to the longer average string length.

5. Significance and Future Directions

• Software Efficiency: The paper demonstrates a decade-long trend of software optimization, achieving a ~10x speedup in float-to-string conversion over 30 years.
• Practical Impact: For applications processing billions of values (telemetry, ML, finance), switching from legacy libraries to modern algorithms (Schubfach/Dragonbox) can yield massive performance gains.
• Future Research Opportunities:
  1. Unified Backends: Developing string generation routines that decouple from significand calculation to consistently produce the shortest string, not just the shortest significand.
  2. Batch Processing: Since single-value conversion does not fully utilize SIMD/FMA, future work should explore batch conversion (processing multiple floats in parallel) to leverage modern CPU vectorization capabilities.
  3. Optimization Targets: Reducing the cost of the final string formatting step, which currently consumes a significant portion of runtime in modern fast algorithms.

In conclusion, the paper establishes that while modern algorithms have solved the speed problem, the "shortest string" problem remains an open challenge in standard libraries, and significant performance headroom exists through batch processing and better string formatting strategies.