zenith_float_num/
integer.rs

1//! Arbitrary-precision signed integers on `Word` limbs.
2
3use crate::common::util::add_carry;
4use crate::common::util::sub_borrow;
5use crate::defs::DoubleWord;
6use crate::defs::RoundingMode;
7use crate::defs::Sign;
8use crate::defs::Word;
9use crate::defs::DEFAULT_P;
10use crate::defs::WORD_BIT_SIZE;
11use crate::ExactNum;
12use alloc::vec;
13use alloc::vec::Vec;
14use core::cmp::Ordering;
15
16/// Arbitrary-precision signed integer. Distinct from [`ExactNum`], which is floating-point.
17///
18/// Limbs are little-endian `Word`s with no leading zeros. Zero is an empty limb
19/// vector and a positive sign.
20#[derive(Clone, Debug, Eq)]
21pub struct ExactInt {
22    sign: Sign,
23    limbs: Vec<Word>,
24}
25
26impl ExactInt {
27    /// The integer `0`.
28    pub fn zero() -> Self {
29        Self {
30            sign: Sign::Pos,
31            limbs: Vec::new(),
32        }
33    }
34
35    /// The integer `1`.
36    pub fn one() -> Self {
37        Self::from_u64(1)
38    }
39
40    fn normalize(&mut self) {
41        while self.limbs.last().is_some_and(|w| *w == 0) {
42            self.limbs.pop();
43        }
44        if self.limbs.is_empty() {
45            self.sign = Sign::Pos;
46        }
47    }
48
49    fn from_limbs(sign: Sign, limbs: Vec<Word>) -> Self {
50        let mut s = Self { sign, limbs };
51        s.normalize();
52        s
53    }
54
55    /// Integer from `u64`.
56    pub fn from_u64(n: u64) -> Self {
57        Self::from_u128(n as u128)
58    }
59
60    /// Integer from `u128`.
61    pub fn from_u128(mut n: u128) -> Self {
62        if n == 0 {
63            return Self::zero();
64        }
65        let mut limbs = Vec::new();
66        while n > 0 {
67            limbs.push(n as Word);
68            n >>= WORD_BIT_SIZE;
69        }
70        Self {
71            sign: Sign::Pos,
72            limbs,
73        }
74    }
75
76    /// Integer from `i64`.
77    pub fn from_i64(n: i64) -> Self {
78        Self::from_i128(n as i128)
79    }
80
81    /// Integer from `i128`.
82    pub fn from_i128(n: i128) -> Self {
83        if n == i128::MIN {
84            let mut v = Self::from_u128(1u128 << 127);
85            v.sign = Sign::Neg;
86            return v;
87        }
88        let mut v = Self::from_u128(n.unsigned_abs());
89        if n < 0 {
90            v.sign = Sign::Neg;
91        }
92        v
93    }
94
95    /// True if the value is `0`.
96    pub fn is_zero(&self) -> bool {
97        self.limbs.is_empty()
98    }
99
100    /// True if the value is strictly negative.
101    pub fn is_negative(&self) -> bool {
102        self.sign == Sign::Neg && !self.is_zero()
103    }
104
105    /// `-1`, `0`, or `+1`.
106    pub fn signum(&self) -> Self {
107        if self.is_zero() {
108            Self::zero()
109        } else if self.sign == Sign::Neg {
110            Self::from_i64(-1)
111        } else {
112            Self::one()
113        }
114    }
115
116    /// Number of bits in `|self|`. Zero has bit length `0`.
117    pub fn bit_length(&self) -> usize {
118        match self.limbs.last() {
119            None => 0,
120            Some(last) => {
121                (self.limbs.len() - 1) * WORD_BIT_SIZE
122                    + (WORD_BIT_SIZE - last.leading_zeros() as usize)
123            }
124        }
125    }
126
127    fn cmp_abs(a: &[Word], b: &[Word]) -> Ordering {
128        match a.len().cmp(&b.len()) {
129            Ordering::Equal => {
130                for (x, y) in a.iter().rev().zip(b.iter().rev()) {
131                    match x.cmp(y) {
132                        Ordering::Equal => {}
133                        o => return o,
134                    }
135                }
136                Ordering::Equal
137            }
138            o => o,
139        }
140    }
141
142    /// Compare as signed integers.
143    pub fn cmp(&self, other: &Self) -> Ordering {
144        if self.is_zero() && other.is_zero() {
145            return Ordering::Equal;
146        }
147        match (self.sign, other.sign) {
148            (Sign::Pos, Sign::Neg) => Ordering::Greater,
149            (Sign::Neg, Sign::Pos) => Ordering::Less,
150            (Sign::Pos, Sign::Pos) => Self::cmp_abs(&self.limbs, &other.limbs),
151            (Sign::Neg, Sign::Neg) => Self::cmp_abs(&other.limbs, &self.limbs),
152        }
153    }
154
155    fn add_abs(a: &[Word], b: &[Word]) -> Vec<Word> {
156        let n = a.len().max(b.len());
157        let mut out = vec![0; n + 1];
158        let mut c = 0;
159        for i in 0..n {
160            let x = a.get(i).copied().unwrap_or(0);
161            let y = b.get(i).copied().unwrap_or(0);
162            c = add_carry(x, y, c, &mut out[i]);
163        }
164        out[n] = c;
165        out
166    }
167
168    fn sub_abs(a: &[Word], b: &[Word]) -> Vec<Word> {
169        debug_assert!(Self::cmp_abs(a, b) != Ordering::Less);
170        let mut out = vec![0; a.len()];
171        let mut c = 0;
172        for i in 0..a.len() {
173            let y = b.get(i).copied().unwrap_or(0);
174            c = sub_borrow(a[i], y, c, &mut out[i]);
175        }
176        debug_assert!(c == 0);
177        out
178    }
179
180    /// `self + rhs`.
181    pub fn add(&self, rhs: &Self) -> Self {
182        if self.is_zero() {
183            return rhs.clone();
184        }
185        if rhs.is_zero() {
186            return self.clone();
187        }
188        if self.sign == rhs.sign {
189            Self::from_limbs(self.sign, Self::add_abs(&self.limbs, &rhs.limbs))
190        } else {
191            match Self::cmp_abs(&self.limbs, &rhs.limbs) {
192                Ordering::Equal => Self::zero(),
193                Ordering::Greater => {
194                    Self::from_limbs(self.sign, Self::sub_abs(&self.limbs, &rhs.limbs))
195                }
196                Ordering::Less => {
197                    Self::from_limbs(rhs.sign, Self::sub_abs(&rhs.limbs, &self.limbs))
198                }
199            }
200        }
201    }
202
203    /// `self - rhs`.
204    pub fn sub(&self, rhs: &Self) -> Self {
205        self.add(&rhs.neg())
206    }
207
208    /// `-self`.
209    pub fn neg(&self) -> Self {
210        if self.is_zero() {
211            return Self::zero();
212        }
213        Self {
214            sign: self.sign.invert(),
215            limbs: self.limbs.clone(),
216        }
217    }
218
219    /// `self * rhs`.
220    pub fn mul(&self, rhs: &Self) -> Self {
221        if self.is_zero() || rhs.is_zero() {
222            return Self::zero();
223        }
224        let mut out = vec![0; self.limbs.len() + rhs.limbs.len()];
225        for (i, &d1) in self.limbs.iter().enumerate() {
226            let d1 = d1 as DoubleWord;
227            if d1 == 0 {
228                continue;
229            }
230            let mut k = 0;
231            for (j, &d2) in rhs.limbs.iter().enumerate() {
232                let m = d1 * (d2 as DoubleWord) + out[i + j] as DoubleWord + k;
233                out[i + j] = m as Word;
234                k = m >> WORD_BIT_SIZE;
235            }
236            out[i + rhs.limbs.len()] = k as Word;
237        }
238        let sign = if self.sign == rhs.sign { Sign::Pos } else { Sign::Neg };
239        Self::from_limbs(sign, out)
240    }
241
242    fn shl_one(a: &mut Vec<Word>) {
243        let mut c = 0;
244        for w in a.iter_mut() {
245            let n = (*w << 1) | c;
246            c = *w >> (WORD_BIT_SIZE - 1);
247            *w = n;
248        }
249        if c != 0 {
250            a.push(c);
251        }
252    }
253
254    fn bit(a: &[Word], i: usize) -> bool {
255        let w = i / WORD_BIT_SIZE;
256        let b = i % WORD_BIT_SIZE;
257        a.get(w).is_some_and(|v| (*v >> b) & 1 == 1)
258    }
259
260    fn set_bit(a: &mut [Word], i: usize) {
261        let w = i / WORD_BIT_SIZE;
262        let b = i % WORD_BIT_SIZE;
263        if w < a.len() {
264            a[w] |= 1 << b;
265        }
266    }
267
268    fn div_rem_abs(a: &[Word], b: &[Word]) -> (Vec<Word>, Vec<Word>) {
269        debug_assert!(!b.is_empty());
270        if Self::cmp_abs(a, b) == Ordering::Less {
271            return (Vec::new(), a.to_vec());
272        }
273        let bits = (a.len() - 1) * WORD_BIT_SIZE
274            + (WORD_BIT_SIZE - a.last().unwrap().leading_zeros() as usize); // a >= b, b nonempty
275        let mut rem: Vec<Word> = Vec::new();
276        let mut quot = vec![0; a.len()];
277        for i in (0..bits).rev() {
278            Self::shl_one(&mut rem);
279            if rem.is_empty() {
280                rem.push(0);
281            }
282            if Self::bit(a, i) {
283                rem[0] |= 1;
284            }
285            while rem.last().is_some_and(|w| *w == 0) {
286                rem.pop();
287            }
288            if Self::cmp_abs(&rem, b) != Ordering::Less {
289                rem = Self::sub_abs(&rem, b);
290                while rem.last().is_some_and(|w| *w == 0) {
291                    rem.pop();
292                }
293                Self::set_bit(&mut quot, i);
294            }
295        }
296        (quot, rem)
297    }
298
299    /// Truncated division: `(quotient, remainder)` with remainder sign matching `self`.
300    /// Zero divisor is `None`.
301    pub fn div_rem(&self, rhs: &Self) -> Option<(Self, Self)> {
302        if rhs.is_zero() {
303            return None;
304        }
305        if self.is_zero() {
306            return Some((Self::zero(), Self::zero()));
307        }
308        let (q, r) = Self::div_rem_abs(&self.limbs, &rhs.limbs);
309        let qsign = if self.sign == rhs.sign { Sign::Pos } else { Sign::Neg };
310        Some((Self::from_limbs(qsign, q), Self::from_limbs(self.sign, r)))
311    }
312
313    /// Non-negative GCD. `gcd(0, 0) = 0`.
314    pub fn gcd(&self, rhs: &Self) -> Self {
315        let mut a = Self::from_limbs(Sign::Pos, self.limbs.clone());
316        let mut b = Self::from_limbs(Sign::Pos, rhs.limbs.clone());
317        while !b.is_zero() {
318            let r = a.div_rem(&b).map(|(_, r)| r).unwrap_or_else(Self::zero);
319            a = b;
320            b = r;
321        }
322        a
323    }
324
325    /// `self.pow(exp)` by binary exponentiation. `self^0 = 1`.
326    pub fn pow(&self, mut exp: u64) -> Self {
327        if exp == 0 {
328            return Self::one();
329        }
330        let mut base = self.clone();
331        let mut acc = Self::one();
332        while exp > 0 {
333            if exp & 1 == 1 {
334                acc = acc.mul(&base);
335            }
336            exp >>= 1;
337            if exp > 0 {
338                base = base.mul(&base);
339            }
340        }
341        acc
342    }
343
344    /// True if the value is `+1`.
345    pub(crate) fn is_one(&self) -> bool {
346        self.sign == Sign::Pos && self.limbs.len() == 1 && self.limbs[0] == 1
347    }
348
349    /// Least-significant limb, or `0`.
350    pub(crate) fn low_word(&self) -> Word {
351        self.limbs.first().copied().unwrap_or(0)
352    }
353
354    /// Little-endian limbs with the given sign.
355    pub(crate) fn from_le_words(sign: Sign, words: &[Word]) -> Self {
356        Self::from_limbs(sign, words.to_vec())
357    }
358
359    /// `self << bits`.
360    pub(crate) fn shl(&self, bits: usize) -> Self {
361        if self.is_zero() || bits == 0 {
362            return self.clone();
363        }
364        let woff = bits / WORD_BIT_SIZE;
365        let boff = bits % WORD_BIT_SIZE;
366        let mut out = vec![0; self.limbs.len() + woff + 1];
367        if boff == 0 {
368            out[woff..woff + self.limbs.len()].copy_from_slice(&self.limbs);
369        } else {
370            let mut c = 0;
371            for (i, &w) in self.limbs.iter().enumerate() {
372                out[woff + i] = (w << boff) | c;
373                c = w >> (WORD_BIT_SIZE - boff);
374            }
375            out[woff + self.limbs.len()] = c;
376        }
377        Self::from_limbs(self.sign, out)
378    }
379
380    /// Convert to an `ExactNum` at `(p, rm)`.
381    pub fn to_exact_num(&self, p: usize, rm: RoundingMode) -> ExactNum {
382        if self.is_zero() {
383            return ExactNum::from_u8(0, p);
384        }
385        let work = p.max(self.bit_length()).saturating_add(WORD_BIT_SIZE);
386        let mut acc = ExactNum::from_u8(0, work);
387        for &limb in self.limbs.iter().rev() {
388            acc = acc.ldexp(WORD_BIT_SIZE as i32, work, RoundingMode::None);
389            acc = acc.add(&ExactNum::from_word(limb, work), work, RoundingMode::None);
390        }
391        if self.sign == Sign::Neg {
392            acc = acc.neg();
393        }
394        let _ = acc.set_precision(p, rm);
395        acc
396    }
397
398    /// Decimal string of `self` (sign plus digits, no exponent).
399    pub fn to_dec_string(&self) -> alloc::string::String {
400        if self.is_zero() {
401            return alloc::string::String::from("0");
402        }
403        let ten = Self::from_u64(10);
404        let mut n = if self.is_negative() { self.neg() } else { self.clone() };
405        let mut digits = alloc::vec::Vec::new();
406        while !n.is_zero() {
407            let (q, r) = n.div_rem(&ten).unwrap_or((Self::zero(), Self::zero()));
408            digits.push(b'0' + (r.low_word() as u8));
409            n = q;
410        }
411        if self.is_negative() {
412            digits.push(b'-');
413        }
414        digits.reverse();
415        alloc::string::String::from_utf8(digits)
416            .unwrap_or_else(|_| alloc::string::String::from("0"))
417    }
418
419    /// Parse a decimal integer string (`-?[0-9]+`). Empty or non-digits is `None`.
420    pub fn from_dec_string(s: &str) -> Option<Self> {
421        let s = s.trim();
422        if s.is_empty() {
423            return None;
424        }
425        let (neg, digits) = if let Some(rest) = s.strip_prefix('-') {
426            (true, rest)
427        } else {
428            (false, s.strip_prefix('+').unwrap_or(s))
429        };
430        if digits.is_empty() || !digits.bytes().all(|c| c.is_ascii_digit()) {
431            return None;
432        }
433        let ten = Self::from_u64(10);
434        let mut acc = Self::zero();
435        for b in digits.bytes() {
436            acc = acc.mul(&ten).add(&Self::from_u64((b - b'0') as u64));
437        }
438        Some(if neg { acc.neg() } else { acc })
439    }
440
441    /// Truncate a finite `ExactNum` toward zero. `None` if Inf or NaN.
442    pub fn from_exact_num(x: &ExactNum) -> Option<Self> {
443        if x.is_nan() || x.is_inf() {
444            return None;
445        }
446        let v = x.int();
447        if v.is_zero() {
448            return Some(Self::zero());
449        }
450        let p = v.precision().unwrap_or(DEFAULT_P).max(WORD_BIT_SIZE + 8);
451        let two_w = ExactNum::from_u8(1, p).ldexp(WORD_BIT_SIZE as i32, p, RoundingMode::None);
452        let mut cur = v.abs();
453        let mut limbs = Vec::new();
454        while !cur.is_zero() {
455            let r = cur.rem(&two_w);
456            limbs.push(exact_word_lt_base(&r));
457            cur = cur.div(&two_w, p, RoundingMode::ToZero).int();
458        }
459        let sign = if v.is_negative() { Sign::Neg } else { Sign::Pos };
460        Some(Self::from_limbs(sign, limbs))
461    }
462}
463
464fn exact_word_lt_base(x: &ExactNum) -> Word {
465    if x.is_zero() {
466        return 0;
467    }
468    let Some((m, _n, _s, e, _)) = x.as_raw_parts() else {
469        return 0;
470    };
471    let pbuf = m.len() * WORD_BIT_SIZE;
472    let shift = e as isize - pbuf as isize;
473    shift_le_low_word(m, shift)
474}
475
476fn shift_le_low_word(m: &[Word], shift: isize) -> Word {
477    if m.is_empty() {
478        return 0;
479    }
480    if shift >= 0 {
481        let s = shift as usize;
482        let woff = s / WORD_BIT_SIZE;
483        let boff = s % WORD_BIT_SIZE;
484        let lo = m.get(woff).copied().unwrap_or(0);
485        if boff == 0 {
486            lo
487        } else {
488            let hi = m.get(woff + 1).copied().unwrap_or(0);
489            (lo << boff) | (hi >> (WORD_BIT_SIZE - boff))
490        }
491    } else {
492        let r = (-shift) as usize;
493        let woff = r / WORD_BIT_SIZE;
494        let boff = r % WORD_BIT_SIZE;
495        let lo = m.get(woff).copied().unwrap_or(0);
496        if boff == 0 {
497            lo
498        } else {
499            let hi = m.get(woff + 1).copied().unwrap_or(0);
500            (lo >> boff) | (hi << (WORD_BIT_SIZE - boff))
501        }
502    }
503}
504
505impl PartialEq for ExactInt {
506    fn eq(&self, other: &Self) -> bool {
507        self.cmp(other) == Ordering::Equal
508    }
509}
510
511#[cfg(test)]
512mod tests {
513    use super::*;
514
515    #[test]
516    fn exact_int_fact20_gcd_pow2_divrem() {
517        let mut fact = ExactInt::one();
518        for k in 2..=20 {
519            fact = fact.mul(&ExactInt::from_i64(k));
520        }
521        assert_eq!(fact, ExactInt::from_i64(2_432_902_008_176_640_000));
522
523        let g = ExactInt::from_i64(48).gcd(&ExactInt::from_i64(18));
524        assert_eq!(g, ExactInt::from_i64(6));
525
526        let p2 = ExactInt::from_i64(2).pow(100);
527        assert_eq!(p2, ExactInt::from_u128(1u128 << 100));
528        assert_eq!(
529            p2,
530            ExactInt::from_u128(1_267_650_600_228_229_401_496_703_205_376)
531        );
532        assert_eq!(p2.bit_length(), 101);
533
534        let (q, r) = ExactInt::from_i64(17)
535            .div_rem(&ExactInt::from_i64(5))
536            .unwrap();
537        assert_eq!(q, ExactInt::from_i64(3));
538        assert_eq!(r, ExactInt::from_i64(2));
539
540        let n = ExactInt::from_i64(-3);
541        let f = n.to_exact_num(64, RoundingMode::ToEven);
542        assert_eq!(ExactInt::from_exact_num(&f), Some(n));
543        assert!(ExactInt::from_exact_num(&crate::NAN).is_none());
544        assert!(ExactInt::from_i64(1).div_rem(&ExactInt::zero()).is_none());
545    }
546}
zenith_float_num/integer.rs

zenith_float_num/
integer.rs
