Skip to main content

xingo_extprec/
big.rs

1//! # Chapter 11.3 — Natural numbers for the decimal conversions
2//!
3//! ## Purpose
4//! The decimal conversions of Chapter 11.4 are *exact*: a double-double is
5//! a dyadic rational `M · 2ᴱ` whose decimal expansion is finite, and a
6//! decimal string is a rational `D · 10^q`. Both need integers of a few
7//! thousand bits and five operations on them. This module is that and no
8//! more — it is not a general big-integer library (no dependency is
9//! allowed at run time, and none is needed).
10//!
11//! ## Notation
12//! A natural number `N = Σ dᵢ βⁱ` is held as its digits `dᵢ` in base `β =
13//! 2³²`, least significant first. `bits(N)` is the position of its leading
14//! one bit plus one (`bits(0) = 0`).
15//!
16//! ## Algorithms
17//! All are the schoolbook ones (Knuth, TAOCP vol. 2, §4.3.1), linear or
18//! quadratic in the number of digits.
19//!
20//! **Algorithm Q (short quotient).** Input `N`, `D > 0` with `⌊N/D⌋ <
21//! 2¹²⁸`. Output `(⌊N/D⌋, N mod D ≠ 0)`.
22//!
23//! Q1. `R ← N`, `q ← 0`, `k ← max(bits(N) − bits(D), 0)`.
24//! Q2. For `i = k, k−1, …, 0`: if `D · 2ⁱ ≤ R`, set `R ← R − D · 2ⁱ` and
25//!     bit `i` of `q`.
26//! Q3. Return `(q, R ≠ 0)`.
27//!
28//! Binary long division: `k + 1` comparisons and at most as many
29//! subtractions of numbers of `bits(N)` bits. The conversions call it with
30//! `k ≤ 66`.
31//!
32//! ## Invariants
33//! (N1) *Normalized.* The most significant digit stored is nonzero; zero
34//!      is the empty digit string. `Nat::check_invariants` (test builds).
35//!
36//! ## References
37//! Knuth, TAOCP vol. 2, §4.3.1 (Algorithms A, S, M) and §4.4 (radix
38//! conversion).
39
40use core::cmp::Ordering;
41
42/// `10⁹`, the largest power of ten below `2³²`.
43const BILLION: u32 = 1_000_000_000;
44
45/// A natural number (the chapter).
46#[derive(Clone, Debug, PartialEq, Eq)]
47pub(crate) struct Nat {
48    /// Base-`2³²` digits, least significant first, no leading zero (N1).
49    limbs: Vec<u32>,
50}
51
52/// The low 32 bits of `x`.
53#[inline]
54#[allow(clippy::cast_possible_truncation)] // the truncation is the operation
55fn low32(x: u64) -> u32 {
56    x as u32
57}
58
59impl Nat {
60    /// Zero.
61    pub(crate) fn zero() -> Self {
62        Self { limbs: Vec::new() }
63    }
64
65    /// The value of a `u64`.
66    pub(crate) fn from_u64(x: u64) -> Self {
67        let mut n = Self {
68            limbs: vec![low32(x), low32(x >> 32)],
69        };
70        n.trim();
71        n
72    }
73
74    /// The value of a string of decimal digits (bytes `0..=9`, most
75    /// significant first).
76    pub(crate) fn from_decimal_digits(digits: &[u8]) -> Self {
77        let mut n = Self::zero();
78        for chunk in digits.chunks(9) {
79            let mut scale = 1_u32;
80            let mut value = 0_u32;
81            for &d in chunk {
82                debug_assert!(d <= 9, "not a decimal digit");
83                scale *= 10;
84                value = value * 10 + u32::from(d);
85            }
86            n.mul_small(scale);
87            n.add_small(value);
88        }
89        n
90    }
91
92    /// `10ᵏ`.
93    pub(crate) fn pow10(k: u32) -> Self {
94        let mut n = Self::from_u64(1);
95        for _ in 0..k / 9 {
96            n.mul_small(BILLION);
97        }
98        n.mul_small(10_u32.pow(k % 9));
99        n
100    }
101
102    /// Restores (N1).
103    fn trim(&mut self) {
104        while self.limbs.last() == Some(&0) {
105            self.limbs.pop();
106        }
107    }
108
109    /// `N = 0`.
110    pub(crate) fn is_zero(&self) -> bool {
111        self.limbs.is_empty()
112    }
113
114    /// `bits(N)`.
115    pub(crate) fn bits(&self) -> u64 {
116        match self.limbs.last() {
117            None => 0,
118            Some(&top) => 32 * self.limbs.len() as u64 - u64::from(top.leading_zeros()),
119        }
120    }
121
122    /// `N ← N · m`.
123    pub(crate) fn mul_small(&mut self, m: u32) {
124        let mut carry = 0_u64;
125        for limb in &mut self.limbs {
126            let t = u64::from(*limb) * u64::from(m) + carry;
127            *limb = low32(t);
128            carry = t >> 32;
129        }
130        if carry != 0 {
131            self.limbs.push(low32(carry));
132        }
133        self.trim();
134    }
135
136    /// `N ← N + a`.
137    pub(crate) fn add_small(&mut self, a: u32) {
138        let mut carry = u64::from(a);
139        for limb in &mut self.limbs {
140            if carry == 0 {
141                return;
142            }
143            let t = u64::from(*limb) + carry;
144            *limb = low32(t);
145            carry = t >> 32;
146        }
147        if carry != 0 {
148            self.limbs.push(low32(carry));
149        }
150    }
151
152    /// `N ← ⌊N / d⌋`, returning `N mod d`; `d > 0`.
153    pub(crate) fn div_rem_small(&mut self, d: u32) -> u32 {
154        debug_assert!(d != 0, "division by zero");
155        let mut rem = 0_u64;
156        for limb in self.limbs.iter_mut().rev() {
157            let t = (rem << 32) | u64::from(*limb);
158            *limb = low32(t / u64::from(d));
159            rem = t % u64::from(d);
160        }
161        self.trim();
162        low32(rem)
163    }
164
165    /// `N · 2ˢ`.
166    pub(crate) fn shl(&self, s: u64) -> Self {
167        if self.is_zero() {
168            return Self::zero();
169        }
170        let words = usize::try_from(s / 32).expect("shift fits memory");
171        let bits = s % 32;
172        let mut limbs = vec![0_u32; words];
173        limbs.reserve(self.limbs.len() + 1);
174        let mut carry = 0_u64;
175        for &limb in &self.limbs {
176            let t = (u64::from(limb) << bits) | carry;
177            limbs.push(low32(t));
178            carry = t >> 32;
179        }
180        if carry != 0 {
181            limbs.push(low32(carry));
182        }
183        Self { limbs }
184    }
185
186    /// `(⌊N / 2ˢ⌋, N mod 2ˢ)`.
187    pub(crate) fn split_at_bit(&self, s: u64) -> (Self, Self) {
188        let words = usize::try_from(s / 32).unwrap_or(usize::MAX);
189        if words >= self.limbs.len() {
190            return (Self::zero(), self.clone());
191        }
192        let bits = s % 32;
193        let mut low = Self {
194            limbs: self.limbs[..=words].to_vec(),
195        };
196        low.limbs[words] &= (1_u32 << bits) - 1;
197        low.trim();
198        let mut high = Vec::with_capacity(self.limbs.len() - words);
199        for i in words..self.limbs.len() {
200            let here = u64::from(self.limbs[i]) >> bits;
201            let above = self.limbs.get(i + 1).map_or(0, |&l| u64::from(l));
202            high.push(low32(here | (above << (32 - bits))));
203        }
204        let mut high = Self { limbs: high };
205        high.trim();
206        (high, low)
207    }
208
209    /// `N + M`.
210    pub(crate) fn add(&self, other: &Self) -> Self {
211        let (long, short) = if self.limbs.len() >= other.limbs.len() {
212            (self, other)
213        } else {
214            (other, self)
215        };
216        let mut limbs = Vec::with_capacity(long.limbs.len() + 1);
217        let mut carry = 0_u64;
218        for (i, &l) in long.limbs.iter().enumerate() {
219            let t = u64::from(l) + short.limbs.get(i).map_or(0, |&s| u64::from(s)) + carry;
220            limbs.push(low32(t));
221            carry = t >> 32;
222        }
223        if carry != 0 {
224            limbs.push(low32(carry));
225        }
226        Self { limbs }
227    }
228
229    /// `N − M`; requires `N ≥ M`.
230    pub(crate) fn sub(&self, other: &Self) -> Self {
231        debug_assert!(*self >= *other, "Nat::sub would be negative");
232        let mut limbs = Vec::with_capacity(self.limbs.len());
233        let mut borrow = 0_i64;
234        for (i, &l) in self.limbs.iter().enumerate() {
235            let t = i64::from(l) - other.limbs.get(i).map_or(0, |&s| i64::from(s)) - borrow;
236            borrow = i64::from(t < 0);
237            limbs.push(low32(t.rem_euclid(1_i64 << 32).unsigned_abs()));
238        }
239        debug_assert_eq!(borrow, 0, "Nat::sub underflowed");
240        let mut n = Self { limbs };
241        n.trim();
242        n
243    }
244
245    /// `N · M`.
246    pub(crate) fn mul(&self, other: &Self) -> Self {
247        if self.is_zero() || other.is_zero() {
248            return Self::zero();
249        }
250        let mut limbs = vec![0_u32; self.limbs.len() + other.limbs.len()];
251        for (i, &a) in self.limbs.iter().enumerate() {
252            let mut carry = 0_u64;
253            for (j, &b) in other.limbs.iter().enumerate() {
254                let t = u64::from(a) * u64::from(b) + u64::from(limbs[i + j]) + carry;
255                limbs[i + j] = low32(t);
256                carry = t >> 32;
257            }
258            limbs[i + other.limbs.len()] = low32(carry);
259        }
260        let mut n = Self { limbs };
261        n.trim();
262        n
263    }
264
265    /// Algorithm Q: `(⌊N / D⌋, N mod D ≠ 0)`; requires `D > 0` and a
266    /// quotient below `2¹²⁸`.
267    pub(crate) fn short_quotient(&self, den: &Self) -> (u128, bool) {
268        debug_assert!(!den.is_zero(), "division by zero");
269        let mut rem = self.clone(); // Q1
270        let mut q = 0_u128;
271        let k = self.bits().saturating_sub(den.bits());
272        debug_assert!(k < 128, "short_quotient: the quotient does not fit");
273        for i in (0..=k).rev() {
274            // Q2
275            let t = den.shl(i);
276            if t <= rem {
277                rem = rem.sub(&t);
278                q |= 1_u128 << i;
279            }
280        }
281        (q, !rem.is_zero()) // Q3
282    }
283
284    /// The decimal digits (bytes `0..=9`), most significant first; empty
285    /// for zero.
286    pub(crate) fn to_decimal_digits(&self) -> Vec<u8> {
287        let mut n = self.clone();
288        let mut out = Vec::new();
289        while !n.is_zero() {
290            let mut chunk = n.div_rem_small(BILLION);
291            for _ in 0..9 {
292                out.push(u8::try_from(chunk % 10).expect("a digit"));
293                chunk /= 10;
294            }
295        }
296        while out.last() == Some(&0) {
297            out.pop();
298        }
299        out.reverse();
300        out
301    }
302
303    /// Invariant (N1).
304    #[cfg(test)]
305    pub(crate) fn check_invariants(&self) -> Result<(), &'static str> {
306        if self.limbs.last() == Some(&0) {
307            return Err("N1: a leading zero digit");
308        }
309        Ok(())
310    }
311}
312
313impl PartialOrd for Nat {
314    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
315        Some(self.cmp(other))
316    }
317}
318
319impl Ord for Nat {
320    fn cmp(&self, other: &Self) -> Ordering {
321        self.limbs
322            .len()
323            .cmp(&other.limbs.len())
324            .then_with(|| self.limbs.iter().rev().cmp(other.limbs.iter().rev()))
325    }
326}
327
328#[cfg(test)]
329mod tests {
330    use super::*;
331
332    fn nat(s: &str) -> Nat {
333        let digits: Vec<u8> = s.bytes().map(|b| b - b'0').collect();
334        let n = Nat::from_decimal_digits(&digits);
335        n.check_invariants().unwrap();
336        n
337    }
338
339    fn dec(n: &Nat) -> String {
340        n.check_invariants().unwrap();
341        let d = n.to_decimal_digits();
342        if d.is_empty() {
343            "0".into()
344        } else {
345            d.iter().map(|&b| char::from(b + b'0')).collect()
346        }
347    }
348
349    #[test]
350    fn decimal_round_trip() {
351        for s in [
352            "0",
353            "7",
354            "4294967296",
355            "999999999",
356            "1000000000",
357            "340282366920938463463374607431768211456",
358            "123456789012345678901234567890123456789012345678901234567890",
359        ] {
360            assert_eq!(dec(&nat(s)), s);
361        }
362        assert_eq!(dec(&nat("000123")), "123");
363        assert_eq!(dec(&Nat::from_u64(u64::MAX)), "18446744073709551615");
364        assert_eq!(dec(&Nat::pow10(0)), "1");
365        assert_eq!(dec(&Nat::pow10(25)), "10000000000000000000000000");
366    }
367
368    #[test]
369    fn arithmetic() {
370        let a = nat("340282366920938463463374607431768211456"); // 2^128
371        let b = nat("18446744073709551615"); // 2^64 − 1
372        assert_eq!(a.bits(), 129);
373        assert_eq!(b.bits(), 64);
374        assert_eq!(Nat::zero().bits(), 0);
375        assert_eq!(dec(&a.add(&b)), "340282366920938463481821351505477763071");
376        assert_eq!(dec(&b.add(&a)), "340282366920938463481821351505477763071");
377        assert_eq!(dec(&a.sub(&b)), "340282366920938463444927863358058659841");
378        assert_eq!(dec(&a.sub(&a)), "0");
379        assert_eq!(
380            dec(&a.mul(&b)),
381            "6277101735386680763495507056286727952638980837032266301440"
382        );
383        assert_eq!(dec(&a.mul(&Nat::zero())), "0");
384        assert!(b < a);
385        assert!(a > b);
386        assert_eq!(a, a.clone());
387        assert!(nat("4294967296") > nat("4294967295"));
388    }
389
390    #[test]
391    fn shifts() {
392        let one = Nat::from_u64(1);
393        assert_eq!(
394            dec(&one.shl(128)),
395            "340282366920938463463374607431768211456"
396        );
397        assert_eq!(dec(&Nat::from_u64(5).shl(33)), "42949672960");
398        assert_eq!(dec(&Nat::zero().shl(77)), "0");
399        let n = nat("123456789012345678901234567890");
400        for s in [0, 1, 31, 32, 33, 64, 70, 96, 97, 200] {
401            let (high, low) = n.split_at_bit(s);
402            high.check_invariants().unwrap();
403            low.check_invariants().unwrap();
404            assert_eq!(high.shl(s).add(&low), n, "s = {s}");
405            assert!(low.bits() <= s);
406        }
407    }
408
409    #[test]
410    fn small_operations() {
411        let mut n = nat("99999999999999999999");
412        n.add_small(1);
413        assert_eq!(dec(&n), "100000000000000000000");
414        n.mul_small(7);
415        assert_eq!(dec(&n), "700000000000000000000");
416        assert_eq!(n.div_rem_small(9), 7);
417        assert_eq!(dec(&n), "77777777777777777777");
418        n.mul_small(0);
419        assert!(n.is_zero());
420        n.add_small(3);
421        assert_eq!(dec(&n), "3");
422    }
423
424    #[test]
425    fn short_quotients() {
426        let n = nat("1000000000000000000000000000000");
427        assert_eq!(
428            n.short_quotient(&nat("7")),
429            (142_857_142_857_142_857_142_857_142_857, true)
430        );
431        assert_eq!(
432            n.short_quotient(&nat("1000000000000")),
433            (1_000_000_000_000_000_000, false)
434        );
435        assert_eq!(nat("5").short_quotient(&nat("7")), (0, true));
436        assert_eq!(Nat::zero().short_quotient(&nat("7")), (0, false));
437        assert_eq!(nat("49").short_quotient(&nat("7")), (7, false));
438    }
439}