Correctly Rounded Decimal Conversion and Shortest Round-Trip Printing

Every decimal fraction with a denominator that is not a power of two has no exact binary representation, so the string 0.1 denotes a real number that is not a double. Reading it requires choosing the nearest double, and printing a double requires choosing a decimal string that reads back as the same value. Both directions look like formatting chores. Both are exact-arithmetic problems in their worst cases, and both are specified tightly enough that implementations disagree only where the standard allows them to.

The nearest value is a decision, not a formula

Parsing d₁d₂…dₖ × 10^e means computing the rational number M × 10^e / 10^j for some integer M and exponent, then rounding it to p bits. The naive implementation accumulates digits in a double and multiplies by a power of ten. That performs a rounding at every digit and another at the scaling, so the result can be several ulps away from the nearest value. It is also what many quick parsers do, which is why a hand-written parser and the C library can disagree on the last bits of a long input.

Correct rounding means producing exactly the value that the rounding mode selects, as if the decimal had been computed exactly and rounded once. For most inputs this is easy, because most inputs are short. For a small fraction it requires knowing the decimal expansion to hundreds of digits: the hardest binary64 cases need well over 700 significant decimal digits before the comparison against the midpoint can be decided. That number is not a property of the format’s precision but of the worst-case distance between a binary64 value and a decimal midpoint, and it is why a correct parser needs arbitrary-precision integers in its slow path.

The fast path that covers almost everything

There is a large set of inputs for which the conversion is exact with ordinary arithmetic, and identifying it is the central trick in practical parsers. If the decimal significand M is below 2^53 and the exponent e satisfies 0 ≤ e ≤ 22, then both M and 10^e are exactly representable as binary64 — 10^22 is the largest power of ten that is, because 5^22 still fits in 53 bits — and the product M × 10^e is a single correctly rounded operation. The same holds for negative exponents down to −22, where the division M / 10^-e is a single rounding.

So a parser can convert the digit string to an integer, check the two bounds, and take the fast path with one multiplication or division. Clinger’s formulation of this test is the reason a simple loop over digits with a bounded exponent is provably correct rather than merely usually correct. Everything outside the bounds goes to the slow path: exact big-integer scaling, a comparison against the two neighbouring binary values, and a decision about which is nearer.

Modern parsers are built around the same split. The fast path handles the overwhelming majority of literals in source code and data files; the slow path exists for the rest and is exercised by adversarial or high-precision input. A parser that omits the slow path entirely will be correct on typical data and wrong on some inputs, which is the worst combination for a numerical code, because the failure is silent and input-dependent.

Reading, printing, and the interval in between

Printing is the inverse problem and has a cleaner statement. A binary64 value x is the correct parse of every decimal in an interval around it: the interval is bounded by the midpoints between x and its two neighbours, with the boundary points themselves assigned by the tie rule. Any decimal string inside that interval reads back as x. The task is to find the shortest such string, and among equally short ones the closest to x.

Seventeen significant digits always suffice for binary64, because 10^17 > 2^53: distinct binary64 values cannot collide when each is written with 17 digits. Nine digits suffice for binary32. That gives a trivially correct printing strategy — format with %.17g — and a visually poor one, since 0.1 prints as 0.10000000000000001. The shortest-round-trip algorithms exist to recover the nice string.

The search is not a search over strings. Steele and White’s Dragon4 generates digits one at a time with exact rational arithmetic, stopping as soon as the remaining interval contains a decimal that can be written with the digits produced so far. Later algorithms replace the exact arithmetic with precomputed tables: Grisu3 produces the shortest representation in most cases and detects the cases where it cannot prove correctness, falling back to a slower exact method; Ryu and Schubfach compute the answer directly with fixed-size integer arithmetic and no fallback. The result is that the shortest representation of a binary64 is a bounded computation, not an unbounded one.

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    double x = strtod("0.1", NULL);   /* nearest binary64 to one tenth */
    printf("%.17g\n", x);             /* 0.10000000000000001 */
    printf("%a\n", x);                /* 0x1.999999999999ap-4 */
    printf("%.17g\n", 0.1);           /* the literal is rounded the same way */
    return 0;
}

The %a conversion is the escape hatch from the whole problem. Hexadecimal floating-point literals, added to C in C99, write the significand as a hexadecimal fraction and the exponent as a power of two, so every field maps directly onto the binary format. Reading and writing them is exact and requires no decimal arithmetic. A file of %a values round-trips through any conforming implementation bit for bit, at the cost of being unreadable to humans and unsupported by many other languages’ parsers.

Where the guarantees thin out

The C standard’s latitude for decimal floating constants is one ulp: a translation-time constant may be the nearest representable value or an immediately adjacent one, at the implementation’s choice. In practice compilers are correctly rounded, but the permission exists, and it is the reason a literal that a program depends on for exactness is better written in hexadecimal or constructed from exactly representable parts.

Locale is the second gap. strtod and printf consult the current locale for the decimal point character, so a program that parses a data file with a comma-separated decimal in one locale and a period in another gets different results, or no result. The C locale-independent functions for this purpose are not part of the base standard on every platform, and the portable fix is to set the numeric locale explicitly around the conversion or to avoid locale-dependent formatting entirely.

The third gap is the one that matters for reproducibility. A value that is printed with insufficient digits and read back is a different value, and the difference is not random: it is the rounding of the print, which depends on the format string. Six digits is enough for a human to read a physical quantity and not enough to preserve a computation’s state. Any checkpoint, cache, or intermediate file that will be read back into a calculation needs either 17 digits, a shortest-round-trip printer, or a binary encoding.

Choosing a representation

Three properties are being traded: human readability, exactness, and compactness. Decimal text with the shortest round-trip property is readable and exact but requires a correct printer and parser on both ends. Fixed 17-digit text is exact and trivially produced but ugly and longer than the shortest form for most values. Hexadecimal float text is exact and cheap but foreign to most tools. Raw binary is compact and exact but carries endianness and format-width assumptions that make it fragile across platforms.

For values that are themselves decimal quantities — money, measured constants, anything whose definition is a decimal string — the binary round trip is the wrong layer, and a decimal floating-point or scaled-integer representation avoids the question. For values that are the output of a binary computation, the round trip is the only requirement, and the shortest representation is the right default. The same reasoning applies to the arithmetic that consumes these values: a decimal literal is rounded once on entry, and everything after that is the binary arithmetic covered in IEEE 754 Binary Formats: Sign, Exponent, and Fraction Layouts and Round-to-Nearest-Even and the Mechanics of Correct Rounding.