probl_number/
lib.rs

1//! One integer type with inline small values and shared, canonical large values.
2//! The hard size ceiling bounds parsing and individual allocations even before
3//! the runtime has a work budget. Hosts can impose a smaller runtime ceiling.
4
5pub mod primes;
6
7use num_bigint::BigInt;
8use num_rational::BigRational;
9use num_traits::{FromPrimitive, Signed, ToPrimitive, Zero};
10use rustc_hash::FxHasher;
11use std::borrow::Cow;
12use std::cmp::Ordering;
13use std::fmt;
14use std::hash::{Hash, Hasher};
15use std::str::FromStr;
16use std::sync::Arc;
17
18pub const MAX_INTEGER_BITS: u64 = 65_536;
19// ceil(MAX_INTEGER_BITS * log10(2)); check bits after parsing the last digit.
20pub const MAX_INTEGER_DIGITS: usize = 19_729;
21
22#[derive(Clone)]
23pub struct Integer(Repr);
24
25#[derive(Clone)]
26enum Repr {
27    Small(i64),
28    Large(Arc<Large>),
29}
30
31struct Large {
32    value: BigInt,
33    hash: u64,
34}
35
36#[derive(Clone, Copy, Debug, PartialEq, Eq)]
37pub enum IntError {
38    Invalid,
39    TooLarge,
40    DivisionByZero,
41}
42
43impl fmt::Display for IntError {
44    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
45        match self {
46            Self::Invalid => f.write_str("invalid integer"),
47            Self::TooLarge => write!(f, "integer size exceeds the limit of {MAX_INTEGER_BITS} bits"),
48            Self::DivisionByZero => f.write_str("division by zero"),
49        }
50    }
51}
52
53impl Integer {
54    pub const ZERO: Self = Self(Repr::Small(0));
55    pub const ONE: Self = Self(Repr::Small(1));
56
57    /// Parse unsigned binary or hexadecimal digits (no prefix or separators).
58    /// Check the significant bit count before allocating a bigint. Decimal
59    /// parsing remains separate so data files keep their decimal-only contract.
60    pub fn from_radix_digits(digits: &str, radix: u32) -> Result<Self, IntError> {
61        let valid = match radix {
62            2 => digits.bytes().all(|b| matches!(b, b'0' | b'1')),
63            16 => digits.bytes().all(|b| b.is_ascii_hexdigit()),
64            _ => false,
65        };
66        if digits.is_empty() || !valid {
67            return Err(IntError::Invalid);
68        }
69        let digits = digits.trim_start_matches('0');
70        if digits.is_empty() {
71            return Ok(Self::ZERO);
72        }
73        let first = (digits.as_bytes()[0] as char).to_digit(radix).expect("validated digit");
74        let bits = (digits.len() as u64 - 1)
75            .saturating_mul(u64::from(radix.trailing_zeros()))
76            .saturating_add(u64::from(32 - first.leading_zeros()));
77        if bits > MAX_INTEGER_BITS {
78            return Err(IntError::TooLarge);
79        }
80        if let Ok(n) = i64::from_str_radix(digits, radix) {
81            return Ok(n.into());
82        }
83        Self::from_big(BigInt::parse_bytes(digits.as_bytes(), radix).ok_or(IntError::Invalid)?)
84    }
85
86    pub fn from_big(value: BigInt) -> Result<Self, IntError> {
87        if let Some(n) = value.to_i64() {
88            return Ok(n.into());
89        }
90        if value.bits() > MAX_INTEGER_BITS {
91            return Err(IntError::TooLarge);
92        }
93        let mut h = FxHasher::default();
94        value.hash(&mut h);
95        Ok(Self(Repr::Large(Arc::new(Large {
96            value,
97            hash: h.finish(),
98        }))))
99    }
100
101    pub fn big(&self) -> Cow<'_, BigInt> {
102        match &self.0 {
103            Repr::Small(n) => Cow::Owned(BigInt::from(*n)),
104            Repr::Large(n) => Cow::Borrowed(&n.value),
105        }
106    }
107
108    pub fn to_i64(&self) -> Option<i64> {
109        match self.0 {
110            Repr::Small(n) => Some(n),
111            _ => None,
112        }
113    }
114    pub fn to_u64(&self) -> Option<u64> {
115        match &self.0 {
116            Repr::Small(n) => u64::try_from(*n).ok(),
117            Repr::Large(n) => n.value.to_u64(),
118        }
119    }
120    pub fn to_u128(&self) -> Option<u128> {
121        match &self.0 {
122            Repr::Small(n) => u128::try_from(*n).ok(),
123            Repr::Large(n) => n.value.to_u128(),
124        }
125    }
126    pub fn to_f64(&self) -> Option<f64> {
127        match &self.0 {
128            Repr::Small(n) => Some(*n as f64),
129            Repr::Large(n) => n.value.to_f64().filter(|x| x.is_finite()),
130        }
131    }
132    pub fn from_f64(x: f64) -> Option<Self> {
133        if x >= i64::MIN as f64 && x < -(i64::MIN as f64) {
134            Some((x as i64).into())
135        } else {
136            BigInt::from_f64(x).and_then(|n| Self::from_big(n).ok())
137        }
138    }
139    pub fn bits(&self) -> u64 {
140        match &self.0 {
141            Repr::Small(n) => 64 - u64::from(n.unsigned_abs().leading_zeros()),
142            Repr::Large(n) => n.value.bits(),
143        }
144    }
145    /// Count set bits in the magnitude, ignoring the sign.
146    pub fn bit_count(&self) -> u64 {
147        match &self.0 {
148            Repr::Small(n) => u64::from(n.unsigned_abs().count_ones()),
149            Repr::Large(n) => n.value.magnitude().count_ones(),
150        }
151    }
152    /// Signed bit operations use infinite two's-complement sign extension.
153    pub fn bit_and(&self, rhs: &Self) -> Result<Self, IntError> {
154        if let (Some(a), Some(b)) = (self.to_i64(), rhs.to_i64()) {
155            return Ok((a & b).into());
156        }
157        Self::from_big(self.big().as_ref() & rhs.big().as_ref())
158    }
159    pub fn bit_or(&self, rhs: &Self) -> Result<Self, IntError> {
160        if let (Some(a), Some(b)) = (self.to_i64(), rhs.to_i64()) {
161            return Ok((a | b).into());
162        }
163        Self::from_big(self.big().as_ref() | rhs.big().as_ref())
164    }
165    pub fn bit_xor(&self, rhs: &Self) -> Result<Self, IntError> {
166        if let (Some(a), Some(b)) = (self.to_i64(), rhs.to_i64()) {
167            return Ok((a ^ b).into());
168        }
169        Self::from_big(self.big().as_ref() ^ rhs.big().as_ref())
170    }
171    pub fn bit_not(&self) -> Result<Self, IntError> {
172        if let Some(n) = self.to_i64() {
173            return Ok((!n).into());
174        }
175        Self::from_big(!self.big().as_ref())
176    }
177    pub fn is_negative(&self) -> bool {
178        match &self.0 {
179            Repr::Small(n) => *n < 0,
180            Repr::Large(n) => n.value.is_negative(),
181        }
182    }
183    pub fn is_zero(&self) -> bool {
184        matches!(self.0, Repr::Small(0))
185    }
186    pub fn is_odd(&self) -> bool {
187        match &self.0 {
188            Repr::Small(n) => n & 1 != 0,
189            Repr::Large(n) => n.value.bit(0),
190        }
191    }
192    pub fn magnitude_bit(&self, i: u64) -> bool {
193        match &self.0 {
194            Repr::Small(n) => i < 64 && (n.unsigned_abs() >> i) & 1 != 0,
195            Repr::Large(n) => n.value.magnitude().bit(i),
196        }
197    }
198    pub fn negated(&self) -> Self {
199        if let Some(n) = self.to_i64().and_then(i64::checked_neg) {
200            return n.into();
201        }
202        Self::from_big(-self.big().as_ref()).expect("negation preserves magnitude")
203    }
204    pub fn abs(&self) -> Self {
205        if self.is_negative() {
206            self.negated()
207        } else {
208            self.clone()
209        }
210    }
211
212    pub fn add(&self, rhs: &Self) -> Result<Self, IntError> {
213        if let (Some(a), Some(b)) = (self.to_i64(), rhs.to_i64()) {
214            if let Some(n) = a.checked_add(b) {
215                return Ok(n.into());
216            }
217        }
218        Self::from_big(self.big().as_ref() + rhs.big().as_ref())
219    }
220    pub fn sub(&self, rhs: &Self) -> Result<Self, IntError> {
221        if let (Some(a), Some(b)) = (self.to_i64(), rhs.to_i64()) {
222            if let Some(n) = a.checked_sub(b) {
223                return Ok(n.into());
224            }
225        }
226        Self::from_big(self.big().as_ref() - rhs.big().as_ref())
227    }
228    pub fn mul(&self, rhs: &Self) -> Result<Self, IntError> {
229        if let (Some(a), Some(b)) = (self.to_i64(), rhs.to_i64()) {
230            if let Some(n) = a.checked_mul(b) {
231                return Ok(n.into());
232            }
233        }
234        if !self.is_zero() && !rhs.is_zero() && self.bits() + rhs.bits() - 1 > MAX_INTEGER_BITS {
235            return Err(IntError::TooLarge);
236        }
237        Self::from_big(self.big().as_ref() * rhs.big().as_ref())
238    }
239    pub fn div_mod(&self, rhs: &Self) -> Result<(Self, Self), IntError> {
240        if rhs.is_zero() {
241            return Err(IntError::DivisionByZero);
242        }
243        if let (Some(a), Some(b)) = (self.to_i64(), rhs.to_i64()) {
244            if let Some(mut q) = a.checked_div(b) {
245                let mut r = a % b;
246                if r != 0 && (r < 0) != (b < 0) {
247                    q -= 1;
248                    r += b;
249                }
250                return Ok((q.into(), r.into()));
251            }
252        }
253        let (a, b) = (self.big(), rhs.big());
254        let mut q = a.as_ref() / b.as_ref();
255        let mut r = a.as_ref() % b.as_ref();
256        if !r.is_zero() && r.is_negative() != b.is_negative() {
257            q -= 1;
258            r += b.as_ref();
259        }
260        Ok((Self::from_big(q)?, Self::from_big(r)?))
261    }
262    pub fn pow(&self, exponent: u32) -> Result<Self, IntError> {
263        if let Some(n) = self.to_i64().and_then(|n| n.checked_pow(exponent)) {
264            return Ok(n.into());
265        }
266        if self.bits().saturating_sub(1).saturating_mul(u64::from(exponent)) >= MAX_INTEGER_BITS {
267            return Err(IntError::TooLarge);
268        }
269        Self::from_big(self.big().pow(exponent))
270    }
271    /// The floor of the square root, for a nonnegative integer.
272    pub fn isqrt(&self) -> Option<Self> {
273        match &self.0 {
274            Repr::Small(n) => u64::try_from(*n).ok().map(|n| n.isqrt().into()),
275            Repr::Large(n) if n.value.is_negative() => None,
276            Repr::Large(n) => Some(Self::from_big(n.value.sqrt()).expect("a root is no larger than its square")),
277        }
278    }
279    /// `self` to the power `exponent`, modulo `modulus`, as `mod` gives it:
280    /// on the modulus's side of 0. A negative exponent takes powers of the
281    /// inverse, and gives `None` when there's none.
282    pub fn mod_pow(&self, exponent: &Self, modulus: &Self) -> Result<Option<Self>, IntError> {
283        let m = modulus.abs();
284        let mut base = self.div_mod(&m)?.1;
285        if exponent.is_negative() {
286            match base.mod_inverse(&m)? {
287                Some(inverse) => base = inverse,
288                None => return Ok(None),
289            }
290        }
291        let e = exponent.abs();
292        let power = match (base.to_u64(), e.to_u64(), m.to_u64()) {
293            (Some(b), Some(e), Some(m)) => primes::pow_mod(b, e, m).into(),
294            _ => {
295                let power = base.big().magnitude().modpow(e.big().magnitude(), m.big().magnitude());
296                Self::from_big(power.into())?
297            }
298        };
299        Ok(Some(power.remainder_for(modulus)?))
300    }
301    /// The inverse of `self` modulo `modulus`, as `mod` gives it, if they're
302    /// coprime.
303    pub fn mod_inverse(&self, modulus: &Self) -> Result<Option<Self>, IntError> {
304        let m = modulus.abs();
305        let a = self.div_mod(&m)?.1;
306        match a.big().magnitude().modinv(m.big().magnitude()) {
307            Some(inverse) => Ok(Some(Self::from_big(inverse.into())?.remainder_for(modulus)?)),
308            None => Ok(None),
309        }
310    }
311    /// Move a remainder from 0 up to `|m|` to `m`'s side of 0, as `div_mod`
312    /// places it.
313    fn remainder_for(self, m: &Self) -> Result<Self, IntError> {
314        if m.is_negative() && !self.is_zero() {
315            self.add(m)
316        } else {
317            Ok(self)
318        }
319    }
320    /// Convert the quotient jointly: individually converting huge operands
321    /// would turn a finite ratio into infinity / infinity.
322    pub fn ratio(&self, denominator: &Self) -> Option<f64> {
323        if denominator.is_zero() {
324            return None;
325        }
326        if let (Some(a), Some(b)) = (self.to_i64(), denominator.to_i64()) {
327            if a.unsigned_abs() <= 1 << 53 && b.unsigned_abs() <= 1 << 53 {
328                return Some(a as f64 / b as f64);
329            }
330        }
331        BigRational::new_raw(self.big().into_owned(), denominator.big().into_owned())
332            .to_f64()
333            .filter(|x| x.is_finite())
334    }
335
336    /// ceil(n*p) for a nonnegative n and a finite probability. The float is
337    /// interpreted exactly, so rank selection works beyond float precision.
338    /// The temporary product uses at most 53 extra bits above n's size.
339    pub fn probability_rank(&self, p: f64) -> Result<Self, IntError> {
340        if self.is_negative() || !p.is_finite() || !(0.0..=1.0).contains(&p) {
341            return Err(IntError::Invalid);
342        }
343        let fraction = BigRational::from_float(p).ok_or(IntError::Invalid)?;
344        let product = self.big().as_ref() * fraction.numer();
345        let denominator = fraction.denom();
346        let q = &product / denominator;
347        Self::from_big(if (&product % denominator).is_zero() { q } else { q + 1 })
348    }
349
350    /// Round an integer to a power of ten, halfway away from zero. The
351    /// temporary scale is bounded to at most a few bits above the value ceiling.
352    pub fn round_decimal(&self, places: u32) -> Result<Self, IntError> {
353        if places as usize > MAX_INTEGER_DIGITS || u64::from(places) > self.bits() * 30103 / 100000 + 1 {
354            return Ok(Self::ZERO);
355        }
356        let scale = BigInt::from(10).pow(places);
357        let magnitude = self.big().abs();
358        let rounded = (magnitude + &scale / 2u32) / &scale * &scale;
359        Self::from_big(if self.is_negative() { -rounded } else { rounded })
360    }
361    /// Compare to the exact value represented by a float, without converting
362    /// the integer to a rounded float. Finite floats need at most 1024 bits.
363    pub fn cmp_f64(&self, x: f64) -> Option<Ordering> {
364        if x.is_nan() {
365            return None;
366        }
367        if x == f64::INFINITY {
368            return Some(Ordering::Less);
369        }
370        if x == f64::NEG_INFINITY {
371            return Some(Ordering::Greater);
372        }
373        let truncated = Self::from_f64(x).expect("finite float fits the integer ceiling");
374        let cmp = self.cmp(&truncated);
375        Some(if cmp.is_eq() {
376            0.0f64.partial_cmp(&x.fract()).unwrap()
377        } else {
378            cmp
379        })
380    }
381}
382
383impl FromStr for Integer {
384    type Err = IntError;
385    fn from_str(s: &str) -> Result<Self, Self::Err> {
386        if let Ok(n) = s.parse::<i64>() {
387            return Ok(n.into());
388        }
389        let digits = s.strip_prefix(['+', '-']).unwrap_or(s);
390        if digits.is_empty() || !digits.bytes().all(|c| c.is_ascii_digit()) {
391            return Err(IntError::Invalid);
392        }
393        let digits = digits.trim_start_matches('0');
394        if digits.len() > MAX_INTEGER_DIGITS {
395            return Err(IntError::TooLarge);
396        }
397        if digits.is_empty() {
398            return Ok(Self::ZERO);
399        }
400        let n = BigInt::from_str(digits).map_err(|_| IntError::Invalid)?;
401        Self::from_big(if s.starts_with('-') { -n } else { n })
402    }
403}
404impl From<i64> for Integer {
405    fn from(n: i64) -> Self {
406        Self(Repr::Small(n))
407    }
408}
409macro_rules! from_integer {
410    ($($t:ty),*) => { $(impl From<$t> for Integer { fn from(n: $t) -> Self { match i64::try_from(n) { Ok(n) => Self::from(n), Err(_) => Self::from_big(BigInt::from(n)).expect("machine integer fits") } } })* };
411}
412impl From<i32> for Integer {
413    fn from(n: i32) -> Self {
414        Self::from(i64::from(n))
415    }
416}
417impl From<u32> for Integer {
418    fn from(n: u32) -> Self {
419        Self::from(i64::from(n))
420    }
421}
422from_integer!(u64, usize, i128, u128);
423impl PartialEq for Integer {
424    #[inline]
425    fn eq(&self, rhs: &Self) -> bool {
426        match (&self.0, &rhs.0) {
427            (Repr::Small(a), Repr::Small(b)) => a == b,
428            (Repr::Large(a), Repr::Large(b)) => Arc::ptr_eq(a, b) || (a.hash == b.hash && a.value == b.value),
429            // A large integer is outside the range of a small one (`from_big`).
430            _ => false,
431        }
432    }
433}
434impl Eq for Integer {}
435impl PartialOrd for Integer {
436    fn partial_cmp(&self, rhs: &Self) -> Option<Ordering> {
437        Some(self.cmp(rhs))
438    }
439}
440impl Ord for Integer {
441    fn cmp(&self, rhs: &Self) -> Ordering {
442        match (&self.0, &rhs.0) {
443            (Repr::Small(a), Repr::Small(b)) => a.cmp(b),
444            (Repr::Large(a), Repr::Large(b)) => a.value.cmp(&b.value),
445            (Repr::Large(a), Repr::Small(_)) => {
446                if a.value.is_negative() {
447                    Ordering::Less
448                } else {
449                    Ordering::Greater
450                }
451            }
452            (Repr::Small(_), Repr::Large(b)) => {
453                if b.value.is_negative() {
454                    Ordering::Greater
455                } else {
456                    Ordering::Less
457                }
458            }
459        }
460    }
461}
462impl PartialEq<i64> for Integer {
463    fn eq(&self, rhs: &i64) -> bool {
464        self.to_i64() == Some(*rhs)
465    }
466}
467impl PartialOrd<i64> for Integer {
468    fn partial_cmp(&self, rhs: &i64) -> Option<Ordering> {
469        Some(self.cmp(&Self::from(*rhs)))
470    }
471}
472impl Hash for Integer {
473    fn hash<H: Hasher>(&self, h: &mut H) {
474        match &self.0 {
475            Repr::Small(n) => {
476                0u8.hash(h);
477                n.hash(h);
478            }
479            Repr::Large(n) => {
480                1u8.hash(h);
481                n.hash.hash(h);
482            }
483        }
484    }
485}
486impl fmt::Display for Integer {
487    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
488        match &self.0 {
489            Repr::Small(n) => n.fmt(f),
490            Repr::Large(n) => n.value.fmt(f),
491        }
492    }
493}
494impl fmt::Debug for Integer {
495    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
496        fmt::Display::fmt(self, f)
497    }
498}
499
500#[cfg(test)]
501mod tests {
502    use super::*;
503
504    #[test]
505    fn integer_square_roots_are_exact_floors() {
506        for n in 0..10_000u64 {
507            let root = Integer::from(n).isqrt().unwrap().to_u64().unwrap();
508            assert!(root * root <= n && (root + 1) * (root + 1) > n, "{n}");
509        }
510        for n in [u64::MAX, u64::MAX - 1, (1 << 32) * (1 << 31)] {
511            let root = u128::from(Integer::from(n).isqrt().unwrap().to_u64().unwrap());
512            assert!(
513                root * root <= u128::from(n) && (root + 1) * (root + 1) > u128::from(n),
514                "{n}"
515            );
516        }
517        let big = Integer::from(10).pow(200).unwrap();
518        let square = big.mul(&big).unwrap();
519        assert_eq!(square.isqrt(), Some(big.clone()));
520        assert_eq!(
521            square.sub(&Integer::ONE).unwrap().isqrt(),
522            Some(big.sub(&Integer::ONE).unwrap())
523        );
524        assert_eq!(Integer::from(-1).isqrt(), None);
525        assert_eq!(square.negated().isqrt(), None);
526    }
527
528    #[test]
529    fn modular_powers_and_inverses_agree_with_mod() {
530        let int = |s: &str| s.parse::<Integer>().unwrap();
531        for b in -12..=12i64 {
532            for m in (-10..=10i64).filter(|&m| m != 0) {
533                let m = Integer::from(m);
534                for e in 0..8u32 {
535                    let expected = Integer::from(b).pow(e).unwrap().div_mod(&m).unwrap().1;
536                    let found = Integer::from(b).mod_pow(&e.into(), &m).unwrap();
537                    assert_eq!(found, Some(expected), "{b}^{e} mod {m}");
538                }
539                // An inverse, multiplied back, leaves what 1 leaves.
540                let one = Integer::ONE.div_mod(&m).unwrap().1;
541                let coprime = m.abs() == 1 || (2..=12).all(|d| b % d != 0 || m.div_mod(&d.into()).unwrap().1 != 0);
542                match Integer::from(b).mod_inverse(&m).unwrap() {
543                    Some(x) => {
544                        assert!(coprime, "{b} mod {m}");
545                        assert_eq!(x.mul(&b.into()).unwrap().div_mod(&m).unwrap().1, one, "{b} mod {m}");
546                        assert_eq!(x.div_mod(&m).unwrap().1, x, "{b} mod {m}");
547                        let cube = Integer::from(b).mod_pow(&(-3).into(), &m).unwrap().unwrap();
548                        assert_eq!(cube, x.pow(3).unwrap().div_mod(&m).unwrap().1, "{b} mod {m}");
549                    }
550                    None => {
551                        assert!(!coprime, "{b} mod {m}");
552                        assert_eq!(Integer::from(b).mod_pow(&(-1).into(), &m), Ok(None));
553                    }
554                }
555            }
556        }
557        // Python's three-argument pow, which places remainders as `mod` does.
558        let m127 = int("170141183460469231731687303715884105727");
559        let twenty = Integer::from(10).pow(20).unwrap();
560        for (b, e, m, expected) in [
561            (int("3"), twenty.clone(), int("7"), "4"),
562            (
563                int("123456789"),
564                Integer::from(10).pow(30).unwrap(),
565                m127.clone(),
566                "122595712604757454617202977651078910759",
567            ),
568            (
569                int("-987654321987654321987654321"),
570                int("1267650600228229401496703205383"),
571                int("-1000000000000000000000000000057"),
572                "-293969698994636477086079925553",
573            ),
574            (int("2"), m127.sub(&Integer::ONE).unwrap(), m127.clone(), "1"),
575            (
576                int("10000000000000000000000003"),
577                int("-1"),
578                int("618970019642690137449562111"),
579                "71994936398798874148776713",
580            ),
581            (int("2"), int("-1"), int("-7"), "-3"),
582            (int("3"), int("-2"), int("10"), "9"),
583            (int("-3"), int("5"), int("-7"), "-5"),
584            (int("5"), int("0"), int("1"), "0"),
585            (int("5"), twenty, int("-1"), "0"),
586        ] {
587            assert_eq!(b.mod_pow(&e, &m), Ok(Some(int(expected))), "{b}^{e} mod {m}");
588        }
589        assert_eq!(int("6").mod_inverse(&int("9")), Ok(None));
590        assert_eq!(int("0").mod_inverse(&int("1")), Ok(Some(Integer::ZERO)));
591        assert_eq!(
592            int("2").mod_pow(&int("3"), &Integer::ZERO),
593            Err(IntError::DivisionByZero)
594        );
595        assert_eq!(int("2").mod_inverse(&Integer::ZERO), Err(IntError::DivisionByZero));
596    }
597
598    #[test]
599    fn radix_parsing_is_exact_and_checks_limits_before_allocation() {
600        for bits in [0, 1, 31, 32, 53, 63, 64, 65, 127, 1024, 65535] {
601            let n: BigInt = (BigInt::from(1) << bits) - 1u32;
602            let expected = Integer::from_big(n.clone()).unwrap();
603            for radix in [2, 16] {
604                let digits = n.to_str_radix(radix);
605                assert_eq!(Integer::from_radix_digits(&digits, radix).unwrap(), expected);
606                assert_eq!(
607                    Integer::from_radix_digits(&format!("000{digits}"), radix).unwrap(),
608                    expected
609                );
610            }
611        }
612        for (radix, digits) in [(2, "1".repeat(65536)), (16, "f".repeat(16384))] {
613            assert_eq!(
614                Integer::from_radix_digits(&digits, radix).unwrap().bits(),
615                MAX_INTEGER_BITS
616            );
617            assert_eq!(
618                Integer::from_radix_digits(&format!("1{digits}"), radix),
619                Err(IntError::TooLarge)
620            );
621        }
622        for radix in [2, 16] {
623            assert_eq!(
624                Integer::from_radix_digits(&"0".repeat(100_000), radix).unwrap(),
625                Integer::ZERO
626            );
627            for digits in ["", "_1", "1_", "-1", "+1", "1g"] {
628                assert_eq!(Integer::from_radix_digits(digits, radix), Err(IntError::Invalid));
629            }
630        }
631        assert_eq!(Integer::from_radix_digits("1", 0), Err(IntError::Invalid));
632        assert!("0xff".parse::<Integer>().is_err()); // data parsing stays decimal
633    }
634
635    #[test]
636    fn bit_operations_match_signed_machine_integers_across_storage_boundaries() {
637        let values = [
638            i128::MIN,
639            i64::MIN as i128 - 1,
640            i64::MIN as i128,
641            -101,
642            -1,
643            0,
644            1,
645            101,
646            i64::MAX as i128,
647            i64::MAX as i128 + 1,
648            i128::MAX,
649        ];
650        for a in values {
651            let x = Integer::from(a);
652            assert_eq!(x.bit_not().unwrap(), Integer::from(!a));
653            assert_eq!(x.bit_count(), u64::from(a.unsigned_abs().count_ones()));
654            for b in values {
655                let y = Integer::from(b);
656                assert_eq!(x.bit_and(&y).unwrap(), Integer::from(a & b));
657                assert_eq!(x.bit_or(&y).unwrap(), Integer::from(a | b));
658                assert_eq!(x.bit_xor(&y).unwrap(), Integer::from(a ^ b));
659            }
660            // Results that fit in i64 must regain the inline representation.
661            assert_eq!(x.bit_xor(&x).unwrap().to_i64(), Some(0));
662            assert_eq!(x.bit_or(&(-1).into()).unwrap().to_i64(), Some(-1));
663        }
664    }
665
666    #[test]
667    fn bit_operations_obey_the_magnitude_ceiling() {
668        let max = Integer::from_radix_digits(&"f".repeat(16384), 16).unwrap();
669        assert_eq!(max.bit_count(), MAX_INTEGER_BITS);
670        assert_eq!(max.negated().bit_count(), MAX_INTEGER_BITS);
671        assert_eq!(max.bit_not(), Err(IntError::TooLarge));
672        assert_eq!(max.bit_xor(&(-1).into()), Err(IntError::TooLarge));
673        assert_eq!(max.bit_and(&(-1).into()).unwrap(), max);
674        assert_eq!(max.bit_or(&(-1).into()).unwrap().to_i64(), Some(-1));
675        let below = max.sub(&Integer::ONE).unwrap();
676        assert_eq!(max.negated().bit_not().unwrap(), below);
677        assert_eq!(below.bit_not().unwrap(), max.negated());
678        // AND can also require one more magnitude bit for negative operands.
679        assert_eq!(max.negated().bit_and(&(-2).into()), Err(IntError::TooLarge));
680    }
681
682    #[test]
683    fn signed_arithmetic_matches_wider_machine_integers() {
684        let values = [
685            i64::MIN as i128 - 1,
686            i64::MIN as i128,
687            -101,
688            -1,
689            0,
690            1,
691            101,
692            i64::MAX as i128,
693            i64::MAX as i128 + 1,
694        ];
695        for a in values {
696            for b in values {
697                let (x, y) = (Integer::from(a), Integer::from(b));
698                assert_eq!(x.add(&y).unwrap().to_string(), (a + b).to_string());
699                assert_eq!(x.sub(&y).unwrap().to_string(), (a - b).to_string());
700                assert_eq!(x.mul(&y).unwrap().to_string(), (a * b).to_string());
701                if b != 0 {
702                    let (mut q, mut r) = (a / b, a % b);
703                    if r != 0 && (r < 0) != (b < 0) {
704                        q -= 1;
705                        r += b;
706                    }
707                    let actual = x.div_mod(&y).unwrap();
708                    assert_eq!(actual, (q.into(), r.into()));
709                    assert_eq!(actual.0.mul(&y).unwrap().add(&actual.1).unwrap(), x);
710                }
711            }
712        }
713    }
714
715    #[test]
716    fn comparisons_agree_with_exact_rationals() {
717        let integers = [
718            "-10000000000000000000000000000000001",
719            "-9223372036854775809",
720            "-9007199254740993",
721            "-1",
722            "0",
723            "1",
724            "9007199254740993",
725            "9223372036854775807",
726            "10000000000000000000000000000000001",
727        ];
728        let mut seed = 123456789u64;
729        for _ in 0..2000 {
730            seed ^= seed << 13;
731            seed ^= seed >> 7;
732            seed ^= seed << 17;
733            let f = f64::from_bits(seed);
734            if !f.is_finite() {
735                continue;
736            }
737            let rational = BigRational::from_float(f).unwrap();
738            for text in integers {
739                let n: Integer = text.parse().unwrap();
740                assert_eq!(
741                    n.cmp_f64(f),
742                    Some(BigRational::from_integer(n.big().into_owned()).cmp(&rational)),
743                    "{n}, {f}"
744                );
745            }
746        }
747    }
748
749    #[test]
750    fn parsing_and_operations_enforce_the_bit_ceiling() {
751        let max = Integer::from(2).pow(65535).unwrap();
752        assert_eq!(max.bits(), MAX_INTEGER_BITS);
753        assert_eq!(max.to_string().parse::<Integer>().unwrap(), max);
754        assert_eq!(max.mul(&2.into()), Err(IntError::TooLarge));
755        assert_eq!(Integer::from(2).pow(65536), Err(IntError::TooLarge));
756        assert_eq!(
757            "9".repeat(MAX_INTEGER_DIGITS + 1).parse::<Integer>(),
758            Err(IntError::TooLarge)
759        );
760        assert_eq!("0".repeat(100_000).parse::<Integer>().unwrap(), Integer::ZERO);
761        assert_eq!(
762            format!("-{}12", "0".repeat(100_000)).parse::<Integer>().unwrap(),
763            Integer::from(-12)
764        );
765        assert_eq!("+".parse::<Integer>(), Err(IntError::Invalid));
766    }
767}
probl_number/lib.rs

probl_number/
lib.rs
