Skip to main content

Module decimal

Module decimal 

Source
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§

ParseDoubleDoubleError
A decimal string that is not a number.

Constants§

DEFAULT_DIGITS 🔒
Significant digits of the default output (step O4).
FIXED_RANGE 🔒
The exponents e written in fixed notation (step O3).
MAX_MAGNITUDE 🔒
Step I2: decimal magnitudes beyond these are ∞ and 0.
MIN_MAGNITUDE 🔒

Functions§

decompose 🔒
|x| = m · 2ᵉ for a finite f64.
exact_expansion 🔒
Algorithm X: the digits d₁…d_n (bytes 0..=9) and e of a finite nonzero double-double.
fixed 🔒
d₁.d₂… × 10ᵉ in fixed notation, with exactly frac digits 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 ≠ 0 given by its digits.
nearest_f64 🔒
Algorithm N: RN(num / den) for naturals, den > 0.
push_digits 🔒
round_digits 🔒
Rounds d₁.d₂… × 10ᵉ to keep significant digits, half to even, and drops trailing zeros. keep ≤ 0 rounds 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 q of D · 10^q. None if the text is not a number.
scientific 🔒
d₁.d₂… × 10ᵉ in scientific notation (digits nonempty).
write_decimal 🔒
Algorithm O. always_scientific is the {:e} of step O3.