Expand description
§Chapter 11.4 — Decimal formatting and parsing
§Purpose
Display, LowerExp and FromStr for DoubleDouble. The contract
asks for faithful conversions (question E7: an error of at most one
unit of the 32nd digit). Both are in fact correctly rounded: they are computed
in exact integer arithmetic (Chapter 11.3), which is simpler to state
and to test than a conversion carried out in double-double arithmetic
itself, whose error would have to be bounded.
§Notation
A finite nonzero double-double is x = ± M · 2ᴱ with M a natural
number (M = m_h 2^(e_h − E) ± m_ℓ 2^(e_ℓ − E) from the two
significands). Its decimal expansion d₁.d₂d₃… × 10ᵉ, d₁ ≠ 0, is
finite, because 2 divides 10. A decimal string is v = ± D · 10^q
with D a natural number. RN rounds to the nearest f64, ties to
even.
§Algorithms
Algorithm X (exact expansion). Input M, E. Output the digits
d₁ d₂ … d_n and e.
X1. [Integer.] If E ≥ 0, the digits are those of M · 2ᴱ (radix
conversion by repeated division by 10⁹) and e = n − 1. Stop.
X2. [Split.] I ← ⌊M / 2ˢ⌋, F ← M mod 2ˢ, s = −E. The integer
digits are those of I.
X3. [Fraction.] While F ≠ 0: F ← 10⁹ F; emit the nine digits of
⌊F / 2ˢ⌋; F ← F mod 2ˢ. (Each pass removes nine factors of two
from the denominator: at most ⌈s/9⌉ passes.)
X4. [Normalize.] Drop the leading and trailing zeros; e is the
position of d₁ relative to the point.
Algorithm O (output). Input x and an optional precision N (the
{:.N} of the format string).
O1. [Special.] NaN is NaN, the infinities inf and -inf, zero 0
(-0 for the negative zero).
O2. [Expand.] Algorithm X gives the digits and e.
O3. [Notation.] For {}: fixed if −5 ≤ e ≤ 31, else scientific
(d₁.d₂…e±k, as Rust writes {:e} for an f64: no +, no
leading zero in the exponent). With a precision the choice uses the
e of the exact value; without, that of the rounded one. For
{:e}: always scientific (zero is 0e0).
O4. [Round.] Without a precision: to 31 significant digits, half to
even, trailing zeros dropped. With precision N: to N digits
after the point of the chosen notation, zero-padded.
O5. [Pad.] Sign, width, fill and + as for the integers of core.
Algorithm I (input). Input a string. Output a double-double or an error.
I1. [Scan.] [+-] then inf, infinity or nan (any case), or
digits with at most one point and an optional exponent e[+-]k; at
least one digit; nothing else (no blanks). This gives D and q.
I2. [Range.] If v ≥ 10³¹⁰ return ±∞; if v < 10⁻³³⁰ return ±0.
I3. [Leading.] h ← RN(D · 10^q) by Algorithm N. If h is infinite
return ±∞.
I4. [Trailing.] ℓ ← RN(D · 10^q − h), the difference formed exactly
as a fraction of naturals, rounded by Algorithm N. Return ±2Sum(h, ℓ) (the pair itself, but for the tie of invariant P2).
Algorithm N (nearest f64 of a fraction). Input naturals A, B > 0. Output RN(A/B).
N1. [Scale.] t ← 65 − (bits(A) − bits(B)); (Q, sticky) ← the
short quotient (Algorithm Q of Chapter 11.3) of A · 2ᵗ by B, so
that 2⁶⁴ ≤ Q < 2⁶⁶.
N2. [Position.] The unit of the result is 2ᶜ, c = max(msb(Q) − t − 52, −1074) (53 significant bits, fewer in the subnormal range).
N3. [Round.] Drop the c + t low bits of Q, rounding half to even
with sticky breaking the tie upward.
N4. [Encode.] Assemble the bits; a significand of 2⁵³ moves to the
next binade, an exponent beyond the range is +∞.
§Invariants
(P1) Exact output. The digits written are those of the decimal
expansion of x correctly rounded (half to even) at the stated
position; with a precision large enough ({:.1100} always is) the
output is x.
(P2) Correctly rounded input. from_str returns the normalized pair
(D1) of value RN(v) + RN(v − RN(v)), within ulp(ℓ)/2 of the
string’s value v. Its components are h = RN(v) and ℓ = RN(v − h) themselves, except when ℓ is subnormal and was rounded to
exactly half an ulp of an odd h (then normalizing moves the tie
to the even neighbour; the value is the same).
(P3) Round trip. Two statements, both consequences of (P1) and (P2).
Text. A decimal v of at most 31 significant digits with |v| ≥ 2⁻⁹⁶⁸ (below, the trailing component is subnormal and short),
read by from_str and written with {} or {:e}, comes back as
the same decimal: the double-double read is within 2⁻¹⁰⁶ |v| < 1,24 · 10⁻³² |v| of v, less than half a unit of the 31st digit
(≥ 5 · 10⁻³² |v|). This is why the default is 31 digits and not
32 (10³¹ < 2¹⁰⁶ < 10³²): with 32 a short decimal can come back
as …29799999999999e74. Value. x.to_string().parse() is x
whenever x has at most 31 significant decimal digits, and
format!("{x:.1100e}").parse() is x for every finite x. In
general the default output does not parse back to the same
bits: a double-double is not a 106-bit number — ℓ may lie
arbitrarily far below h (1 + 2⁻⁹⁰⁰ is one) — so no fixed number
of digits identifies it (a divergence from the contract’s wording,
reported in Chapter 11).
§References
Knuth, TAOCP vol. 2, §4.4 (radix conversion). Clinger, “How to read floating point numbers accurately”, PLDI 1990 (the exact-arithmetic reader, Algorithm N here). Steele & White, “How to print floating-point numbers accurately”, PLDI 1990 (not used: no shortest-digits search is possible for double-doubles, see (P3)).
Structs§
- Parse
Double Double Error - A decimal string that is not a number.
Constants§
- DEFAULT_
DIGITS 🔒 - Significant digits of the default output (step O4).
- FIXED_
RANGE 🔒 - The exponents
ewritten in fixed notation (step O3). - MAX_
MAGNITUDE 🔒 - Step I2: decimal magnitudes beyond these are
∞and0. - MIN_
MAGNITUDE 🔒
Functions§
- decompose 🔒
|x| = m · 2ᵉfor a finitef64.- exact_
expansion 🔒 - Algorithm X: the digits
d₁…d_n(bytes0..=9) andeof a finite nonzero double-double. - fixed 🔒
d₁.d₂… × 10ᵉin fixed notation, with exactlyfracdigits after the point when given (the digits were rounded to fit).- magnitude 🔒
|x| = M · 2ᴱfor a finite nonzero double-double (the notation).- nearest_
double_ 🔒double - Steps I2–I4: the double-double nearest to
D · 10^q,D ≠ 0given by its digits. - nearest_
f64 🔒 - Algorithm N:
RN(num / den)for naturals,den > 0. - push_
digits 🔒 - round_
digits 🔒 - Rounds
d₁.d₂… × 10ᵉtokeepsignificant digits, half to even, and drops trailing zeros.keep ≤ 0rounds at or above the first digit; the result may be zero (no digits). - scan 🔒
- Step I1 for a numeric literal: the significant digits (no leading or
trailing zeros) and the exponent
qofD · 10^q.Noneif the text is not a number. - scientific 🔒
d₁.d₂… × 10ᵉin scientific notation (digitsnonempty).- write_
decimal 🔒 - Algorithm O.
always_scientificis the{:e}of step O3.