Printing a float

Status: settled and built.

floating-point.md §7 listed printing as “the one that makes float awkward rather than incomplete”, and that was the right word. A language with float and no way to print one reports numbers through truncate and a scale factor, which is fixed point with extra steps — examples/newton.cho did exactly that, and said so.

This document is that row closed. The answer is std.fmt.float_into, and the thing worth reading it for is where the answer lives: not in the compiler.

1. What “printing a float” means

There are three things a printer could aim at, and only one of them is a contract:

The third is the contract, and it is the one this implements: for every float x, reading back what float_into wrote gives x again, and no shorter decimal would have.

That property is worth stating precisely, because it is stronger than “accurate”. 0.1000000000000000055511151231257827 is more accurate and still wrong for this purpose: the value it names is the same float, so the extra digits carry no information and cost thirty characters.

1.1 The form

d[.ddd]e[-]k

One digit, optionally a point and the rest, then e and a decimal exponent. 0.1 is 1e-1, 1.5 is 1.5e0, 100.0 is 1e2, zero is 0e0.

This is not the prettiest choice and it is deliberate. Positional notation — printing 0.1 as 0.1 and 1e21 as 1000000000000000000000 — needs a second set of decisions (at which exponent does it switch? how many leading zeros before it gives up?) which have nothing to do with the digits and which every language answers differently. Those decisions are a formatting layer’s business. The digits are the hard part, and this is the layer that gets them right.

inf, -inf and NaN are spelled rather than refused, because floating-point.md §2 made them values. -0.0 prints as -0e0: the sign bit is part of the value, and losing it on the way out would make printing the one place the language forgot.

2. Where it lives, which is the point

float_into is written in cancho, in std/fmt.cho. It is not a builtin, not a call into libc, and not a special case in the code generator. The compiler’s entire contribution is one builtin:

bits_of(x: float) -> int          // the same 64 bits, read as an integer

