# How fmtlib Uses the Dragonbox Algorithm for Fast Floating-Point Formatting

> Discover how fmtlib leverages the Dragonbox algorithm for rapid floating-point formatting. Achieve O(1) decimal representation conversion without heap allocation.

- Repository: [Hello World Foundation/fmt](https://github.com/fmtlib/fmt)
- Tags: deep-dive
- Published: 2026-09-05

---

**The fmt library implements the Dragonbox algorithm in [`include/fmt/format-inl.h`](https://github.com/fmtlib/fmt/blob/main/include/fmt/format-inl.h) to convert binary floating-point numbers to their shortest decimal representation in O(1) time without heap allocation.**

fmt (also known as `{fmt}`) embeds a complete, header-only implementation of the Dragonbox algorithm to achieve industry-leading performance when formatting `float` and `double` values. Unlike traditional sprintf-style conversions that rely on division-heavy arbitrary-precision arithmetic, Dragonbox uses pre-computed power-of-10 caches and high-precision integer multiplication to produce correctly rounded, shortest-decimal output in constant time.

## What Is the Dragonbox Algorithm?

Dragonbox is a "Schubfach-style" algorithm that solves the floating-point-to-decimal conversion problem by treating the binary significand as an integer and scaling it through multiplication by cached powers of ten. The method guarantees that the output decimal string is the shortest possible representation that round-trips back to the original binary value when parsed. This approach avoids iterative division and runs in **O(1)** time regardless of the input's magnitude or precision.

## Architectural Overview of fmtlib's Implementation

The conversion pipeline lives entirely within the `dragonbox` namespace in [`include/fmt/format-inl.h`](https://github.com/fmtlib/fmt/blob/main/include/fmt/format-inl.h) and is invoked through a strict dispatch chain that begins in the public API headers.

### Entry Point and Dispatch

When you call `fmt::format` with a floating-point argument, the library forwards the value to `detail::write_float` in [`include/fmt/format.h`](https://github.com/fmtlib/fmt/blob/main/include/fmt/format.h) (around line 1710). This function eventually invokes `dragonbox::to_decimal`, which serves as the main entry point for binary-to-decimal conversion.

### Binary Decomposition

Inside `to_decimal` (lines 1240-1290 of [`format-inl.h`](https://github.com/fmtlib/fmt/blob/main/format-inl.h)), the algorithm extracts the raw IEEE 754 bits of the value using `bit_cast`, normalizes subnormal numbers, and separates the **significand** and **exponent**. This decomposition yields `two_fc`, a scaled integer representation of the value's mantissa that will be multiplied against the power-of-ten cache.

### Cache-Based Scaling

The core scaling logic (lines 1308-1312) computes two critical parameters:
- `k = floor_log10_pow2(exponent) - kappa`
- `beta = exponent + floor_log2_pow10(-k)`

These determine which pre-computed power of ten to fetch from `cache_accessor<T>::get_cached_power(-minus_k)` (lines 1385-1540). The cache contains 64-bit entries for `float` and 128-bit entries for `double`. When `FMT_USE_FULL_CACHE_DRAGONBOX` is disabled, fmtlib uses a compressed table with runtime reconstruction to minimize binary size.

### High-Precision Multiplication

With the cached power selected, the algorithm multiplies `two_fc` by the cached value using hand-rolled 96-bit and 192-bit multiplication routines (`umul96_upper64`, `umul192_upper128`) defined at lines 211-226. These portable intrinsics avoid compiler-specific dependencies while maintaining performance across platforms. The high bits of this product (`z_mul.result`) contain the scaled significand ready for decimal extraction.

### Digit Extraction and Rounding

For the division step (lines 1330-1340), the algorithm divides the high-precision product by `10^kappa` using `divide_by_10_to_kappa_plus_1` to isolate the integer portion of the decimal significand. The **shorter-interval case** (lines 1400-1472) handles edge cases where the interval between two adjacent decimal representations is smaller than usual, applying correct tie-breaking (round-to-even) when the input falls exactly between two valid outputs. Trailing zeros are stripped to ensure the shortest representation.

The final result is encapsulated in a `decimal_fp<T>` struct (significand plus exponent) returned at lines 1240-1248, which `detail::write_float` then renders into the output buffer.

## Key Implementation Details in format-inl.h

### The dragonbox Namespace

All low-level arithmetic helpers—`floor_log10_pow2`, `floor_log2_pow10`, and the multiplication primitives—reside inside the `dragonbox` namespace (lines 207-210). This isolation mirrors the reference implementation and prevents symbol collisions while keeping the code discoverable.

### Cache Compression Strategy

The `cache_accessor` templates (lines 891-907) provide either a full lookup table or a compressed representation depending on the `FMT_USE_FULL_CACHE_DRAGONBOX` macro. The compressed variant stores reduced-precision entries and reconstructs full 128-bit values at runtime, trading a small speed penalty for significant binary size reduction in embedded deployments.

### Portable Multiplication Primitives

To ensure correct behavior on platforms without native 128-bit integers, fmtlib implements `umul96_upper64` and `umul192_upper128` using standard 64-bit operations. These functions compute only the high bits of the product, which is sufficient for Dragonbox's scaling calculations and eliminates the need for full arbitrary-precision libraries.

## Practical Usage Examples

The Dragonbox implementation activates automatically for any floating-point formatting operation. Both fixed and general format specifiers route through the same `to_decimal` machinery:

```cpp
#include <fmt/core.h>

int main() {
    double d = 12345.6789;
    // Uses Dragonbox internally for shortest representation
    std::string s = fmt::format("{}", d);
    // Result: "12345.6789"
    
    float f = 1.0f / 3.0f;
    fmt::print("{:.6f}\n", f);  // "0.333333"
}

```

Even printf-style formatting triggers the optimized path:

```cpp
#include <fmt/printf.h>

int main() {
    float f = 0.33333334f;
    // %g specifier invokes Dragonbox via to_decimal
    fmt::print("%g\n", f);  // "0.333333"
}

```

No dynamic allocation occurs during conversion, and the execution time remains constant regardless of whether the input is `1e-308` or `1e308`.

## Summary

- **Dragonbox algorithm** provides O(1) shortest-decimal conversion without arbitrary-precision division.
- **Implementation location**: [`include/fmt/format-inl.h`](https://github.com/fmtlib/fmt/blob/main/include/fmt/format-inl.h) inside the `dragonbox` namespace.
- **Cache system**: Pre-computed power-of-10 tables with optional compression via `FMT_USE_FULL_CACHE_DRAGONBOX`.
- **Multiplication**: Custom 96-bit and 192-bit routines (`umul96_upper64`, `umul192_upper128`) ensure portability.
- **Rounding**: Special handling for shorter intervals via `shorter_interval_case` ensures correct round-to-even behavior.
- **Zero allocation**: The entire conversion pipeline is header-only and stack-based.

## Frequently Asked Questions

### What makes Dragonbox faster than std::to_chars?

Dragonbox avoids iterative division and digit-by-digit extraction by using cached powers of ten and high-precision integer multiplication. According to the fmtlib source code, this reduces the conversion to a constant-time sequence of bit operations and a single division by a power of ten, whereas many `std::to_chars` implementations use Grisu2 or Dragon4 algorithms that require variable-length loops or heap-allocated big integers.

### Does fmtlib allocate memory during Dragonbox conversion?

No. The implementation in [`include/fmt/format-inl.h`](https://github.com/fmtlib/fmt/blob/main/include/fmt/format-inl.h) uses only stack-allocated variables and compile-time constant tables. The `to_decimal` function returns a `decimal_fp<T>` struct containing two integers (significand and exponent), making the conversion suitable for real-time systems and embedded environments where heap allocation is prohibited.

### How does fmtlib handle subnormal floating-point numbers?

During the initial bit extraction phase (lines 1240-1290), `dragonbox::to_decimal` detects subnormal values by checking the exponent field and normalizes them by shifting the significand and adjusting the exponent accordingly. This ensures the subsequent cache lookup and multiplication steps operate on consistent integer representations regardless of the input's denormalized status.

### What is the shorter-interval case in Dragonbox?

The shorter-interval case occurs when the distance between two adjacent floating-point numbers is smaller than the standard unit in the last place (ULP) relative to decimal representations. In [`format-inl.h`](https://github.com/fmtlib/fmt/blob/main/format-inl.h) (lines 1400-1472), the `shorter_interval_case` template handles these scenarios by checking if the input falls exactly between two valid decimal outputs, applying round-to-even tie-breaking to maintain IEEE 754 correctness while still producing the shortest decimal string.