Skip to main content

xingo_extprec/
decimal.rs

1//! # Chapter 11.4 — Decimal formatting and parsing
2//!
3//! ## Purpose
4//! `Display`, `LowerExp` and `FromStr` for [`DoubleDouble`]. The contract
5//! asks for *faithful* conversions (question E7: an error of at most one
6//! unit of the 32nd digit). Both are in fact **correctly rounded**: they are computed
7//! in exact integer arithmetic (Chapter 11.3), which is simpler to state
8//! and to test than a conversion carried out in double-double arithmetic
9//! itself, whose error would have to be bounded.
10//!
11//! ## Notation
12//! A finite nonzero double-double is `x = ± M · 2ᴱ` with `M` a natural
13//! number (`M = m_h 2^(e_h − E) ± m_ℓ 2^(e_ℓ − E)` from the two
14//! significands). Its *decimal expansion* `d₁.d₂d₃… × 10ᵉ`, `d₁ ≠ 0`, is
15//! finite, because `2` divides `10`. A decimal string is `v = ± D · 10^q`
16//! with `D` a natural number. `RN` rounds to the nearest `f64`, ties to
17//! even.
18//!
19//! ## Algorithms
20//! **Algorithm X (exact expansion).** Input `M`, `E`. Output the digits
21//! `d₁ d₂ … d_n` and `e`.
22//!
23//! X1. \[Integer.\] If `E ≥ 0`, the digits are those of `M · 2ᴱ` (radix
24//!     conversion by repeated division by `10⁹`) and `e = n − 1`. Stop.
25//! X2. \[Split.\] `I ← ⌊M / 2ˢ⌋`, `F ← M mod 2ˢ`, `s = −E`. The integer
26//!     digits are those of `I`.
27//! X3. \[Fraction.\] While `F ≠ 0`: `F ← 10⁹ F`; emit the nine digits of
28//!     `⌊F / 2ˢ⌋`; `F ← F mod 2ˢ`. (Each pass removes nine factors of two
29//!     from the denominator: at most `⌈s/9⌉` passes.)
30//! X4. \[Normalize.\] Drop the leading and trailing zeros; `e` is the
31//!     position of `d₁` relative to the point.
32//!
33//! **Algorithm O (output).** Input `x` and an optional precision `N` (the
34//! `{:.N}` of the format string).
35//!
36//! O1. \[Special.\] NaN is `NaN`, the infinities `inf` and `-inf`, zero `0`
37//!     (`-0` for the negative zero).
38//! O2. \[Expand.\] Algorithm X gives the digits and `e`.
39//! O3. \[Notation.\] For `{}`: *fixed* if `−5 ≤ e ≤ 31`, else *scientific*
40//!     (`d₁.d₂…e±k`, as Rust writes `{:e}` for an `f64`: no `+`, no
41//!     leading zero in the exponent). With a precision the choice uses the
42//!     `e` of the exact value; without, that of the rounded one. For
43//!     `{:e}`: always scientific (zero is `0e0`).
44//! O4. \[Round.\] Without a precision: to 31 significant digits, half to
45//!     even, trailing zeros dropped. With precision `N`: to `N` digits
46//!     after the point of the chosen notation, zero-padded.
47//! O5. \[Pad.\] Sign, width, fill and `+` as for the integers of `core`.
48//!
49//! **Algorithm I (input).** Input a string. Output a double-double or an
50//! error.
51//!
52//! I1. \[Scan.\] `[+-]` then `inf`, `infinity` or `nan` (any case), or
53//!     digits with at most one point and an optional exponent `e[+-]k`; at
54//!     least one digit; nothing else (no blanks). This gives `D` and `q`.
55//! I2. \[Range.\] If `v ≥ 10³¹⁰` return `±∞`; if `v < 10⁻³³⁰` return `±0`.
56//! I3. \[Leading.\] `h ← RN(D · 10^q)` by Algorithm N. If `h` is infinite
57//!     return `±∞`.
58//! I4. \[Trailing.\] `ℓ ← RN(D · 10^q − h)`, the difference formed exactly
59//!     as a fraction of naturals, rounded by Algorithm N. Return `±2Sum(h,
60//!     ℓ)` (the pair itself, but for the tie of invariant P2).
61//!
62//! **Algorithm N (nearest `f64` of a fraction).** Input naturals `A`, `B >
63//! 0`. Output `RN(A/B)`.
64//!
65//! N1. \[Scale.\] `t ← 65 − (bits(A) − bits(B))`; `(Q, sticky) ←` the
66//!     short quotient (Algorithm Q of Chapter 11.3) of `A · 2ᵗ` by `B`, so
67//!     that `2⁶⁴ ≤ Q < 2⁶⁶`.
68//! N2. \[Position.\] The unit of the result is `2ᶜ`, `c = max(msb(Q) − t −
69//!     52, −1074)` (53 significant bits, fewer in the subnormal range).
70//! N3. \[Round.\] Drop the `c + t` low bits of `Q`, rounding half to even
71//!     with `sticky` breaking the tie upward.
72//! N4. \[Encode.\] Assemble the bits; a significand of `2⁵³` moves to the
73//!     next binade, an exponent beyond the range is `+∞`.
74//!
75//! ## Invariants
76//! (P1) *Exact output.* The digits written are those of the decimal
77//!      expansion of `x` correctly rounded (half to even) at the stated
78//!      position; with a precision large enough (`{:.1100}` always is) the
79//!      output *is* `x`.
80//! (P2) *Correctly rounded input.* `from_str` returns the normalized pair
81//!      (D1) of value `RN(v) + RN(v − RN(v))`, within `ulp(ℓ)/2` of the
82//!      string's value `v`. Its components are `h = RN(v)` and `ℓ = RN(v −
83//!      h)` themselves, except when `ℓ` is subnormal and was rounded to
84//!      exactly half an ulp of an odd `h` (then normalizing moves the tie
85//!      to the even neighbour; the value is the same).
86//! (P3) *Round trip.* Two statements, both consequences of (P1) and (P2).
87//!      *Text.* A decimal `v` of at most 31 significant digits with `|v| ≥
88//!      2⁻⁹⁶⁸` (below, the trailing component is subnormal and short),
89//!      read by `from_str` and written with `{}` or `{:e}`, comes back as
90//!      the same decimal: the double-double read is within `2⁻¹⁰⁶ |v| <
91//!      1,24 · 10⁻³² |v|` of `v`, less than half a unit of the 31st digit
92//!      (`≥ 5 · 10⁻³² |v|`). This is why the default is 31 digits and not
93//!      32 (`10³¹ < 2¹⁰⁶ < 10³²`): with 32 a short decimal can come back
94//!      as `…29799999999999e74`. *Value.* `x.to_string().parse()` is `x`
95//!      whenever `x` has at most 31 significant decimal digits, and
96//!      `format!("{x:.1100e}").parse()` is `x` for every finite `x`. In
97//!      general the default output does **not** parse back to the same
98//!      bits: a double-double is not a 106-bit number — `ℓ` may lie
99//!      arbitrarily far below `h` (`1 + 2⁻⁹⁰⁰` is one) — so no fixed number
100//!      of digits identifies it (a divergence from the contract's wording,
101//!      reported in Chapter 11).
102//!
103//! ## References
104//! Knuth, TAOCP vol. 2, §4.4 (radix conversion). Clinger, "How to read
105//! floating point numbers accurately", PLDI 1990 (the exact-arithmetic
106//! reader, Algorithm N here). Steele & White, "How to print floating-point
107//! numbers accurately", PLDI 1990 (not used: no shortest-digits search is
108//! possible for double-doubles, see (P3)).
109
110use core::cmp::Ordering;
111use core::fmt;
112use core::str::FromStr;
113
114use crate::big::Nat;
115use crate::dd::DoubleDouble;
116
117/// Significant digits of the default output (step O4).
118const DEFAULT_DIGITS: i64 = 31;
119/// The exponents `e` written in fixed notation (step O3).
120const FIXED_RANGE: core::ops::RangeInclusive<i32> = -5..=31;
121/// Step I2: decimal magnitudes beyond these are `∞` and `0`.
122const MAX_MAGNITUDE: i64 = 310;
123const MIN_MAGNITUDE: i64 = -330;
124
125/// `|x| = m · 2ᵉ` for a finite `f64`.
126fn decompose(x: f64) -> (u64, i32) {
127    let bits = x.to_bits();
128    let frac = bits & ((1_u64 << 52) - 1);
129    let biased = i32::try_from((bits >> 52) & 0x7ff).expect("11 bits");
130    if biased == 0 {
131        (frac, -1074)
132    } else {
133        (frac | (1_u64 << 52), biased - 1075)
134    }
135}
136
137/// `|x| = M · 2ᴱ` for a finite nonzero double-double (the notation).
138fn magnitude(x: DoubleDouble) -> (Nat, i32) {
139    let (mh, eh) = decompose(x.hi());
140    let (ml, el) = decompose(x.lo());
141    if ml == 0 {
142        return (Nat::from_u64(mh), eh);
143    }
144    let e = eh.min(el);
145    let h = Nat::from_u64(mh).shl(u64::from((eh - e).unsigned_abs()));
146    let l = Nat::from_u64(ml).shl(u64::from((el - e).unsigned_abs()));
147    let same_sign = x.hi().is_sign_negative() == x.lo().is_sign_negative();
148    (if same_sign { h.add(&l) } else { h.sub(&l) }, e)
149}
150
151/// Algorithm X: the digits `d₁…d_n` (bytes `0..=9`) and `e` of a finite
152/// nonzero double-double.
153fn exact_expansion(x: DoubleDouble) -> (Vec<u8>, i32) {
154    let (m, e2) = magnitude(x);
155    let s = u64::from(e2.unsigned_abs());
156    let (int_digits, mut digits) = if e2 >= 0 {
157        (0, m.shl(s).to_decimal_digits()) // X1
158    } else {
159        let (int, mut frac) = m.split_at_bit(s); // X2
160        let mut digits = int.to_decimal_digits();
161        let int_digits = digits.len();
162        while !frac.is_zero() {
163            // X3
164            frac.mul_small(1_000_000_000);
165            let (top, rest) = frac.split_at_bit(s);
166            let chunk = top.to_decimal_digits();
167            digits.extend(core::iter::repeat_n(0, 9 - chunk.len()));
168            digits.extend(chunk);
169            frac = rest;
170        }
171        (int_digits, digits)
172    };
173    // X4. For an integer (X1) the point follows the last digit.
174    let point = if e2 >= 0 { digits.len() } else { int_digits };
175    let leading = digits.iter().take_while(|&&d| d == 0).count();
176    digits.drain(..leading);
177    while digits.last() == Some(&0) {
178        digits.pop();
179    }
180    let e = i32::try_from(point).expect("a few thousand digits")
181        - 1
182        - i32::try_from(leading).expect("a few thousand digits");
183    (digits, e)
184}
185
186/// Rounds `d₁.d₂… × 10ᵉ` to `keep` significant digits, half to even, and
187/// drops trailing zeros. `keep ≤ 0` rounds at or above the first digit;
188/// the result may be zero (no digits).
189fn round_digits(digits: &mut Vec<u8>, e: &mut i32, keep: i64) {
190    let Ok(k) = usize::try_from(keep) else {
191        digits.clear();
192        return;
193    };
194    if k >= digits.len() {
195        return;
196    }
197    let next = digits[k];
198    let rest_nonzero = digits[k + 1..].iter().any(|&d| d != 0);
199    let odd = k > 0 && digits[k - 1] % 2 == 1;
200    let up = next > 5 || (next == 5 && (rest_nonzero || odd));
201    digits.truncate(k);
202    if up {
203        let mut i = k;
204        loop {
205            if i == 0 {
206                // All nines (or no digit kept): 10^(e+1).
207                digits.insert(0, 1);
208                digits.truncate(k.max(1));
209                *e += 1;
210                break;
211            }
212            i -= 1;
213            if digits[i] == 9 {
214                digits[i] = 0;
215            } else {
216                digits[i] += 1;
217                break;
218            }
219        }
220    }
221    while digits.last() == Some(&0) {
222        digits.pop();
223    }
224}
225
226fn push_digits(out: &mut String, digits: impl IntoIterator<Item = u8>) {
227    out.extend(digits.into_iter().map(|d| char::from(b'0' + d)));
228}
229
230/// `d₁.d₂… × 10ᵉ` in fixed notation, with exactly `frac` digits after the
231/// point when given (the digits were rounded to fit).
232fn fixed(digits: &[u8], e: i32, frac: Option<usize>) -> String {
233    let mut out = String::new();
234    let mut tail: Vec<u8> = Vec::new();
235    match usize::try_from(e) {
236        Ok(e) if !digits.is_empty() => {
237            let int = e + 1;
238            push_digits(&mut out, digits.iter().copied().take(int));
239            push_digits(
240                &mut out,
241                core::iter::repeat_n(0, int.saturating_sub(digits.len())),
242            );
243            tail.extend(digits.iter().skip(int));
244        }
245        _ => {
246            out.push('0');
247            if !digits.is_empty() {
248                let zeros = usize::try_from(-(e + 1)).expect("e < 0");
249                tail.extend(core::iter::repeat_n(0, zeros));
250                tail.extend(digits);
251            }
252        }
253    }
254    if let Some(n) = frac {
255        debug_assert!(
256            tail.len() <= n,
257            "the digits were not rounded to the precision"
258        );
259        tail.resize(n, 0);
260    }
261    if !tail.is_empty() {
262        out.push('.');
263        push_digits(&mut out, tail);
264    }
265    out
266}
267
268/// `d₁.d₂… × 10ᵉ` in scientific notation (`digits` nonempty).
269fn scientific(digits: &[u8], e: i32, frac: Option<usize>) -> String {
270    let mut out = String::new();
271    push_digits(&mut out, digits.iter().copied().take(1));
272    let mut tail: Vec<u8> = digits[1..].to_vec();
273    if let Some(n) = frac {
274        debug_assert!(
275            tail.len() <= n,
276            "the digits were not rounded to the precision"
277        );
278        tail.resize(n, 0);
279    }
280    if !tail.is_empty() {
281        out.push('.');
282        push_digits(&mut out, tail);
283    }
284    out.push('e');
285    out.push_str(&e.to_string());
286    out
287}
288
289/// Algorithm O. `always_scientific` is the `{:e}` of step O3.
290#[allow(clippy::float_cmp)] // the zero test is exact
291fn write_decimal(
292    x: DoubleDouble,
293    f: &mut fmt::Formatter<'_>,
294    always_scientific: bool,
295) -> fmt::Result {
296    let negative = x.hi().is_sign_negative();
297    // O1. `pad_integral` and not `pad`: a precision must not truncate.
298    if x.is_nan() {
299        return f.pad_integral(true, "", "NaN");
300    }
301    if !x.is_finite() {
302        return f.pad_integral(!negative, "", "inf");
303    }
304    let precision = f.precision();
305    let body = if x.hi() == 0.0 {
306        if always_scientific {
307            scientific(&[0], 0, precision)
308        } else {
309            fixed(&[], 0, precision)
310        }
311    } else {
312        let (mut digits, mut e) = exact_expansion(x); // O2
313        let is_fixed = |e: i32| !always_scientific && FIXED_RANGE.contains(&e); // O3
314        match precision {
315            None => {
316                round_digits(&mut digits, &mut e, DEFAULT_DIGITS); // O4
317                if is_fixed(e) {
318                    fixed(&digits, e, None)
319                } else {
320                    scientific(&digits, e, None)
321                }
322            }
323            Some(n) => {
324                let n_i64 = i64::try_from(n).unwrap_or(i64::MAX);
325                if is_fixed(e) {
326                    let keep = n_i64.saturating_add(i64::from(e) + 1);
327                    round_digits(&mut digits, &mut e, keep);
328                    fixed(&digits, e, Some(n))
329                } else {
330                    round_digits(&mut digits, &mut e, n_i64.saturating_add(1));
331                    scientific(&digits, e, Some(n))
332                }
333            }
334        }
335    };
336    f.pad_integral(!negative, "", &body) // O5
337}
338
339/// Decimal, scientific notation when the exponent calls for it; `{:.N}`
340/// gives `N` digits after the point, the default is the value correctly
341/// rounded to 31 significant digits, trailing zeros dropped (Algorithm O
342/// of Chapter 11.4). A decimal of at most 31 digits that was read by
343/// `from_str` is written back as the same decimal; the output parses back
344/// to the same *bits* whenever the value has at most 31 significant
345/// decimal digits — see invariant P3 for why no fixed number of digits can
346/// do so in general (`{:.1100e}` always does).
347impl fmt::Display for DoubleDouble {
348    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
349        write_decimal(*self, f, false)
350    }
351}
352
353/// Scientific notation as for `f64`: `d.ddd` then `e` and the decimal
354/// exponent, without `+` or leading zeros (`1.5e-7`, `1e0`, `0e0`).
355/// `{:e}` gives the value correctly rounded to the 31 significant digits
356/// of `Display`, trailing zeros dropped; `{:.Ne}` gives `N` digits after
357/// the point, correctly rounded (half to even), zero-padded.
358impl fmt::LowerExp for DoubleDouble {
359    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
360        write_decimal(*self, f, true)
361    }
362}
363
364/// A decimal string that is not a number.
365#[derive(Clone, Debug, PartialEq, Eq)]
366pub struct ParseDoubleDoubleError;
367
368impl fmt::Display for ParseDoubleDoubleError {
369    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
370        f.write_str("invalid double-double literal")
371    }
372}
373
374impl core::error::Error for ParseDoubleDoubleError {}
375
376/// Algorithm N: `RN(num / den)` for naturals, `den > 0`.
377fn nearest_f64(num: &Nat, den: &Nat) -> f64 {
378    if num.is_zero() {
379        return 0.0;
380    }
381    // N1.
382    let d = i64::try_from(num.bits()).expect("bits fit i64")
383        - i64::try_from(den.bits()).expect("bits fit i64");
384    let t = 65 - d;
385    let (q, sticky) = if t >= 0 {
386        num.shl(t.unsigned_abs()).short_quotient(den)
387    } else {
388        num.short_quotient(&den.shl(t.unsigned_abs()))
389    };
390    debug_assert!(q >> 64 != 0 && q >> 66 == 0, "N1: 2^64 <= Q < 2^66");
391    // N2.
392    let msb = i64::from(q.ilog2());
393    let unit = (msb - t - 52).max(-1074);
394    let drop = unit + t;
395    debug_assert!(drop >= 12, "N2: at most 53 bits are kept");
396    let Ok(drop) = u32::try_from(drop) else {
397        return 0.0;
398    };
399    if drop > 127 {
400        return 0.0; // Q < 2^66 is below half a unit
401    }
402    // N3.
403    let mut m = u64::try_from(q >> drop).expect("at most 54 bits");
404    let rem = q & ((1_u128 << drop) - 1);
405    let half = 1_u128 << (drop - 1);
406    let up = match rem.cmp(&half) {
407        Ordering::Greater => true,
408        Ordering::Equal => sticky || m % 2 == 1,
409        Ordering::Less => false,
410    };
411    m += u64::from(up);
412    // N4.
413    let mut unit = unit;
414    if m == 1_u64 << 53 {
415        m >>= 1;
416        unit += 1;
417    }
418    if m < 1_u64 << 52 {
419        debug_assert_eq!(unit, -1074, "N4: a short significand is subnormal");
420        return f64::from_bits(m);
421    }
422    let biased = unit + 52 + 1023;
423    if biased >= 2047 {
424        return f64::INFINITY;
425    }
426    let biased = u64::try_from(biased).expect("N2: unit >= -1074");
427    f64::from_bits((biased << 52) | (m - (1_u64 << 52)))
428}
429
430/// Step I1 for a numeric literal: the significant digits (no leading or
431/// trailing zeros) and the exponent `q` of `D · 10^q`. `None` if the text
432/// is not a number.
433fn scan(text: &[u8]) -> Option<(Vec<u8>, i64)> {
434    /// Exponents saturate here: far beyond any representable magnitude,
435    /// yet small enough that sums with a digit count cannot overflow.
436    const EXPONENT_CAP: i64 = 1_000_000_000_000;
437    let mut digits = Vec::new();
438    let mut i = 0;
439    let mut frac_len = 0_i64;
440    let mut seen_point = false;
441    while i < text.len() {
442        match text[i] {
443            c @ b'0'..=b'9' => {
444                digits.push(c - b'0');
445                frac_len += i64::from(seen_point);
446            }
447            b'.' if !seen_point => seen_point = true,
448            _ => break,
449        }
450        i += 1;
451    }
452    if digits.is_empty() {
453        return None;
454    }
455    let mut exponent = 0_i64;
456    if i < text.len() {
457        if !matches!(text[i], b'e' | b'E') {
458            return None;
459        }
460        i += 1;
461        let negative = match text.get(i) {
462            Some(b'-') => {
463                i += 1;
464                true
465            }
466            Some(b'+') => {
467                i += 1;
468                false
469            }
470            _ => false,
471        };
472        if i == text.len() {
473            return None;
474        }
475        for &c in &text[i..] {
476            if !c.is_ascii_digit() {
477                return None;
478            }
479            exponent = (exponent * 10 + i64::from(c - b'0')).min(EXPONENT_CAP);
480        }
481        if negative {
482            exponent = -exponent;
483        }
484    }
485    let leading = digits.iter().take_while(|&&d| d == 0).count();
486    digits.drain(..leading);
487    let mut q = exponent - frac_len;
488    while digits.last() == Some(&0) {
489        digits.pop();
490        q += 1;
491    }
492    Some((digits, q))
493}
494
495/// Steps I2–I4: the double-double nearest to `D · 10^q`, `D ≠ 0` given by
496/// its digits.
497fn nearest_double_double(digits: &[u8], q: i64) -> DoubleDouble {
498    // I2.
499    let magnitude = i64::try_from(digits.len())
500        .unwrap_or(i64::MAX)
501        .saturating_add(q);
502    if magnitude > MAX_MAGNITUDE {
503        return DoubleDouble::INFINITY;
504    }
505    if magnitude < MIN_MAGNITUDE {
506        return DoubleDouble::ZERO;
507    }
508    let d = Nat::from_decimal_digits(digits);
509    let scale = Nat::pow10(u32::try_from(q.unsigned_abs()).expect("bounded by I2"));
510    let (num, den) = if q >= 0 {
511        (d.mul(&scale), Nat::from_u64(1))
512    } else {
513        (d, scale)
514    };
515    // I3.
516    let hi = nearest_f64(&num, &den);
517    if !hi.is_finite() || hi.to_bits() == 0 {
518        return DoubleDouble::from_f64(hi);
519    }
520    // I4: v − hi = (a − b) / c with hi = m 2^k.
521    let (m, k) = decompose(hi);
522    let m = Nat::from_u64(m);
523    let shift = u64::from(k.unsigned_abs());
524    let (a, b, c) = if k >= 0 {
525        (num, m.shl(shift).mul(&den), den)
526    } else {
527        (num.shl(shift), m.mul(&den), den.shl(shift))
528    };
529    let lo = match a.cmp(&b) {
530        Ordering::Equal => 0.0,
531        Ordering::Greater => nearest_f64(&a.sub(&b), &c),
532        Ordering::Less => -nearest_f64(&b.sub(&a), &c),
533    };
534    // Normalized already, except when `lo` was rounded in the subnormal
535    // range to exactly half an ulp of an odd `hi`; the sum is exact (P2).
536    DoubleDouble::from_sum(hi, lo)
537}
538
539/// Decimal or scientific notation, `inf`, `nan`; faithful (question E7) —
540/// in fact correctly rounded: the leading component is the `f64` nearest
541/// to the string's value and the trailing one the `f64` nearest to the
542/// rest (Algorithm I of Chapter 11.4).
543impl FromStr for DoubleDouble {
544    type Err = ParseDoubleDoubleError;
545    fn from_str(s: &str) -> Result<Self, Self::Err> {
546        // I1.
547        let (negative, rest) = match s.as_bytes().first() {
548            Some(b'-') => (true, &s[1..]),
549            Some(b'+') => (false, &s[1..]),
550            _ => (false, s),
551        };
552        let magnitude = if rest.eq_ignore_ascii_case("inf") || rest.eq_ignore_ascii_case("infinity")
553        {
554            Self::INFINITY
555        } else if rest.eq_ignore_ascii_case("nan") {
556            Self::NAN
557        } else {
558            let (digits, q) = scan(rest.as_bytes()).ok_or(ParseDoubleDoubleError)?;
559            if digits.is_empty() {
560                Self::ZERO
561            } else {
562                nearest_double_double(&digits, q)
563            }
564        };
565        Ok(if negative { -magnitude } else { magnitude })
566    }
567}
568
569#[cfg(test)]
570#[allow(clippy::disallowed_methods)] // L2.4 (Chapter 11.11): the tests may use the libm of `f64` (clippy.toml)
571#[allow(clippy::float_cmp)] // the tests compare exact values
572mod tests {
573    use super::*;
574
575    type Dd = DoubleDouble;
576
577    fn parse(s: &str) -> Dd {
578        s.parse().unwrap_or_else(|_| panic!("{s:?} does not parse"))
579    }
580
581    #[test]
582    fn displays_short_values_exactly() {
583        for (x, s) in [
584            (0.0, "0"),
585            (-0.0, "-0"),
586            (1.0, "1"),
587            (-1.5, "-1.5"),
588            (0.5, "0.5"),
589            (1024.0, "1024"),
590            (0.001_953_125, "0.001953125"),
591            (1e15, "1000000000000000"),
592            (9_007_199_254_740_992.0, "9007199254740992"),
593            (0.000_030_517_578_125, "0.000030517578125"),
594        ] {
595            assert_eq!(Dd::from_f64(x).to_string(), s);
596            assert_eq!(parse(s), Dd::from_f64(x));
597            assert_eq!(parse(s).hi().to_bits(), x.to_bits());
598        }
599        assert_eq!(Dd::NAN.to_string(), "NaN");
600        assert_eq!(Dd::INFINITY.to_string(), "inf");
601        assert_eq!((-Dd::INFINITY).to_string(), "-inf");
602    }
603
604    #[test]
605    fn displays_thirty_two_digits() {
606        let third = Dd::ONE / 3.0;
607        assert_eq!(third.to_string(), "0.3333333333333333333333333333333");
608        // The f64 nearest to 0.1 is not 0.1.
609        assert_eq!(
610            Dd::from_f64(0.1).to_string(),
611            "0.1000000000000000055511151231258"
612        );
613        assert_eq!(
614            Dd::from_f64(2.0).sqrt().to_string(),
615            "1.41421356237309504880168872421"
616        );
617        // 1 + 2^-900 is 1 to 31 digits (invariant P3).
618        let x = Dd::ONE + 2f64.powi(-900);
619        assert_eq!(x.to_string(), "1");
620        assert_ne!(parse(&x.to_string()), x);
621        assert_eq!(parse(&format!("{x:.1100}")), x);
622    }
623
624    #[test]
625    fn notation_follows_the_exponent() {
626        assert_eq!(Dd::from_f64(1e-5).to_string()[..7].to_string(), "0.00001");
627        assert_eq!(
628            Dd::from_f64(2f64.powi(-20)).to_string(),
629            "9.5367431640625e-7"
630        );
631        assert_eq!(
632            parse("1e31").to_string(),
633            "10000000000000000000000000000000"
634        );
635        assert_eq!(parse("1e32").to_string(), "1e32");
636        assert_eq!(parse("-1.25e-200").to_string(), "-1.25e-200");
637        assert_eq!(parse("123456789e40").to_string(), "1.23456789e48");
638        // Rounding may carry into the next decade.
639        let nines = parse("9.99999999999999999999999999999999999");
640        assert_eq!(nines.to_string(), "10");
641    }
642
643    #[test]
644    fn precision_counts_digits_after_the_point() {
645        let third = Dd::ONE / 3.0;
646        assert_eq!(format!("{third:.3}"), "0.333");
647        assert_eq!(format!("{third:.0}"), "0");
648        assert_eq!(format!("{:.2}", Dd::from_f64(2.675)), "2.67"); // 2.67499999…
649        assert_eq!(format!("{:.1}", Dd::from_f64(0.25)), "0.2"); // tie to even
650        assert_eq!(format!("{:.1}", Dd::from_f64(0.75)), "0.8");
651        assert_eq!(format!("{:.0}", Dd::from_f64(0.5)), "0");
652        assert_eq!(format!("{:.0}", Dd::from_f64(1.5)), "2");
653        assert_eq!(format!("{:.0}", Dd::from_f64(0.75)), "1");
654        assert_eq!(format!("{:.2}", Dd::from_f64(9.999)), "10.00");
655        assert_eq!(format!("{:.2}", Dd::from_f64(-0.001)), "-0.00");
656        assert_eq!(format!("{:.3}", Dd::ZERO), "0.000");
657        assert_eq!(format!("{:.4}", Dd::from_f64(1.0)), "1.0000");
658        assert_eq!(format!("{:.2}", parse("1.2345e40")), "1.23e40");
659        assert_eq!(format!("{:.0}", parse("9.5e40")), "1e41");
660        assert_eq!(format!("{:.3}", parse("1e-7")), "1.000e-7");
661        assert_eq!(format!("{third:.40}").len(), 42);
662    }
663
664    #[test]
665    fn lower_exp_follows_f64() {
666        // The same strings as f64. Without a precision f64 writes the
667        // shortest digits that identify the f64, we write the value: they
668        // agree when the value has few digits.
669        for x in [
670            1.0,
671            -1.5,
672            0.0,
673            -0.0,
674            1024.0,
675            0.001_953_125,
676            1e15,
677            2f64.powi(-20),
678        ] {
679            assert_eq!(format!("{:e}", Dd::from_f64(x)), format!("{x:e}"));
680            assert_eq!(format!("{:12e}|", Dd::from_f64(x)), format!("{x:12e}|"));
681            assert_eq!(format!("{:+e}", Dd::from_f64(x)), format!("{x:+e}"));
682        }
683        // With a precision both are the exact value correctly rounded.
684        for x in [
685            1.0,
686            -1.5,
687            0.0,
688            -0.0,
689            0.1,
690            2.5e-7,
691            6.25e100,
692            0.125,
693            9.5,
694            f64::MAX,
695            5e-324,
696        ] {
697            assert_eq!(format!("{:.3e}", Dd::from_f64(x)), format!("{x:.3e}"));
698            assert_eq!(format!("{:+.0e}", Dd::from_f64(x)), format!("{x:+.0e}"));
699            assert_eq!(
700                format!("{:<12.1e}|", Dd::from_f64(x)),
701                format!("{x:<12.1e}|")
702            );
703            assert_eq!(format!("{:012.2e}", Dd::from_f64(x)), format!("{x:012.2e}"));
704            assert_eq!(format!("{:.25e}", Dd::from_f64(x)), format!("{x:.25e}"));
705        }
706        assert_eq!(format!("{:e}", Dd::NAN), "NaN");
707        assert_eq!(format!("{:e}", Dd::INFINITY), "inf");
708        assert_eq!(format!("{:.2e}", -Dd::INFINITY), "-inf");
709        // 31 digits without a precision, trailing zeros dropped.
710        let third = Dd::ONE / 3.0;
711        assert_eq!(format!("{third:e}"), "3.333333333333333333333333333333e-1");
712        assert_eq!(format!("{:e}", parse("1e31")), "1e31");
713        assert_eq!(format!("{:e}", parse("123.5")), "1.235e2");
714        // With a precision: digits after the point, half to even, carries.
715        assert_eq!(format!("{third:.5e}"), "3.33333e-1");
716        assert_eq!(format!("{:.0e}", Dd::from_f64(2.5)), "2e0");
717        assert_eq!(format!("{:.0e}", Dd::from_f64(3.5)), "4e0");
718        assert_eq!(format!("{:.1e}", Dd::from_f64(9.96)), "1.0e1");
719        assert_eq!(format!("{:.2e}", parse("9.995e-10")), "9.99e-10"); // below the tie in dd
720        assert_eq!(format!("{:.3e}", Dd::ZERO), "0.000e0");
721        assert_eq!(format!("{third:.40e}").len(), 2 + 40 + 3);
722        // Round trips.
723        for s in [
724            "1e0",
725            "-2.5e-7",
726            "1.2345678901234567890123456789e-200",
727            "9.99e307",
728        ] {
729            assert_eq!(format!("{:e}", parse(s)), s);
730        }
731        let x = Dd::ONE + 2f64.powi(-900);
732        assert_eq!(parse(&format!("{x:.1100e}")), x);
733    }
734
735    #[test]
736    fn width_fill_and_sign() {
737        let x = Dd::from_f64(1.5);
738        assert_eq!(format!("{x:8}"), "     1.5");
739        assert_eq!(format!("{x:<8}|"), "1.5     |");
740        assert_eq!(format!("{x:+}"), "+1.5");
741        assert_eq!(format!("{x:08.2}"), "00001.50");
742        assert_eq!(format!("{:+}", Dd::INFINITY), "+inf");
743        assert_eq!(format!("{:>5}", Dd::NAN), "  NaN");
744        assert_eq!(format!("{:.1}", Dd::NAN), "NaN");
745        assert_eq!(format!("{:6.1}", -Dd::INFINITY), "  -inf");
746    }
747
748    #[test]
749    fn parses_the_grammar() {
750        assert_eq!(parse("3"), Dd::from_f64(3.0));
751        assert_eq!(parse("+3."), Dd::from_f64(3.0));
752        assert_eq!(parse(".5"), Dd::from_f64(0.5));
753        assert_eq!(parse("-00012.50"), Dd::from_f64(-12.5));
754        assert_eq!(parse("1e3"), Dd::from_f64(1000.0));
755        assert_eq!(parse("1E+3"), Dd::from_f64(1000.0));
756        assert_eq!(parse("2500e-2"), Dd::from_f64(25.0));
757        assert_eq!(parse("0e999999999999999999999"), Dd::ZERO);
758        assert_eq!(parse("-0").hi().to_bits(), (-0.0_f64).to_bits());
759        assert_eq!(parse("inf"), Dd::INFINITY);
760        assert_eq!(parse("-Infinity"), -Dd::INFINITY);
761        assert!(parse("NaN").is_nan() && parse("-nan").is_nan());
762        for bad in [
763            "", "+", "-", ".", "e5", "1e", "1e+", "1.2.3", " 1", "1 ", "1_0", "0x10", "1e5.0",
764            "infinit", "--1", "1f",
765        ] {
766            assert_eq!(bad.parse::<Dd>(), Err(ParseDoubleDoubleError), "{bad:?}");
767        }
768        assert_eq!(
769            ParseDoubleDoubleError.to_string(),
770            "invalid double-double literal"
771        );
772    }
773
774    #[test]
775    fn parses_correctly_rounded() {
776        // 0.1 = hi + lo with hi the nearest f64 and lo the rest.
777        let tenth = parse("0.1");
778        assert_eq!(tenth.hi().to_bits(), 0.1_f64.to_bits());
779        assert_eq!(tenth, Dd::ONE / 10.0);
780        assert_eq!(tenth.to_string(), "0.1");
781        // Halfway cases of the leading component go to even.
782        assert_eq!(
783            parse("9007199254740993"),
784            Dd::from_parts(9_007_199_254_740_992.0, 1.0)
785        );
786        assert_eq!(
787            parse("9007199254740995"),
788            Dd::from_parts(9_007_199_254_740_996.0, -1.0)
789        );
790        // π to 40 digits.
791        let pi = parse("3.141592653589793238462643383279502884197");
792        assert_eq!(pi.hi().to_bits(), core::f64::consts::PI.to_bits());
793        assert_eq!(pi.lo(), 1.224_646_799_147_353_2e-16);
794        assert_eq!(pi.to_string(), "3.14159265358979323846264338328");
795    }
796
797    #[test]
798    fn parses_the_ends_of_the_range() {
799        assert_eq!(parse("1e400"), Dd::INFINITY);
800        assert_eq!(parse("-1e309"), -Dd::INFINITY);
801        assert_eq!(parse("1.7976931348623157e308").hi(), f64::MAX);
802        assert_eq!(parse("1.7976931348623159e308"), Dd::INFINITY);
803        assert_eq!(parse("1e-400"), Dd::ZERO);
804        assert_eq!(parse("1e-99999999999999999999"), Dd::ZERO);
805        assert_eq!(parse("1e99999999999999999999"), Dd::INFINITY);
806        let eta = f64::from_bits(1);
807        assert_eq!(parse("5e-324"), Dd::from_f64(eta));
808        assert_eq!(parse("2.4703282292062327e-324"), Dd::ZERO); // just below η/2
809        assert_eq!(parse("2.4703282292062328e-324"), Dd::from_f64(eta));
810        assert_eq!(parse("2.2250738585072014e-308").hi(), f64::MIN_POSITIVE);
811        // The exact expansion of η has 751 significant digits.
812        let s = format!("{:.1100}", Dd::from_f64(eta));
813        assert!(s.starts_with("4.940656458412465441765687928682213723650598"));
814        assert!(s.ends_with("e-324") && s.len() == 2 + 1100 + 5);
815        assert_eq!(parse(&s), Dd::from_f64(eta));
816        assert_eq!(
817            parse(&format!("{:.1100}", Dd::from_f64(f64::MAX))).hi(),
818            f64::MAX
819        );
820    }
821
822    #[test]
823    fn round_digits_cases() {
824        let round = |s: &str, e: i32, keep: i64| {
825            let mut d: Vec<u8> = s.bytes().map(|b| b - b'0').collect();
826            let mut e = e;
827            round_digits(&mut d, &mut e, keep);
828            (
829                d.iter().map(|&b| char::from(b + b'0')).collect::<String>(),
830                e,
831            )
832        };
833        assert_eq!(round("12345", 0, 3), ("123".into(), 0));
834        assert_eq!(round("1235", 0, 3), ("124".into(), 0)); // tie, odd
835        assert_eq!(round("1225", 0, 3), ("122".into(), 0)); // tie, even
836        assert_eq!(round("12251", 0, 3), ("123".into(), 0));
837        assert_eq!(round("9996", 2, 3), ("1".into(), 3));
838        assert_eq!(round("5", 0, 0), (String::new(), 0)); // tie to zero
839        assert_eq!(round("51", 0, 0), ("1".into(), 1));
840        assert_eq!(round("9", 0, 0), ("1".into(), 1));
841        assert_eq!(round("9", 0, -1), (String::new(), 0));
842        assert_eq!(round("12", 0, 5), ("12".into(), 0));
843    }
844}