A bitcast, plus two instructions that give every NaN one pattern (movq, ucomisd, cmovp on x86-64; differential.md §4, #76). From there the algorithm is ordinary cancho: masks and shifts to pull the mantissa and exponent apart (bitwise.md), a region to hold the working numbers, while loops, and a [byte] to write into. Its effect row is [] — printing a float performs nothing, because writing the bytes somewhere is the caller’s effect, not this function’s.

This matters more than it looks. The usual arrangement is that a language’s float printing is a thousand lines of C or Rust inside the runtime, reachable only through whatever interface it chose to expose. Here the worst piece of numerical formatting there is turned out to be library code in the language itself, and the thing that made it possible is a builtin small enough to describe in six words.

It is also the honest test of bits_of. A primitive that only the compiler’s own code could use would not have earned its place; float_into is the program that proves a user could have written this.

3. The algorithm

Steele and White’s, which Dragon4 is a refinement of and Grisu and Ryū are the fast approximations to.

Keep the value as an exact ratio of integers R / S, and keep alongside it the distance to the midpoint of each neighbouring float, M+ and M-. Scale until the value sits in [0.1, 1). Then, repeatedly: multiply R by ten, take the digit, and ask whether what remains is already closer to this float than to either neighbour. When it is, stop — the digits emitted so far are the shortest that round-trip.

The stopping rule is the whole algorithm. It is why the output is shortest rather than merely correct, and it is what Grisu2 cannot guarantee and falls back to Dragon4 for.

The integers involved reach 1080 bits (§4), so std.bignum is underneath — also written in cancho, also in this repository, and ninety lines rather than four hundred for the reason in §3 below.

3.1 The factors of two, and why the setup has four cases

A float is m * 2^e exactly. To make R, S, M+ and M- all integers, everything is scaled by a power of two:

“Uneven” is the case every paper on this spends a paragraph on: at a power of two the gap to the float below is half the gap to the float above, because the mantissa just rolled over. A printer that ignores it is wrong on exactly the values a test suite is most likely to contain — 1.0, 0.5, 2.0, every 2^k — which is why the corpus in §5 contains all 2046 of them rather than a sample.

3.2 No division, which is why std.bignum is ninety lines

A digit is R / S for two bignums. That sounds like it needs bignum division, which is the single nastiest routine in an arbitrary-precision library — Knuth 4.3.1 algorithm D, normalisation, quotient estimation, the correction step.

It does not, because the digit is 0 to 9. Nine subtractions settle it:

var digit = 0;
while bignum.compare(r, s) >= 0 {
    bignum.subtract(r, s);
    digit = digit + 1;
}

std.bignum therefore has no division at all. It has compare, subtract, add_into, mul_small, shift_left, copy and set, all in-place over a fixed-length [int] of base-2³² limbs, all allocation-free — which is what lets the caller keep five of them in one region and never touch the heap.

Base 2³² rather than 2⁶³ for one reason: a limb has to survive being multiplied by ten. 10 * (2^32 - 1) is about 2^35.7 and fits; the same product in base 2⁶³ would trap on overflow.

3.3 The boundaries are inclusive for an even mantissa — a measured digit

Reading a decimal back uses round-to-nearest-even. So when the mantissa is even, a decimal sitting exactly on the midpoint between this float and its neighbour still reads back to this float: the tie goes to the even one, which is this one. The boundary is inclusive.

That turns four comparisons from < into <=, and it is not cosmetic. Without it, 5.299064834871378e16 printed as 5.2990648348713776e16 — seventeen digits where sixteen round-trip. Correct, and one digit too long, which is precisely the failure the shortest-printing contract exists to rule out. Two of the first 4000 corpus values caught it.

3.4 A dead-level tie, where two answers are both right

Once in a while the exact value sits exactly halfway between two shortest decimals. 2^-25 is one: its exact value is

0.0000000298023223876953125

and truncating to seventeen significant digits leaves exactly 5 with nothing after it. Both 2.9802322387695312e-8 and 2.9802322387695313e-8 are seventeen digits, and both read back to 2^-25. Neither is more correct.

So the rule is a choice, and the choice is observable:

The first version of float_into followed Steele and White — round the tie up — which is what Rust does. Python rounds the tie to the even digit. Over the 9000-value corpus in §5 the two disagreed on three values, all of them exact ties, and every one of the six spellings round-trips.

That was a defect, not a choice, and it is fixed. A table tool that wrote floats and was checked against Python found the same double printing as two different strings depending on which tool wrote it (...86.125 is ...86.12 in Python’s repr and was ...86.13 here), which is the one thing a shortest printer is for: one answer. The rule now is the shortest decimal that reads back; among those the closest to the exact value; and an exact tie goes to the even last digit. That is a definition with one answer for every double, and it is the rule of Ryu, of Python’s repr, and of Java since 19. Only Rust’s {:e} (and the first version here) differs, and only on exact ties: 1,543 of 100,000 doubles of the check corpus (which is built to be tie-rich: j / 2^k with j odd and 17 or 18 digits ending in a 5) printed differently from Python before; 0 of 1,002,109 after. In the test corpus of §5 it is the same three values: 2^-25 prints 2.9802322387695312e-8 now.

This is worth a section rather than a footnote because it is the kind of thing a document usually asserts and nobody checks. Both rules were implemented and both were run against both oracles; the numbers above are measurements, not recollections.

4. 1080 bits, measured rather than bounded

The working numbers get large: near the bottom of the subnormals the numerator picks up a factor of 10³²³ on the way to the first digit, while the denominator is already 2¹⁰⁷⁶.

The first draft of this comment claimed “about 2200 bits”. Instrumenting the algorithm over the corpus says otherwise:

widest 1080 bits, at 4.3374988771064606e-308  →  34 limbs

So limbs() is 80 — more than double the widest observed, because the cost of the slack is one bump of an arena pointer and the cost of being wrong is a silent carry off the top. But the comment now says 1080, because the comment that said 2200 was made up.

5. Verified against an oracle

A printer is exactly the kind of code that passes every example someone thought of and fails on the 4000th random bit pattern. So it is checked against Rust’s {:e} over a generated corpus, in shortest_printing_agrees_with_an_oracle.

(Since the tie rule of §3.4 changed, the oracle is {:e} or, where they differ, the exact tie rounded to the even digit, decided from the exact value: is_rust_or_even_tie in float_text.rs.)

The test has a pleasant property: the expected output is the input. {:e} is the shortest round-tripping form, and the lexer’s f64::from_str is correctly rounded, so writing each value into the generated program as {:e} and expecting the program to print that same string back tests the digits and nothing else. A failure is a disagreement about digits, never about notation.

The corpus is 9000 values:

Plus the_values_with_no_literal_are_spelled for inf, -inf, NaN and -0.0, which have no literal syntax to generate and so are built from arithmetic inside the program.

At scale, against Python. scripts/float_differential.py prints 1,002,109 doubles through float_of_bits and float_into (random bit patterns, every power of two, the edges, and 100,000 built to be exact ties: j / 2^k with j odd and an exact expansion of 17 or 18 digits ending in a 5) and compares the digits and the exponent with Python’s repr, and that every string reads back to the same 64 bits: 0 differences; before the tie rule changed, 1,543 of the first 100,000. float_text.rs does the same against Rust’s {:e} for 220,000 doubles, accepting only an exact tie rounded to the even digit.

During development this corpus found two real defects: §3.3’s missing inclusive boundary, and §3.4’s tie rule. Both were one-line changes and neither would have been found by an example.

6. What it costs the caller

pub fn float_into[&o](out: &!o [byte], x: float) -> [] int

A [byte] to write into and the value. It answers how many bytes it wrote, or -1 if the buffer was too short — threaded rather than trapped, because the caller chose the buffer.

24 bytes is always enough: a sign, seventeen digits, a point, e, a sign and three exponent digits. The longest output there is is -1.7976931348623157e308, at 23.

No Heap. The five bignums and the digits live in a region, so the whole thing is one arena that dies at the closing brace, and a program with no heap capability can still print a float. That is not an optimisation — examples/newton.cho releases heap in its first three lines, and would not compile otherwise.

7. What is still open

8. The suite