Dragonbox Algorithm in fmtlib: Fast, Correctly-Rounded Float-to-String Conversion

The Dragonbox algorithm converts binary floating-point numbers to their shortest decimal representation using exact integer arithmetic and cached powers of ten, enabling fmtlib to format doubles in O(1) time with guaranteed IEEE-754 round-to-nearest-even semantics.

The fmt library (fmtlib/fmt) utilizes the Dragonbox algorithm as its core engine for floating-point formatting, replacing slower sprintf-based methods with a deterministic, branch-minimized approach. By operating entirely on integer significands and pre-computed logarithmic tables, Dragonbox eliminates floating-point error accumulation during conversion. This implementation lives in include/fmt/format-inl.h and is exposed through the public API in include/fmt/format.h.

What Is the Dragonbox Algorithm?

Dragonbox is a reference implementation of the "shortest round-trip" algorithm originally introduced by Namiko et al. and later refined by Jun-Kyu Jeon. It guarantees that the decimal string produced is the shortest possible representation that converts back to the exact same binary value when parsed.

Core Stages of Conversion

The algorithm executes in three distinct phases:

1. Exact integer arithmetic on the significand – The floating-point exponent is used to left-shift the mantissa into a 128- or 256-bit integer (uint128_t/uint256_t), effectively treating the value as a large integer scaled by a power of two.
2. Fast logarithm approximation – It computes k = floor(log10(2^e)) using pre-computed tables and retrieves a "cached power of ten" via cache_accessor<T>::get_cached_power() to bring the integer into the correct decimal range.
3. Rounding and tie-breaking – Schubfach-style rounding rules are applied to obtain the shortest correctly-rounded decimal string, with trailing zeros removed only when they do not affect round-trip accuracy.

Key Insights and Guarantees

The algorithm’s critical insight is that all operations can be expressed as integer multiplications and bit-shifts, which modern CPUs execute in constant time. Dragonbox guarantees round-to-nearest-even semantics, matching the IEEE-754 rounding mode required by printf-style formatting and ensuring identical results across platforms.

How fmtlib Implements Dragonbox

fmtlib’s Dragonbox integration is located in the dragonbox namespace within include/fmt/format-inl.h (starting around line 207), with the public entry point to_decimal declared in include/fmt/format.h (line 1710).

The Conversion Pipeline

When you call fmt::format("{:g}", value), the library delegates to fmt::detail::to_decimal() defined at line 1275 of format-inl.h. The conversion flow follows these steps:

1. Bit extraction – to_decimal uses bit_cast to extract the raw IEEE-754 representation, separating the sign, exponent, and mantissa fields.
2. Logarithmic scaling – It computes minus_k = floor_log10_pow2(exponent) - kappa to determine the decimal exponent, then fetches the cached power of ten via cache_accessor<T>::get_cached_power(-minus_k).
3. Integer multiplication – Specialized helpers like umul96_upper64() and umul192_upper128() perform high-precision multiplication of the significand against the cached power, producing a scaled integer.
4. Digit generation – The decimal_fp<T> structure (containing significand and decimal exponent) is populated using Dragonbox’s rounding rules, which are then formatted into the final character sequence by generic formatting code.

Internal Helpers and Optimizations

The implementation provides architecture-specific optimizations through functions such as:

• umul128_upper64 and umul192_upper128 – Compute the high bits of large integer products without full 256-bit or 512-bit arithmetic.
• floor_log10_pow2 – Constant-time logarithm approximation using lookup tables.
• cache_accessor – Template-based cache retrieval supporting both float (32-bit) and double (64-bit) precisions.

Because the heavy lifting is performed by these integer routines, fmtlib can format floating-point numbers in roughly O(1) time with minimal branching, often performing 2–3× faster than std::to_chars on older compilers while maintaining a smaller binary footprint than printf implementations.

Practical Usage Examples

All floating-point format specifiers in fmtlib automatically invoke Dragonbox. You do not need special syntax to enable it:

#include <fmt/core.h>

int main() {
    double d = 0.1234567890123456789;  // High-precision value
    fmt::print("Default: {}\n", d);    // Uses Dragonbox via to_decimal
    fmt::print("Fixed 10: {:.10f}\n", d);
    fmt::print("Scientific: {:e}\n", d);
}

For debugging or custom wrappers, you can access the internal Dragonbox result (note: this uses private APIs subject to change):

#include <fmt/format.h>
#include <iostream>

template <typename T>
std::string extract_decimal(T value) {
    // Direct access to Dragonbox output (illustrative only)
    auto dec = fmt::detail::to_decimal(value);
    return fmt::format("significand={}, exponent={}", 
                       dec.significand, dec.exponent);
}

int main() {
    std::cout << extract_decimal(3.141592653589793) << '\n';
}

In this example, fmt::detail::to_decimal returns a decimal_fp<T> structure containing the exact decimal significand and exponent computed by the Dragonbox algorithm before final formatting.

Summary

• Dragonbox is an integer-arithmetic algorithm for shortest-decimal conversion of IEEE-754 floating-point values.
• fmtlib implements Dragonbox in include/fmt/format-inl.h inside the dragonbox namespace, with the entry point to_decimal() at line 1275.
• The algorithm achieves O(1) complexity using cached powers of ten and high-precision integer multiplication helpers like umul192_upper128().
• All floating-point formatting in fmtlib ({:f}, {:e}, {:g}, etc.) routes through this implementation, ensuring correctly-rounded, portable output without libc dependencies.

Frequently Asked Questions

How does Dragonbox differ from Grisu or Ryu algorithms?

Dragonbox focuses exclusively on the "shortest representation" problem using exact integer arithmetic and a single pass through cached logarithmic tables, whereas Grisu sometimes requires fallback to slower routines for edge cases, and Ryu prioritizes speed over minimal code size. Dragonbox achieves comparable speed to Ryu while guaranteeing the shortest output for all inputs, including subnormals.

Does fmtlib use Dragonbox for all floating-point format specifiers?

Yes, any format string involving floating-point types—whether {:f} (fixed), {:e} (scientific), {:g} (general), or automatic formatting—invokes fmt::detail::to_decimal() in format-inl.h, which executes the Dragonbox algorithm to generate the significand and exponent before applying width and precision padding.

How does the algorithm handle subnormal numbers and edge cases?

Dragonbox explicitly handles subnormal values by normalizing them during the bit-extraction phase in to_decimal(), using the same integer-scaling approach with adjusted exponents. The implementation correctly processes NaNs, infinities, and signed zeros by checking the IEEE-754 exponent and mantissa fields before entering the main conversion loop.

Can I call fmtlib’s Dragonbox implementation directly in my code?

While the primary API is fmt::format(), the underlying fmt::detail::to_decimal() function is accessible for specialized use cases, returning a decimal_fp<T> structure with integer significand and exponent. Be aware that fmt::detail symbols are not part of the public ABI and may change between releases; for production code, prefer the documented formatting API.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}