num_bigint/
biguint.rs

1#[allow(deprecated, unused_imports)]
2use std::ascii::AsciiExt;
3use std::borrow::Cow;
4use std::cmp;
5use std::cmp::Ordering::{self, Equal, Greater, Less};
6use std::default::Default;
7use std::fmt;
8use std::iter::{Product, Sum};
9use std::mem;
10use std::ops::{
11    Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Div, DivAssign,
12    Mul, MulAssign, Neg, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign, Sub, SubAssign,
13};
14use std::str::{self, FromStr};
15use std::{f32, f64};
16use std::{u64, u8};
17
18#[cfg(feature = "serde")]
19use serde;
20
21use integer::{Integer, Roots};
22use traits::{
23    CheckedAdd, CheckedDiv, CheckedMul, CheckedSub, Float, FromPrimitive, Num, One, Pow,
24    ToPrimitive, Unsigned, Zero,
25};
26
27use big_digit::{self, BigDigit};
28
29#[path = "algorithms.rs"]
30mod algorithms;
31#[path = "monty.rs"]
32mod monty;
33
34use self::algorithms::{__add2, __sub2rev, add2, sub2, sub2rev};
35use self::algorithms::{biguint_shl, biguint_shr};
36use self::algorithms::{cmp_slice, fls, ilog2};
37use self::algorithms::{div_rem, div_rem_digit, div_rem_ref, rem_digit};
38use self::algorithms::{mac_with_carry, mul3, scalar_mul};
39use self::monty::monty_modpow;
40
41use UsizePromotion;
42
43use ParseBigIntError;
44
45#[cfg(feature = "quickcheck")]
46use quickcheck::{Arbitrary, Gen};
47
48/// A big unsigned integer type.
49#[derive(Clone, Debug, Hash)]
50pub struct BigUint {
51    data: Vec<BigDigit>,
52}
53
54#[cfg(feature = "quickcheck")]
55impl Arbitrary for BigUint {
56    fn arbitrary<G: Gen>(g: &mut G) -> Self {
57        // Use arbitrary from Vec
58        Self::new(Vec::<u32>::arbitrary(g))
59    }
60
61    #[allow(bare_trait_objects)] // `dyn` needs Rust 1.27 to parse, even when cfg-disabled
62    fn shrink(&self) -> Box<Iterator<Item = Self>> {
63        // Use shrinker from Vec
64        Box::new(self.data.shrink().map(BigUint::new))
65    }
66}
67
68impl PartialEq for BigUint {
69    #[inline]
70    fn eq(&self, other: &BigUint) -> bool {
71        match self.cmp(other) {
72            Equal => true,
73            _ => false,
74        }
75    }
76}
77impl Eq for BigUint {}
78
79impl PartialOrd for BigUint {
80    #[inline]
81    fn partial_cmp(&self, other: &BigUint) -> Option<Ordering> {
82        Some(self.cmp(other))
83    }
84}
85
86impl Ord for BigUint {
87    #[inline]
88    fn cmp(&self, other: &BigUint) -> Ordering {
89        cmp_slice(&self.data[..], &other.data[..])
90    }
91}
92
93impl Default for BigUint {
94    #[inline]
95    fn default() -> BigUint {
96        Zero::zero()
97    }
98}
99
100impl fmt::Display for BigUint {
101    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
102        f.pad_integral(true, "", &self.to_str_radix(10))
103    }
104}
105
106impl fmt::LowerHex for BigUint {
107    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
108        f.pad_integral(true, "0x", &self.to_str_radix(16))
109    }
110}
111
112impl fmt::UpperHex for BigUint {
113    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
114        let mut s = self.to_str_radix(16);
115        s.make_ascii_uppercase();
116        f.pad_integral(true, "0x", &s)
117    }
118}
119
120impl fmt::Binary for BigUint {
121    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
122        f.pad_integral(true, "0b", &self.to_str_radix(2))
123    }
124}
125
126impl fmt::Octal for BigUint {
127    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
128        f.pad_integral(true, "0o", &self.to_str_radix(8))
129    }
130}
131
132impl FromStr for BigUint {
133    type Err = ParseBigIntError;
134
135    #[inline]
136    fn from_str(s: &str) -> Result<BigUint, ParseBigIntError> {
137        BigUint::from_str_radix(s, 10)
138    }
139}
140
141// Convert from a power of two radix (bits == ilog2(radix)) where bits evenly divides
142// BigDigit::BITS
143fn from_bitwise_digits_le(v: &[u8], bits: usize) -> BigUint {
144    debug_assert!(!v.is_empty() && bits <= 8 && big_digit::BITS % bits == 0);
145    debug_assert!(v.iter().all(|&c| BigDigit::from(c) < (1 << bits)));
146
147    let digits_per_big_digit = big_digit::BITS / bits;
148
149    let data = v
150        .chunks(digits_per_big_digit)
151        .map(|chunk| {
152            chunk
153                .iter()
154                .rev()
155                .fold(0, |acc, &c| (acc << bits) | BigDigit::from(c))
156        })
157        .collect();
158
159    BigUint::new(data)
160}
161
162// Convert from a power of two radix (bits == ilog2(radix)) where bits doesn't evenly divide
163// BigDigit::BITS
164fn from_inexact_bitwise_digits_le(v: &[u8], bits: usize) -> BigUint {
165    debug_assert!(!v.is_empty() && bits <= 8 && big_digit::BITS % bits != 0);
166    debug_assert!(v.iter().all(|&c| BigDigit::from(c) < (1 << bits)));
167
168    let big_digits = (v.len() * bits + big_digit::BITS - 1) / big_digit::BITS;
169    let mut data = Vec::with_capacity(big_digits);
170
171    let mut d = 0;
172    let mut dbits = 0; // number of bits we currently have in d
173
174    // walk v accumululating bits in d; whenever we accumulate big_digit::BITS in d, spit out a
175    // big_digit:
176    for &c in v {
177        d |= BigDigit::from(c) << dbits;
178        dbits += bits;
179
180        if dbits >= big_digit::BITS {
181            data.push(d);
182            dbits -= big_digit::BITS;
183            // if dbits was > big_digit::BITS, we dropped some of the bits in c (they couldn't fit
184            // in d) - grab the bits we lost here:
185            d = BigDigit::from(c) >> (bits - dbits);
186        }
187    }
188
189    if dbits > 0 {
190        debug_assert!(dbits < big_digit::BITS);
191        data.push(d as BigDigit);
192    }
193
194    BigUint::new(data)
195}
196
197// Read little-endian radix digits
198fn from_radix_digits_be(v: &[u8], radix: u32) -> BigUint {
199    debug_assert!(!v.is_empty() && !radix.is_power_of_two());
200    debug_assert!(v.iter().all(|&c| u32::from(c) < radix));
201
202    // Estimate how big the result will be, so we can pre-allocate it.
203    let bits = f64::from(radix).log2() * v.len() as f64;
204    let big_digits = (bits / big_digit::BITS as f64).ceil();
205    let mut data = Vec::with_capacity(big_digits as usize);
206
207    let (base, power) = get_radix_base(radix);
208    let radix = radix as BigDigit;
209
210    let r = v.len() % power;
211    let i = if r == 0 { power } else { r };
212    let (head, tail) = v.split_at(i);
213
214    let first = head
215        .iter()
216        .fold(0, |acc, &d| acc * radix + BigDigit::from(d));
217    data.push(first);
218
219    debug_assert!(tail.len() % power == 0);
220    for chunk in tail.chunks(power) {
221        if data.last() != Some(&0) {
222            data.push(0);
223        }
224
225        let mut carry = 0;
226        for d in data.iter_mut() {
227            *d = mac_with_carry(0, *d, base, &mut carry);
228        }
229        debug_assert!(carry == 0);
230
231        let n = chunk
232            .iter()
233            .fold(0, |acc, &d| acc * radix + BigDigit::from(d));
234        add2(&mut data, &[n]);
235    }
236
237    BigUint::new(data)
238}
239
240impl Num for BigUint {
241    type FromStrRadixErr = ParseBigIntError;
242
243    /// Creates and initializes a `BigUint`.
244    fn from_str_radix(s: &str, radix: u32) -> Result<BigUint, ParseBigIntError> {
245        assert!(2 <= radix && radix <= 36, "The radix must be within 2...36");
246        let mut s = s;
247        if s.starts_with('+') {
248            let tail = &s[1..];
249            if !tail.starts_with('+') {
250                s = tail
251            }
252        }
253
254        if s.is_empty() {
255            return Err(ParseBigIntError::empty());
256        }
257
258        if s.starts_with('_') {
259            // Must lead with a real digit!
260            return Err(ParseBigIntError::invalid());
261        }
262
263        // First normalize all characters to plain digit values
264        let mut v = Vec::with_capacity(s.len());
265        for b in s.bytes() {
266            #[allow(unknown_lints, ellipsis_inclusive_range_patterns)]
267            let d = match b {
268                b'0'...b'9' => b - b'0',
269                b'a'...b'z' => b - b'a' + 10,
270                b'A'...b'Z' => b - b'A' + 10,
271                b'_' => continue,
272                _ => u8::MAX,
273            };
274            if d < radix as u8 {
275                v.push(d);
276            } else {
277                return Err(ParseBigIntError::invalid());
278            }
279        }
280
281        let res = if radix.is_power_of_two() {
282            // Powers of two can use bitwise masks and shifting instead of multiplication
283            let bits = ilog2(radix);
284            v.reverse();
285            if big_digit::BITS % bits == 0 {
286                from_bitwise_digits_le(&v, bits)
287            } else {
288                from_inexact_bitwise_digits_le(&v, bits)
289            }
290        } else {
291            from_radix_digits_be(&v, radix)
292        };
293        Ok(res)
294    }
295}
296
297forward_val_val_binop!(impl BitAnd for BigUint, bitand);
298forward_ref_val_binop!(impl BitAnd for BigUint, bitand);
299
300// do not use forward_ref_ref_binop_commutative! for bitand so that we can
301// clone the smaller value rather than the larger, avoiding over-allocation
302impl<'a, 'b> BitAnd<&'b BigUint> for &'a BigUint {
303    type Output = BigUint;
304
305    #[inline]
306    fn bitand(self, other: &BigUint) -> BigUint {
307        // forward to val-ref, choosing the smaller to clone
308        if self.data.len() <= other.data.len() {
309            self.clone() & other
310        } else {
311            other.clone() & self
312        }
313    }
314}
315
316forward_val_assign!(impl BitAndAssign for BigUint, bitand_assign);
317
318impl<'a> BitAnd<&'a BigUint> for BigUint {
319    type Output = BigUint;
320
321    #[inline]
322    fn bitand(mut self, other: &BigUint) -> BigUint {
323        self &= other;
324        self
325    }
326}
327impl<'a> BitAndAssign<&'a BigUint> for BigUint {
328    #[inline]
329    fn bitand_assign(&mut self, other: &BigUint) {
330        for (ai, &bi) in self.data.iter_mut().zip(other.data.iter()) {
331            *ai &= bi;
332        }
333        self.data.truncate(other.data.len());
334        self.normalize();
335    }
336}
337
338forward_all_binop_to_val_ref_commutative!(impl BitOr for BigUint, bitor);
339forward_val_assign!(impl BitOrAssign for BigUint, bitor_assign);
340
341impl<'a> BitOr<&'a BigUint> for BigUint {
342    type Output = BigUint;
343
344    fn bitor(mut self, other: &BigUint) -> BigUint {
345        self |= other;
346        self
347    }
348}
349impl<'a> BitOrAssign<&'a BigUint> for BigUint {
350    #[inline]
351    fn bitor_assign(&mut self, other: &BigUint) {
352        for (ai, &bi) in self.data.iter_mut().zip(other.data.iter()) {
353            *ai |= bi;
354        }
355        if other.data.len() > self.data.len() {
356            let extra = &other.data[self.data.len()..];
357            self.data.extend(extra.iter().cloned());
358        }
359    }
360}
361
362forward_all_binop_to_val_ref_commutative!(impl BitXor for BigUint, bitxor);
363forward_val_assign!(impl BitXorAssign for BigUint, bitxor_assign);
364
365impl<'a> BitXor<&'a BigUint> for BigUint {
366    type Output = BigUint;
367
368    fn bitxor(mut self, other: &BigUint) -> BigUint {
369        self ^= other;
370        self
371    }
372}
373impl<'a> BitXorAssign<&'a BigUint> for BigUint {
374    #[inline]
375    fn bitxor_assign(&mut self, other: &BigUint) {
376        for (ai, &bi) in self.data.iter_mut().zip(other.data.iter()) {
377            *ai ^= bi;
378        }
379        if other.data.len() > self.data.len() {
380            let extra = &other.data[self.data.len()..];
381            self.data.extend(extra.iter().cloned());
382        }
383        self.normalize();
384    }
385}
386
387impl Shl<usize> for BigUint {
388    type Output = BigUint;
389
390    #[inline]
391    fn shl(self, rhs: usize) -> BigUint {
392        biguint_shl(Cow::Owned(self), rhs)
393    }
394}
395impl<'a> Shl<usize> for &'a BigUint {
396    type Output = BigUint;
397
398    #[inline]
399    fn shl(self, rhs: usize) -> BigUint {
400        biguint_shl(Cow::Borrowed(self), rhs)
401    }
402}
403
404impl ShlAssign<usize> for BigUint {
405    #[inline]
406    fn shl_assign(&mut self, rhs: usize) {
407        let n = mem::replace(self, BigUint::zero());
408        *self = n << rhs;
409    }
410}
411
412impl Shr<usize> for BigUint {
413    type Output = BigUint;
414
415    #[inline]
416    fn shr(self, rhs: usize) -> BigUint {
417        biguint_shr(Cow::Owned(self), rhs)
418    }
419}
420impl<'a> Shr<usize> for &'a BigUint {
421    type Output = BigUint;
422
423    #[inline]
424    fn shr(self, rhs: usize) -> BigUint {
425        biguint_shr(Cow::Borrowed(self), rhs)
426    }
427}
428
429impl ShrAssign<usize> for BigUint {
430    #[inline]
431    fn shr_assign(&mut self, rhs: usize) {
432        let n = mem::replace(self, BigUint::zero());
433        *self = n >> rhs;
434    }
435}
436
437impl Zero for BigUint {
438    #[inline]
439    fn zero() -> BigUint {
440        BigUint::new(Vec::new())
441    }
442
443    #[inline]
444    fn set_zero(&mut self) {
445        self.data.clear();
446    }
447
448    #[inline]
449    fn is_zero(&self) -> bool {
450        self.data.is_empty()
451    }
452}
453
454impl One for BigUint {
455    #[inline]
456    fn one() -> BigUint {
457        BigUint::new(vec![1])
458    }
459
460    #[inline]
461    fn set_one(&mut self) {
462        self.data.clear();
463        self.data.push(1);
464    }
465
466    #[inline]
467    fn is_one(&self) -> bool {
468        self.data[..] == [1]
469    }
470}
471
472impl Unsigned for BigUint {}
473
474impl<'a> Pow<BigUint> for &'a BigUint {
475    type Output = BigUint;
476
477    #[inline]
478    fn pow(self, exp: BigUint) -> Self::Output {
479        self.pow(&exp)
480    }
481}
482
483impl<'a, 'b> Pow<&'b BigUint> for &'a BigUint {
484    type Output = BigUint;
485
486    #[inline]
487    fn pow(self, exp: &BigUint) -> Self::Output {
488        if self.is_one() || exp.is_zero() {
489            BigUint::one()
490        } else if self.is_zero() {
491            BigUint::zero()
492        } else if let Some(exp) = exp.to_u64() {
493            self.pow(exp)
494        } else {
495            // At this point, `self >= 2` and `exp >= 2⁶⁴`.  The smallest possible result
496            // given `2.pow(2⁶⁴)` would take 2.3 exabytes of memory!
497            panic!("memory overflow")
498        }
499    }
500}
501
502macro_rules! pow_impl {
503    ($T:ty) => {
504        impl<'a> Pow<$T> for &'a BigUint {
505            type Output = BigUint;
506
507            #[inline]
508            fn pow(self, mut exp: $T) -> Self::Output {
509                if exp == 0 {
510                    return BigUint::one();
511                }
512                let mut base = self.clone();
513
514                while exp & 1 == 0 {
515                    base = &base * &base;
516                    exp >>= 1;
517                }
518
519                if exp == 1 {
520                    return base;
521                }
522
523                let mut acc = base.clone();
524                while exp > 1 {
525                    exp >>= 1;
526                    base = &base * &base;
527                    if exp & 1 == 1 {
528                        acc = &acc * &base;
529                    }
530                }
531                acc
532            }
533        }
534
535        impl<'a, 'b> Pow<&'b $T> for &'a BigUint {
536            type Output = BigUint;
537
538            #[inline]
539            fn pow(self, exp: &$T) -> Self::Output {
540                self.pow(*exp)
541            }
542        }
543    };
544}
545
546pow_impl!(u8);
547pow_impl!(u16);
548pow_impl!(u32);
549pow_impl!(u64);
550pow_impl!(usize);
551#[cfg(has_i128)]
552pow_impl!(u128);
553
554forward_all_binop_to_val_ref_commutative!(impl Add for BigUint, add);
555forward_val_assign!(impl AddAssign for BigUint, add_assign);
556
557impl<'a> Add<&'a BigUint> for BigUint {
558    type Output = BigUint;
559
560    fn add(mut self, other: &BigUint) -> BigUint {
561        self += other;
562        self
563    }
564}
565impl<'a> AddAssign<&'a BigUint> for BigUint {
566    #[inline]
567    fn add_assign(&mut self, other: &BigUint) {
568        let self_len = self.data.len();
569        let carry = if self_len < other.data.len() {
570            let lo_carry = __add2(&mut self.data[..], &other.data[..self_len]);
571            self.data.extend_from_slice(&other.data[self_len..]);
572            __add2(&mut self.data[self_len..], &[lo_carry])
573        } else {
574            __add2(&mut self.data[..], &other.data[..])
575        };
576        if carry != 0 {
577            self.data.push(carry);
578        }
579    }
580}
581
582promote_unsigned_scalars!(impl Add for BigUint, add);
583promote_unsigned_scalars_assign!(impl AddAssign for BigUint, add_assign);
584forward_all_scalar_binop_to_val_val_commutative!(impl Add<u32> for BigUint, add);
585forward_all_scalar_binop_to_val_val_commutative!(impl Add<u64> for BigUint, add);
586#[cfg(has_i128)]
587forward_all_scalar_binop_to_val_val_commutative!(impl Add<u128> for BigUint, add);
588
589impl Add<u32> for BigUint {
590    type Output = BigUint;
591
592    #[inline]
593    fn add(mut self, other: u32) -> BigUint {
594        self += other;
595        self
596    }
597}
598
599impl AddAssign<u32> for BigUint {
600    #[inline]
601    fn add_assign(&mut self, other: u32) {
602        if other != 0 {
603            if self.data.is_empty() {
604                self.data.push(0);
605            }
606
607            let carry = __add2(&mut self.data, &[other as BigDigit]);
608            if carry != 0 {
609                self.data.push(carry);
610            }
611        }
612    }
613}
614
615impl Add<u64> for BigUint {
616    type Output = BigUint;
617
618    #[inline]
619    fn add(mut self, other: u64) -> BigUint {
620        self += other;
621        self
622    }
623}
624
625impl AddAssign<u64> for BigUint {
626    #[inline]
627    fn add_assign(&mut self, other: u64) {
628        let (hi, lo) = big_digit::from_doublebigdigit(other);
629        if hi == 0 {
630            *self += lo;
631        } else {
632            while self.data.len() < 2 {
633                self.data.push(0);
634            }
635
636            let carry = __add2(&mut self.data, &[lo, hi]);
637            if carry != 0 {
638                self.data.push(carry);
639            }
640        }
641    }
642}
643
644#[cfg(has_i128)]
645impl Add<u128> for BigUint {
646    type Output = BigUint;
647
648    #[inline]
649    fn add(mut self, other: u128) -> BigUint {
650        self += other;
651        self
652    }
653}
654
655#[cfg(has_i128)]
656impl AddAssign<u128> for BigUint {
657    #[inline]
658    fn add_assign(&mut self, other: u128) {
659        if other <= u128::from(u64::max_value()) {
660            *self += other as u64
661        } else {
662            let (a, b, c, d) = u32_from_u128(other);
663            let carry = if a > 0 {
664                while self.data.len() < 4 {
665                    self.data.push(0);
666                }
667                __add2(&mut self.data, &[d, c, b, a])
668            } else {
669                debug_assert!(b > 0);
670                while self.data.len() < 3 {
671                    self.data.push(0);
672                }
673                __add2(&mut self.data, &[d, c, b])
674            };
675
676            if carry != 0 {
677                self.data.push(carry);
678            }
679        }
680    }
681}
682
683forward_val_val_binop!(impl Sub for BigUint, sub);
684forward_ref_ref_binop!(impl Sub for BigUint, sub);
685forward_val_assign!(impl SubAssign for BigUint, sub_assign);
686
687impl<'a> Sub<&'a BigUint> for BigUint {
688    type Output = BigUint;
689
690    fn sub(mut self, other: &BigUint) -> BigUint {
691        self -= other;
692        self
693    }
694}
695impl<'a> SubAssign<&'a BigUint> for BigUint {
696    fn sub_assign(&mut self, other: &'a BigUint) {
697        sub2(&mut self.data[..], &other.data[..]);
698        self.normalize();
699    }
700}
701
702impl<'a> Sub<BigUint> for &'a BigUint {
703    type Output = BigUint;
704
705    fn sub(self, mut other: BigUint) -> BigUint {
706        let other_len = other.data.len();
707        if other_len < self.data.len() {
708            let lo_borrow = __sub2rev(&self.data[..other_len], &mut other.data);
709            other.data.extend_from_slice(&self.data[other_len..]);
710            if lo_borrow != 0 {
711                sub2(&mut other.data[other_len..], &[1])
712            }
713        } else {
714            sub2rev(&self.data[..], &mut other.data[..]);
715        }
716        other.normalized()
717    }
718}
719
720promote_unsigned_scalars!(impl Sub for BigUint, sub);
721promote_unsigned_scalars_assign!(impl SubAssign for BigUint, sub_assign);
722forward_all_scalar_binop_to_val_val!(impl Sub<u32> for BigUint, sub);
723forward_all_scalar_binop_to_val_val!(impl Sub<u64> for BigUint, sub);
724#[cfg(has_i128)]
725forward_all_scalar_binop_to_val_val!(impl Sub<u128> for BigUint, sub);
726
727impl Sub<u32> for BigUint {
728    type Output = BigUint;
729
730    #[inline]
731    fn sub(mut self, other: u32) -> BigUint {
732        self -= other;
733        self
734    }
735}
736impl SubAssign<u32> for BigUint {
737    fn sub_assign(&mut self, other: u32) {
738        sub2(&mut self.data[..], &[other as BigDigit]);
739        self.normalize();
740    }
741}
742
743impl Sub<BigUint> for u32 {
744    type Output = BigUint;
745
746    #[inline]
747    fn sub(self, mut other: BigUint) -> BigUint {
748        if other.data.is_empty() {
749            other.data.push(self as BigDigit);
750        } else {
751            sub2rev(&[self as BigDigit], &mut other.data[..]);
752        }
753        other.normalized()
754    }
755}
756
757impl Sub<u64> for BigUint {
758    type Output = BigUint;
759
760    #[inline]
761    fn sub(mut self, other: u64) -> BigUint {
762        self -= other;
763        self
764    }
765}
766
767impl SubAssign<u64> for BigUint {
768    #[inline]
769    fn sub_assign(&mut self, other: u64) {
770        let (hi, lo) = big_digit::from_doublebigdigit(other);
771        sub2(&mut self.data[..], &[lo, hi]);
772        self.normalize();
773    }
774}
775
776impl Sub<BigUint> for u64 {
777    type Output = BigUint;
778
779    #[inline]
780    fn sub(self, mut other: BigUint) -> BigUint {
781        while other.data.len() < 2 {
782            other.data.push(0);
783        }
784
785        let (hi, lo) = big_digit::from_doublebigdigit(self);
786        sub2rev(&[lo, hi], &mut other.data[..]);
787        other.normalized()
788    }
789}
790
791#[cfg(has_i128)]
792impl Sub<u128> for BigUint {
793    type Output = BigUint;
794
795    #[inline]
796    fn sub(mut self, other: u128) -> BigUint {
797        self -= other;
798        self
799    }
800}
801#[cfg(has_i128)]
802impl SubAssign<u128> for BigUint {
803    fn sub_assign(&mut self, other: u128) {
804        let (a, b, c, d) = u32_from_u128(other);
805        sub2(&mut self.data[..], &[d, c, b, a]);
806        self.normalize();
807    }
808}
809
810#[cfg(has_i128)]
811impl Sub<BigUint> for u128 {
812    type Output = BigUint;
813
814    #[inline]
815    fn sub(self, mut other: BigUint) -> BigUint {
816        while other.data.len() < 4 {
817            other.data.push(0);
818        }
819
820        let (a, b, c, d) = u32_from_u128(self);
821        sub2rev(&[d, c, b, a], &mut other.data[..]);
822        other.normalized()
823    }
824}
825
826forward_all_binop_to_ref_ref!(impl Mul for BigUint, mul);
827forward_val_assign!(impl MulAssign for BigUint, mul_assign);
828
829impl<'a, 'b> Mul<&'b BigUint> for &'a BigUint {
830    type Output = BigUint;
831
832    #[inline]
833    fn mul(self, other: &BigUint) -> BigUint {
834        mul3(&self.data[..], &other.data[..])
835    }
836}
837impl<'a> MulAssign<&'a BigUint> for BigUint {
838    #[inline]
839    fn mul_assign(&mut self, other: &'a BigUint) {
840        *self = &*self * other
841    }
842}
843
844promote_unsigned_scalars!(impl Mul for BigUint, mul);
845promote_unsigned_scalars_assign!(impl MulAssign for BigUint, mul_assign);
846forward_all_scalar_binop_to_val_val_commutative!(impl Mul<u32> for BigUint, mul);
847forward_all_scalar_binop_to_val_val_commutative!(impl Mul<u64> for BigUint, mul);
848#[cfg(has_i128)]
849forward_all_scalar_binop_to_val_val_commutative!(impl Mul<u128> for BigUint, mul);
850
851impl Mul<u32> for BigUint {
852    type Output = BigUint;
853
854    #[inline]
855    fn mul(mut self, other: u32) -> BigUint {
856        self *= other;
857        self
858    }
859}
860impl MulAssign<u32> for BigUint {
861    #[inline]
862    fn mul_assign(&mut self, other: u32) {
863        if other == 0 {
864            self.data.clear();
865        } else {
866            let carry = scalar_mul(&mut self.data[..], other as BigDigit);
867            if carry != 0 {
868                self.data.push(carry);
869            }
870        }
871    }
872}
873
874impl Mul<u64> for BigUint {
875    type Output = BigUint;
876
877    #[inline]
878    fn mul(mut self, other: u64) -> BigUint {
879        self *= other;
880        self
881    }
882}
883impl MulAssign<u64> for BigUint {
884    #[inline]
885    fn mul_assign(&mut self, other: u64) {
886        if other == 0 {
887            self.data.clear();
888        } else if other <= u64::from(BigDigit::max_value()) {
889            *self *= other as BigDigit
890        } else {
891            let (hi, lo) = big_digit::from_doublebigdigit(other);
892            *self = mul3(&self.data[..], &[lo, hi])
893        }
894    }
895}
896
897#[cfg(has_i128)]
898impl Mul<u128> for BigUint {
899    type Output = BigUint;
900
901    #[inline]
902    fn mul(mut self, other: u128) -> BigUint {
903        self *= other;
904        self
905    }
906}
907#[cfg(has_i128)]
908impl MulAssign<u128> for BigUint {
909    #[inline]
910    fn mul_assign(&mut self, other: u128) {
911        if other == 0 {
912            self.data.clear();
913        } else if other <= u128::from(BigDigit::max_value()) {
914            *self *= other as BigDigit
915        } else {
916            let (a, b, c, d) = u32_from_u128(other);
917            *self = mul3(&self.data[..], &[d, c, b, a])
918        }
919    }
920}
921
922forward_val_ref_binop!(impl Div for BigUint, div);
923forward_ref_val_binop!(impl Div for BigUint, div);
924forward_val_assign!(impl DivAssign for BigUint, div_assign);
925
926impl Div<BigUint> for BigUint {
927    type Output = BigUint;
928
929    #[inline]
930    fn div(self, other: BigUint) -> BigUint {
931        let (q, _) = div_rem(self, other);
932        q
933    }
934}
935
936impl<'a, 'b> Div<&'b BigUint> for &'a BigUint {
937    type Output = BigUint;
938
939    #[inline]
940    fn div(self, other: &BigUint) -> BigUint {
941        let (q, _) = self.div_rem(other);
942        q
943    }
944}
945impl<'a> DivAssign<&'a BigUint> for BigUint {
946    #[inline]
947    fn div_assign(&mut self, other: &'a BigUint) {
948        *self = &*self / other;
949    }
950}
951
952promote_unsigned_scalars!(impl Div for BigUint, div);
953promote_unsigned_scalars_assign!(impl DivAssign for BigUint, div_assign);
954forward_all_scalar_binop_to_val_val!(impl Div<u32> for BigUint, div);
955forward_all_scalar_binop_to_val_val!(impl Div<u64> for BigUint, div);
956#[cfg(has_i128)]
957forward_all_scalar_binop_to_val_val!(impl Div<u128> for BigUint, div);
958
959impl Div<u32> for BigUint {
960    type Output = BigUint;
961
962    #[inline]
963    fn div(self, other: u32) -> BigUint {
964        let (q, _) = div_rem_digit(self, other as BigDigit);
965        q
966    }
967}
968impl DivAssign<u32> for BigUint {
969    #[inline]
970    fn div_assign(&mut self, other: u32) {
971        *self = &*self / other;
972    }
973}
974
975impl Div<BigUint> for u32 {
976    type Output = BigUint;
977
978    #[inline]
979    fn div(self, other: BigUint) -> BigUint {
980        match other.data.len() {
981            0 => panic!(),
982            1 => From::from(self as BigDigit / other.data[0]),
983            _ => Zero::zero(),
984        }
985    }
986}
987
988impl Div<u64> for BigUint {
989    type Output = BigUint;
990
991    #[inline]
992    fn div(self, other: u64) -> BigUint {
993        let (q, _) = div_rem(self, From::from(other));
994        q
995    }
996}
997impl DivAssign<u64> for BigUint {
998    #[inline]
999    fn div_assign(&mut self, other: u64) {
1000        // a vec of size 0 does not allocate, so this is fairly cheap
1001        let temp = mem::replace(self, Zero::zero());
1002        *self = temp / other;
1003    }
1004}
1005
1006impl Div<BigUint> for u64 {
1007    type Output = BigUint;
1008
1009    #[inline]
1010    fn div(self, other: BigUint) -> BigUint {
1011        match other.data.len() {
1012            0 => panic!(),
1013            1 => From::from(self / u64::from(other.data[0])),
1014            2 => From::from(self / big_digit::to_doublebigdigit(other.data[1], other.data[0])),
1015            _ => Zero::zero(),
1016        }
1017    }
1018}
1019
1020#[cfg(has_i128)]
1021impl Div<u128> for BigUint {
1022    type Output = BigUint;
1023
1024    #[inline]
1025    fn div(self, other: u128) -> BigUint {
1026        let (q, _) = div_rem(self, From::from(other));
1027        q
1028    }
1029}
1030#[cfg(has_i128)]
1031impl DivAssign<u128> for BigUint {
1032    #[inline]
1033    fn div_assign(&mut self, other: u128) {
1034        *self = &*self / other;
1035    }
1036}
1037
1038#[cfg(has_i128)]
1039impl Div<BigUint> for u128 {
1040    type Output = BigUint;
1041
1042    #[inline]
1043    fn div(self, other: BigUint) -> BigUint {
1044        match other.data.len() {
1045            0 => panic!(),
1046            1 => From::from(self / u128::from(other.data[0])),
1047            2 => From::from(
1048                self / u128::from(big_digit::to_doublebigdigit(other.data[1], other.data[0])),
1049            ),
1050            3 => From::from(self / u32_to_u128(0, other.data[2], other.data[1], other.data[0])),
1051            4 => From::from(
1052                self / u32_to_u128(other.data[3], other.data[2], other.data[1], other.data[0]),
1053            ),
1054            _ => Zero::zero(),
1055        }
1056    }
1057}
1058
1059forward_val_ref_binop!(impl Rem for BigUint, rem);
1060forward_ref_val_binop!(impl Rem for BigUint, rem);
1061forward_val_assign!(impl RemAssign for BigUint, rem_assign);
1062
1063impl Rem<BigUint> for BigUint {
1064    type Output = BigUint;
1065
1066    #[inline]
1067    fn rem(self, other: BigUint) -> BigUint {
1068        let (_, r) = div_rem(self, other);
1069        r
1070    }
1071}
1072
1073impl<'a, 'b> Rem<&'b BigUint> for &'a BigUint {
1074    type Output = BigUint;
1075
1076    #[inline]
1077    fn rem(self, other: &BigUint) -> BigUint {
1078        let (_, r) = self.div_rem(other);
1079        r
1080    }
1081}
1082impl<'a> RemAssign<&'a BigUint> for BigUint {
1083    #[inline]
1084    fn rem_assign(&mut self, other: &BigUint) {
1085        *self = &*self % other;
1086    }
1087}
1088
1089promote_unsigned_scalars!(impl Rem for BigUint, rem);
1090promote_unsigned_scalars_assign!(impl RemAssign for BigUint, rem_assign);
1091forward_all_scalar_binop_to_ref_val!(impl Rem<u32> for BigUint, rem);
1092forward_all_scalar_binop_to_val_val!(impl Rem<u64> for BigUint, rem);
1093#[cfg(has_i128)]
1094forward_all_scalar_binop_to_val_val!(impl Rem<u128> for BigUint, rem);
1095
1096impl<'a> Rem<u32> for &'a BigUint {
1097    type Output = BigUint;
1098
1099    #[inline]
1100    fn rem(self, other: u32) -> BigUint {
1101        From::from(rem_digit(self, other as BigDigit))
1102    }
1103}
1104impl RemAssign<u32> for BigUint {
1105    #[inline]
1106    fn rem_assign(&mut self, other: u32) {
1107        *self = &*self % other;
1108    }
1109}
1110
1111impl<'a> Rem<&'a BigUint> for u32 {
1112    type Output = BigUint;
1113
1114    #[inline]
1115    fn rem(mut self, other: &'a BigUint) -> BigUint {
1116        self %= other;
1117        From::from(self)
1118    }
1119}
1120
1121macro_rules! impl_rem_assign_scalar {
1122    ($scalar:ty, $to_scalar:ident) => {
1123        forward_val_assign_scalar!(impl RemAssign for BigUint, $scalar, rem_assign);
1124        impl<'a> RemAssign<&'a BigUint> for $scalar {
1125            #[inline]
1126            fn rem_assign(&mut self, other: &BigUint) {
1127                *self = match other.$to_scalar() {
1128                    None => *self,
1129                    Some(0) => panic!(),
1130                    Some(v) => *self % v
1131                };
1132            }
1133        }
1134    }
1135}
1136// we can scalar %= BigUint for any scalar, including signed types
1137#[cfg(has_i128)]
1138impl_rem_assign_scalar!(u128, to_u128);
1139impl_rem_assign_scalar!(usize, to_usize);
1140impl_rem_assign_scalar!(u64, to_u64);
1141impl_rem_assign_scalar!(u32, to_u32);
1142impl_rem_assign_scalar!(u16, to_u16);
1143impl_rem_assign_scalar!(u8, to_u8);
1144#[cfg(has_i128)]
1145impl_rem_assign_scalar!(i128, to_i128);
1146impl_rem_assign_scalar!(isize, to_isize);
1147impl_rem_assign_scalar!(i64, to_i64);
1148impl_rem_assign_scalar!(i32, to_i32);
1149impl_rem_assign_scalar!(i16, to_i16);
1150impl_rem_assign_scalar!(i8, to_i8);
1151
1152impl Rem<u64> for BigUint {
1153    type Output = BigUint;
1154
1155    #[inline]
1156    fn rem(self, other: u64) -> BigUint {
1157        let (_, r) = div_rem(self, From::from(other));
1158        r
1159    }
1160}
1161impl RemAssign<u64> for BigUint {
1162    #[inline]
1163    fn rem_assign(&mut self, other: u64) {
1164        *self = &*self % other;
1165    }
1166}
1167
1168impl Rem<BigUint> for u64 {
1169    type Output = BigUint;
1170
1171    #[inline]
1172    fn rem(mut self, other: BigUint) -> BigUint {
1173        self %= other;
1174        From::from(self)
1175    }
1176}
1177
1178#[cfg(has_i128)]
1179impl Rem<u128> for BigUint {
1180    type Output = BigUint;
1181
1182    #[inline]
1183    fn rem(self, other: u128) -> BigUint {
1184        let (_, r) = div_rem(self, From::from(other));
1185        r
1186    }
1187}
1188#[cfg(has_i128)]
1189impl RemAssign<u128> for BigUint {
1190    #[inline]
1191    fn rem_assign(&mut self, other: u128) {
1192        *self = &*self % other;
1193    }
1194}
1195
1196#[cfg(has_i128)]
1197impl Rem<BigUint> for u128 {
1198    type Output = BigUint;
1199
1200    #[inline]
1201    fn rem(mut self, other: BigUint) -> BigUint {
1202        self %= other;
1203        From::from(self)
1204    }
1205}
1206
1207impl Neg for BigUint {
1208    type Output = BigUint;
1209
1210    #[inline]
1211    fn neg(self) -> BigUint {
1212        panic!()
1213    }
1214}
1215
1216impl<'a> Neg for &'a BigUint {
1217    type Output = BigUint;
1218
1219    #[inline]
1220    fn neg(self) -> BigUint {
1221        panic!()
1222    }
1223}
1224
1225impl CheckedAdd for BigUint {
1226    #[inline]
1227    fn checked_add(&self, v: &BigUint) -> Option<BigUint> {
1228        Some(self.add(v))
1229    }
1230}
1231
1232impl CheckedSub for BigUint {
1233    #[inline]
1234    fn checked_sub(&self, v: &BigUint) -> Option<BigUint> {
1235        match self.cmp(v) {
1236            Less => None,
1237            Equal => Some(Zero::zero()),
1238            Greater => Some(self.sub(v)),
1239        }
1240    }
1241}
1242
1243impl CheckedMul for BigUint {
1244    #[inline]
1245    fn checked_mul(&self, v: &BigUint) -> Option<BigUint> {
1246        Some(self.mul(v))
1247    }
1248}
1249
1250impl CheckedDiv for BigUint {
1251    #[inline]
1252    fn checked_div(&self, v: &BigUint) -> Option<BigUint> {
1253        if v.is_zero() {
1254            return None;
1255        }
1256        Some(self.div(v))
1257    }
1258}
1259
1260impl Integer for BigUint {
1261    #[inline]
1262    fn div_rem(&self, other: &BigUint) -> (BigUint, BigUint) {
1263        div_rem_ref(self, other)
1264    }
1265
1266    #[inline]
1267    fn div_floor(&self, other: &BigUint) -> BigUint {
1268        let (d, _) = div_rem_ref(self, other);
1269        d
1270    }
1271
1272    #[inline]
1273    fn mod_floor(&self, other: &BigUint) -> BigUint {
1274        let (_, m) = div_rem_ref(self, other);
1275        m
1276    }
1277
1278    #[inline]
1279    fn div_mod_floor(&self, other: &BigUint) -> (BigUint, BigUint) {
1280        div_rem_ref(self, other)
1281    }
1282
1283    /// Calculates the Greatest Common Divisor (GCD) of the number and `other`.
1284    ///
1285    /// The result is always positive.
1286    #[inline]
1287    fn gcd(&self, other: &Self) -> Self {
1288        #[inline]
1289        fn twos(x: &BigUint) -> usize {
1290            trailing_zeros(x).unwrap_or(0)
1291        }
1292
1293        // Stein's algorithm
1294        if self.is_zero() {
1295            return other.clone();
1296        }
1297        if other.is_zero() {
1298            return self.clone();
1299        }
1300        let mut m = self.clone();
1301        let mut n = other.clone();
1302
1303        // find common factors of 2
1304        let shift = cmp::min(twos(&n), twos(&m));
1305
1306        // divide m and n by 2 until odd
1307        // m inside loop
1308        n >>= twos(&n);
1309
1310        while !m.is_zero() {
1311            m >>= twos(&m);
1312            if n > m {
1313                mem::swap(&mut n, &mut m)
1314            }
1315            m -= &n;
1316        }
1317
1318        n << shift
1319    }
1320
1321    /// Calculates the Lowest Common Multiple (LCM) of the number and `other`.
1322    #[inline]
1323    fn lcm(&self, other: &BigUint) -> BigUint {
1324        if self.is_zero() && other.is_zero() {
1325            Self::zero()
1326        } else {
1327            self / self.gcd(other) * other
1328        }
1329    }
1330
1331    /// Deprecated, use `is_multiple_of` instead.
1332    #[inline]
1333    fn divides(&self, other: &BigUint) -> bool {
1334        self.is_multiple_of(other)
1335    }
1336
1337    /// Returns `true` if the number is a multiple of `other`.
1338    #[inline]
1339    fn is_multiple_of(&self, other: &BigUint) -> bool {
1340        (self % other).is_zero()
1341    }
1342
1343    /// Returns `true` if the number is divisible by `2`.
1344    #[inline]
1345    fn is_even(&self) -> bool {
1346        // Considering only the last digit.
1347        match self.data.first() {
1348            Some(x) => x.is_even(),
1349            None => true,
1350        }
1351    }
1352
1353    /// Returns `true` if the number is not divisible by `2`.
1354    #[inline]
1355    fn is_odd(&self) -> bool {
1356        !self.is_even()
1357    }
1358}
1359
1360#[inline]
1361fn fixpoint<F>(mut x: BigUint, max_bits: usize, f: F) -> BigUint
1362where
1363    F: Fn(&BigUint) -> BigUint,
1364{
1365    let mut xn = f(&x);
1366
1367    // If the value increased, then the initial guess must have been low.
1368    // Repeat until we reverse course.
1369    while x < xn {
1370        // Sometimes an increase will go way too far, especially with large
1371        // powers, and then take a long time to walk back.  We know an upper
1372        // bound based on bit size, so saturate on that.
1373        x = if xn.bits() > max_bits {
1374            BigUint::one() << max_bits
1375        } else {
1376            xn
1377        };
1378        xn = f(&x);
1379    }
1380
1381    // Now keep repeating while the estimate is decreasing.
1382    while x > xn {
1383        x = xn;
1384        xn = f(&x);
1385    }
1386    x
1387}
1388
1389impl Roots for BigUint {
1390    // nth_root, sqrt and cbrt use Newton's method to compute
1391    // principal root of a given degree for a given integer.
1392
1393    // Reference:
1394    // Brent & Zimmermann, Modern Computer Arithmetic, v0.5.9, Algorithm 1.14
1395    fn nth_root(&self, n: u32) -> Self {
1396        assert!(n > 0, "root degree n must be at least 1");
1397
1398        if self.is_zero() || self.is_one() {
1399            return self.clone();
1400        }
1401
1402        match n {
1403            // Optimize for small n
1404            1 => return self.clone(),
1405            2 => return self.sqrt(),
1406            3 => return self.cbrt(),
1407            _ => (),
1408        }
1409
1410        // The root of non-zero values less than 2ⁿ can only be 1.
1411        let bits = self.bits();
1412        if bits <= n as usize {
1413            return BigUint::one();
1414        }
1415
1416        // If we fit in `u64`, compute the root that way.
1417        if let Some(x) = self.to_u64() {
1418            return x.nth_root(n).into();
1419        }
1420
1421        let max_bits = bits / n as usize + 1;
1422
1423        let guess = if let Some(f) = self.to_f64() {
1424            // We fit in `f64` (lossy), so get a better initial guess from that.
1425            BigUint::from_f64((f.ln() / f64::from(n)).exp()).unwrap()
1426        } else {
1427            // Try to guess by scaling down such that it does fit in `f64`.
1428            // With some (x * 2ⁿᵏ), its nth root ≈ (ⁿ√x * 2ᵏ)
1429            let nsz = n as usize;
1430            let extra_bits = bits - (f64::MAX_EXP as usize - 1);
1431            let root_scale = (extra_bits + (nsz - 1)) / nsz;
1432            let scale = root_scale * nsz;
1433            if scale < bits && bits - scale > nsz {
1434                (self >> scale).nth_root(n) << root_scale
1435            } else {
1436                BigUint::one() << max_bits
1437            }
1438        };
1439
1440        let n_min_1 = n - 1;
1441        fixpoint(guess, max_bits, move |s| {
1442            let q = self / s.pow(n_min_1);
1443            let t = n_min_1 * s + q;
1444            t / n
1445        })
1446    }
1447
1448    // Reference:
1449    // Brent & Zimmermann, Modern Computer Arithmetic, v0.5.9, Algorithm 1.13
1450    fn sqrt(&self) -> Self {
1451        if self.is_zero() || self.is_one() {
1452            return self.clone();
1453        }
1454
1455        // If we fit in `u64`, compute the root that way.
1456        if let Some(x) = self.to_u64() {
1457            return x.sqrt().into();
1458        }
1459
1460        let bits = self.bits();
1461        let max_bits = bits / 2 as usize + 1;
1462
1463        let guess = if let Some(f) = self.to_f64() {
1464            // We fit in `f64` (lossy), so get a better initial guess from that.
1465            BigUint::from_f64(f.sqrt()).unwrap()
1466        } else {
1467            // Try to guess by scaling down such that it does fit in `f64`.
1468            // With some (x * 2²ᵏ), its sqrt ≈ (√x * 2ᵏ)
1469            let extra_bits = bits - (f64::MAX_EXP as usize - 1);
1470            let root_scale = (extra_bits + 1) / 2;
1471            let scale = root_scale * 2;
1472            (self >> scale).sqrt() << root_scale
1473        };
1474
1475        fixpoint(guess, max_bits, move |s| {
1476            let q = self / s;
1477            let t = s + q;
1478            t >> 1
1479        })
1480    }
1481
1482    fn cbrt(&self) -> Self {
1483        if self.is_zero() || self.is_one() {
1484            return self.clone();
1485        }
1486
1487        // If we fit in `u64`, compute the root that way.
1488        if let Some(x) = self.to_u64() {
1489            return x.cbrt().into();
1490        }
1491
1492        let bits = self.bits();
1493        let max_bits = bits / 3 as usize + 1;
1494
1495        let guess = if let Some(f) = self.to_f64() {
1496            // We fit in `f64` (lossy), so get a better initial guess from that.
1497            BigUint::from_f64(f.cbrt()).unwrap()
1498        } else {
1499            // Try to guess by scaling down such that it does fit in `f64`.
1500            // With some (x * 2³ᵏ), its cbrt ≈ (∛x * 2ᵏ)
1501            let extra_bits = bits - (f64::MAX_EXP as usize - 1);
1502            let root_scale = (extra_bits + 2) / 3;
1503            let scale = root_scale * 3;
1504            (self >> scale).cbrt() << root_scale
1505        };
1506
1507        fixpoint(guess, max_bits, move |s| {
1508            let q = self / (s * s);
1509            let t = (s << 1) + q;
1510            t / 3u32
1511        })
1512    }
1513}
1514
1515fn high_bits_to_u64(v: &BigUint) -> u64 {
1516    match v.data.len() {
1517        0 => 0,
1518        1 => u64::from(v.data[0]),
1519        _ => {
1520            let mut bits = v.bits();
1521            let mut ret = 0u64;
1522            let mut ret_bits = 0;
1523
1524            for d in v.data.iter().rev() {
1525                let digit_bits = (bits - 1) % big_digit::BITS + 1;
1526                let bits_want = cmp::min(64 - ret_bits, digit_bits);
1527
1528                if bits_want != 64 {
1529                    ret <<= bits_want;
1530                }
1531                ret |= u64::from(*d) >> (digit_bits - bits_want);
1532                ret_bits += bits_want;
1533                bits -= bits_want;
1534
1535                if ret_bits == 64 {
1536                    break;
1537                }
1538            }
1539
1540            ret
1541        }
1542    }
1543}
1544
1545impl ToPrimitive for BigUint {
1546    #[inline]
1547    fn to_i64(&self) -> Option<i64> {
1548        self.to_u64().as_ref().and_then(u64::to_i64)
1549    }
1550
1551    #[inline]
1552    #[cfg(has_i128)]
1553    fn to_i128(&self) -> Option<i128> {
1554        self.to_u128().as_ref().and_then(u128::to_i128)
1555    }
1556
1557    #[inline]
1558    fn to_u64(&self) -> Option<u64> {
1559        let mut ret: u64 = 0;
1560        let mut bits = 0;
1561
1562        for i in self.data.iter() {
1563            if bits >= 64 {
1564                return None;
1565            }
1566
1567            ret += u64::from(*i) << bits;
1568            bits += big_digit::BITS;
1569        }
1570
1571        Some(ret)
1572    }
1573
1574    #[inline]
1575    #[cfg(has_i128)]
1576    fn to_u128(&self) -> Option<u128> {
1577        let mut ret: u128 = 0;
1578        let mut bits = 0;
1579
1580        for i in self.data.iter() {
1581            if bits >= 128 {
1582                return None;
1583            }
1584
1585            ret |= u128::from(*i) << bits;
1586            bits += big_digit::BITS;
1587        }
1588
1589        Some(ret)
1590    }
1591
1592    #[inline]
1593    fn to_f32(&self) -> Option<f32> {
1594        let mantissa = high_bits_to_u64(self);
1595        let exponent = self.bits() - fls(mantissa);
1596
1597        if exponent > f32::MAX_EXP as usize {
1598            None
1599        } else {
1600            let ret = (mantissa as f32) * 2.0f32.powi(exponent as i32);
1601            if ret.is_infinite() {
1602                None
1603            } else {
1604                Some(ret)
1605            }
1606        }
1607    }
1608
1609    #[inline]
1610    fn to_f64(&self) -> Option<f64> {
1611        let mantissa = high_bits_to_u64(self);
1612        let exponent = self.bits() - fls(mantissa);
1613
1614        if exponent > f64::MAX_EXP as usize {
1615            None
1616        } else {
1617            let ret = (mantissa as f64) * 2.0f64.powi(exponent as i32);
1618            if ret.is_infinite() {
1619                None
1620            } else {
1621                Some(ret)
1622            }
1623        }
1624    }
1625}
1626
1627impl FromPrimitive for BigUint {
1628    #[inline]
1629    fn from_i64(n: i64) -> Option<BigUint> {
1630        if n >= 0 {
1631            Some(BigUint::from(n as u64))
1632        } else {
1633            None
1634        }
1635    }
1636
1637    #[inline]
1638    #[cfg(has_i128)]
1639    fn from_i128(n: i128) -> Option<BigUint> {
1640        if n >= 0 {
1641            Some(BigUint::from(n as u128))
1642        } else {
1643            None
1644        }
1645    }
1646
1647    #[inline]
1648    fn from_u64(n: u64) -> Option<BigUint> {
1649        Some(BigUint::from(n))
1650    }
1651
1652    #[inline]
1653    #[cfg(has_i128)]
1654    fn from_u128(n: u128) -> Option<BigUint> {
1655        Some(BigUint::from(n))
1656    }
1657
1658    #[inline]
1659    fn from_f64(mut n: f64) -> Option<BigUint> {
1660        // handle NAN, INFINITY, NEG_INFINITY
1661        if !n.is_finite() {
1662            return None;
1663        }
1664
1665        // match the rounding of casting from float to int
1666        n = n.trunc();
1667
1668        // handle 0.x, -0.x
1669        if n.is_zero() {
1670            return Some(BigUint::zero());
1671        }
1672
1673        let (mantissa, exponent, sign) = Float::integer_decode(n);
1674
1675        if sign == -1 {
1676            return None;
1677        }
1678
1679        let mut ret = BigUint::from(mantissa);
1680        if exponent > 0 {
1681            ret <<= exponent as usize;
1682        } else if exponent < 0 {
1683            ret >>= (-exponent) as usize;
1684        }
1685        Some(ret)
1686    }
1687}
1688
1689impl From<u64> for BigUint {
1690    #[inline]
1691    fn from(mut n: u64) -> Self {
1692        let mut ret: BigUint = Zero::zero();
1693
1694        while n != 0 {
1695            ret.data.push(n as BigDigit);
1696            // don't overflow if BITS is 64:
1697            n = (n >> 1) >> (big_digit::BITS - 1);
1698        }
1699
1700        ret
1701    }
1702}
1703
1704#[cfg(has_i128)]
1705impl From<u128> for BigUint {
1706    #[inline]
1707    fn from(mut n: u128) -> Self {
1708        let mut ret: BigUint = Zero::zero();
1709
1710        while n != 0 {
1711            ret.data.push(n as BigDigit);
1712            n >>= big_digit::BITS;
1713        }
1714
1715        ret
1716    }
1717}
1718
1719macro_rules! impl_biguint_from_uint {
1720    ($T:ty) => {
1721        impl From<$T> for BigUint {
1722            #[inline]
1723            fn from(n: $T) -> Self {
1724                BigUint::from(n as u64)
1725            }
1726        }
1727    };
1728}
1729
1730impl_biguint_from_uint!(u8);
1731impl_biguint_from_uint!(u16);
1732impl_biguint_from_uint!(u32);
1733impl_biguint_from_uint!(usize);
1734
1735/// A generic trait for converting a value to a `BigUint`.
1736pub trait ToBigUint {
1737    /// Converts the value of `self` to a `BigUint`.
1738    fn to_biguint(&self) -> Option<BigUint>;
1739}
1740
1741impl ToBigUint for BigUint {
1742    #[inline]
1743    fn to_biguint(&self) -> Option<BigUint> {
1744        Some(self.clone())
1745    }
1746}
1747
1748macro_rules! impl_to_biguint {
1749    ($T:ty, $from_ty:path) => {
1750        impl ToBigUint for $T {
1751            #[inline]
1752            fn to_biguint(&self) -> Option<BigUint> {
1753                $from_ty(*self)
1754            }
1755        }
1756    };
1757}
1758
1759impl_to_biguint!(isize, FromPrimitive::from_isize);
1760impl_to_biguint!(i8, FromPrimitive::from_i8);
1761impl_to_biguint!(i16, FromPrimitive::from_i16);
1762impl_to_biguint!(i32, FromPrimitive::from_i32);
1763impl_to_biguint!(i64, FromPrimitive::from_i64);
1764#[cfg(has_i128)]
1765impl_to_biguint!(i128, FromPrimitive::from_i128);
1766
1767impl_to_biguint!(usize, FromPrimitive::from_usize);
1768impl_to_biguint!(u8, FromPrimitive::from_u8);
1769impl_to_biguint!(u16, FromPrimitive::from_u16);
1770impl_to_biguint!(u32, FromPrimitive::from_u32);
1771impl_to_biguint!(u64, FromPrimitive::from_u64);
1772#[cfg(has_i128)]
1773impl_to_biguint!(u128, FromPrimitive::from_u128);
1774
1775impl_to_biguint!(f32, FromPrimitive::from_f32);
1776impl_to_biguint!(f64, FromPrimitive::from_f64);
1777
1778// Extract bitwise digits that evenly divide BigDigit
1779fn to_bitwise_digits_le(u: &BigUint, bits: usize) -> Vec<u8> {
1780    debug_assert!(!u.is_zero() && bits <= 8 && big_digit::BITS % bits == 0);
1781
1782    let last_i = u.data.len() - 1;
1783    let mask: BigDigit = (1 << bits) - 1;
1784    let digits_per_big_digit = big_digit::BITS / bits;
1785    let digits = (u.bits() + bits - 1) / bits;
1786    let mut res = Vec::with_capacity(digits);
1787
1788    for mut r in u.data[..last_i].iter().cloned() {
1789        for _ in 0..digits_per_big_digit {
1790            res.push((r & mask) as u8);
1791            r >>= bits;
1792        }
1793    }
1794
1795    let mut r = u.data[last_i];
1796    while r != 0 {
1797        res.push((r & mask) as u8);
1798        r >>= bits;
1799    }
1800
1801    res
1802}
1803
1804// Extract bitwise digits that don't evenly divide BigDigit
1805fn to_inexact_bitwise_digits_le(u: &BigUint, bits: usize) -> Vec<u8> {
1806    debug_assert!(!u.is_zero() && bits <= 8 && big_digit::BITS % bits != 0);
1807
1808    let mask: BigDigit = (1 << bits) - 1;
1809    let digits = (u.bits() + bits - 1) / bits;
1810    let mut res = Vec::with_capacity(digits);
1811
1812    let mut r = 0;
1813    let mut rbits = 0;
1814
1815    for c in &u.data {
1816        r |= *c << rbits;
1817        rbits += big_digit::BITS;
1818
1819        while rbits >= bits {
1820            res.push((r & mask) as u8);
1821            r >>= bits;
1822
1823            // r had more bits than it could fit - grab the bits we lost
1824            if rbits > big_digit::BITS {
1825                r = *c >> (big_digit::BITS - (rbits - bits));
1826            }
1827
1828            rbits -= bits;
1829        }
1830    }
1831
1832    if rbits != 0 {
1833        res.push(r as u8);
1834    }
1835
1836    while let Some(&0) = res.last() {
1837        res.pop();
1838    }
1839
1840    res
1841}
1842
1843// Extract little-endian radix digits
1844#[inline(always)] // forced inline to get const-prop for radix=10
1845fn to_radix_digits_le(u: &BigUint, radix: u32) -> Vec<u8> {
1846    debug_assert!(!u.is_zero() && !radix.is_power_of_two());
1847
1848    // Estimate how big the result will be, so we can pre-allocate it.
1849    let radix_digits = ((u.bits() as f64) / f64::from(radix).log2()).ceil();
1850    let mut res = Vec::with_capacity(radix_digits as usize);
1851    let mut digits = u.clone();
1852
1853    let (base, power) = get_radix_base(radix);
1854    let radix = radix as BigDigit;
1855
1856    while digits.data.len() > 1 {
1857        let (q, mut r) = div_rem_digit(digits, base);
1858        for _ in 0..power {
1859            res.push((r % radix) as u8);
1860            r /= radix;
1861        }
1862        digits = q;
1863    }
1864
1865    let mut r = digits.data[0];
1866    while r != 0 {
1867        res.push((r % radix) as u8);
1868        r /= radix;
1869    }
1870
1871    res
1872}
1873
1874pub fn to_radix_le(u: &BigUint, radix: u32) -> Vec<u8> {
1875    if u.is_zero() {
1876        vec![0]
1877    } else if radix.is_power_of_two() {
1878        // Powers of two can use bitwise masks and shifting instead of division
1879        let bits = ilog2(radix);
1880        if big_digit::BITS % bits == 0 {
1881            to_bitwise_digits_le(u, bits)
1882        } else {
1883            to_inexact_bitwise_digits_le(u, bits)
1884        }
1885    } else if radix == 10 {
1886        // 10 is so common that it's worth separating out for const-propagation.
1887        // Optimizers can often turn constant division into a faster multiplication.
1888        to_radix_digits_le(u, 10)
1889    } else {
1890        to_radix_digits_le(u, radix)
1891    }
1892}
1893
1894pub fn to_str_radix_reversed(u: &BigUint, radix: u32) -> Vec<u8> {
1895    assert!(2 <= radix && radix <= 36, "The radix must be within 2...36");
1896
1897    if u.is_zero() {
1898        return vec![b'0'];
1899    }
1900
1901    let mut res = to_radix_le(u, radix);
1902
1903    // Now convert everything to ASCII digits.
1904    for r in &mut res {
1905        debug_assert!(u32::from(*r) < radix);
1906        if *r < 10 {
1907            *r += b'0';
1908        } else {
1909            *r += b'a' - 10;
1910        }
1911    }
1912    res
1913}
1914
1915impl BigUint {
1916    /// Creates and initializes a `BigUint`.
1917    ///
1918    /// The base 2<sup>32</sup> digits are ordered least significant digit first.
1919    #[inline]
1920    pub fn new(digits: Vec<u32>) -> BigUint {
1921        BigUint { data: digits }.normalized()
1922    }
1923
1924    /// Creates and initializes a `BigUint`.
1925    ///
1926    /// The base 2<sup>32</sup> digits are ordered least significant digit first.
1927    #[inline]
1928    pub fn from_slice(slice: &[u32]) -> BigUint {
1929        BigUint::new(slice.to_vec())
1930    }
1931
1932    /// Assign a value to a `BigUint`.
1933    ///
1934    /// The base 2<sup>32</sup> digits are ordered least significant digit first.
1935    #[inline]
1936    pub fn assign_from_slice(&mut self, slice: &[u32]) {
1937        self.data.resize(slice.len(), 0);
1938        self.data.clone_from_slice(slice);
1939        self.normalize();
1940    }
1941
1942    /// Creates and initializes a `BigUint`.
1943    ///
1944    /// The bytes are in big-endian byte order.
1945    ///
1946    /// # Examples
1947    ///
1948    /// ```
1949    /// use num_bigint::BigUint;
1950    ///
1951    /// assert_eq!(BigUint::from_bytes_be(b"A"),
1952    ///            BigUint::parse_bytes(b"65", 10).unwrap());
1953    /// assert_eq!(BigUint::from_bytes_be(b"AA"),
1954    ///            BigUint::parse_bytes(b"16705", 10).unwrap());
1955    /// assert_eq!(BigUint::from_bytes_be(b"AB"),
1956    ///            BigUint::parse_bytes(b"16706", 10).unwrap());
1957    /// assert_eq!(BigUint::from_bytes_be(b"Hello world!"),
1958    ///            BigUint::parse_bytes(b"22405534230753963835153736737", 10).unwrap());
1959    /// ```
1960    #[inline]
1961    pub fn from_bytes_be(bytes: &[u8]) -> BigUint {
1962        if bytes.is_empty() {
1963            Zero::zero()
1964        } else {
1965            let mut v = bytes.to_vec();
1966            v.reverse();
1967            BigUint::from_bytes_le(&*v)
1968        }
1969    }
1970
1971    /// Creates and initializes a `BigUint`.
1972    ///
1973    /// The bytes are in little-endian byte order.
1974    #[inline]
1975    pub fn from_bytes_le(bytes: &[u8]) -> BigUint {
1976        if bytes.is_empty() {
1977            Zero::zero()
1978        } else {
1979            from_bitwise_digits_le(bytes, 8)
1980        }
1981    }
1982
1983    /// Creates and initializes a `BigUint`. The input slice must contain
1984    /// ascii/utf8 characters in [0-9a-zA-Z].
1985    /// `radix` must be in the range `2...36`.
1986    ///
1987    /// The function `from_str_radix` from the `Num` trait provides the same logic
1988    /// for `&str` buffers.
1989    ///
1990    /// # Examples
1991    ///
1992    /// ```
1993    /// use num_bigint::{BigUint, ToBigUint};
1994    ///
1995    /// assert_eq!(BigUint::parse_bytes(b"1234", 10), ToBigUint::to_biguint(&1234));
1996    /// assert_eq!(BigUint::parse_bytes(b"ABCD", 16), ToBigUint::to_biguint(&0xABCD));
1997    /// assert_eq!(BigUint::parse_bytes(b"G", 16), None);
1998    /// ```
1999    #[inline]
2000    pub fn parse_bytes(buf: &[u8], radix: u32) -> Option<BigUint> {
2001        str::from_utf8(buf)
2002            .ok()
2003            .and_then(|s| BigUint::from_str_radix(s, radix).ok())
2004    }
2005
2006    /// Creates and initializes a `BigUint`. Each u8 of the input slice is
2007    /// interpreted as one digit of the number
2008    /// and must therefore be less than `radix`.
2009    ///
2010    /// The bytes are in big-endian byte order.
2011    /// `radix` must be in the range `2...256`.
2012    ///
2013    /// # Examples
2014    ///
2015    /// ```
2016    /// use num_bigint::{BigUint};
2017    ///
2018    /// let inbase190 = &[15, 33, 125, 12, 14];
2019    /// let a = BigUint::from_radix_be(inbase190, 190).unwrap();
2020    /// assert_eq!(a.to_radix_be(190), inbase190);
2021    /// ```
2022    pub fn from_radix_be(buf: &[u8], radix: u32) -> Option<BigUint> {
2023        assert!(
2024            2 <= radix && radix <= 256,
2025            "The radix must be within 2...256"
2026        );
2027
2028        if radix != 256 && buf.iter().any(|&b| b >= radix as u8) {
2029            return None;
2030        }
2031
2032        let res = if radix.is_power_of_two() {
2033            // Powers of two can use bitwise masks and shifting instead of multiplication
2034            let bits = ilog2(radix);
2035            let mut v = Vec::from(buf);
2036            v.reverse();
2037            if big_digit::BITS % bits == 0 {
2038                from_bitwise_digits_le(&v, bits)
2039            } else {
2040                from_inexact_bitwise_digits_le(&v, bits)
2041            }
2042        } else {
2043            from_radix_digits_be(buf, radix)
2044        };
2045
2046        Some(res)
2047    }
2048
2049    /// Creates and initializes a `BigUint`. Each u8 of the input slice is
2050    /// interpreted as one digit of the number
2051    /// and must therefore be less than `radix`.
2052    ///
2053    /// The bytes are in little-endian byte order.
2054    /// `radix` must be in the range `2...256`.
2055    ///
2056    /// # Examples
2057    ///
2058    /// ```
2059    /// use num_bigint::{BigUint};
2060    ///
2061    /// let inbase190 = &[14, 12, 125, 33, 15];
2062    /// let a = BigUint::from_radix_be(inbase190, 190).unwrap();
2063    /// assert_eq!(a.to_radix_be(190), inbase190);
2064    /// ```
2065    pub fn from_radix_le(buf: &[u8], radix: u32) -> Option<BigUint> {
2066        assert!(
2067            2 <= radix && radix <= 256,
2068            "The radix must be within 2...256"
2069        );
2070
2071        if radix != 256 && buf.iter().any(|&b| b >= radix as u8) {
2072            return None;
2073        }
2074
2075        let res = if radix.is_power_of_two() {
2076            // Powers of two can use bitwise masks and shifting instead of multiplication
2077            let bits = ilog2(radix);
2078            if big_digit::BITS % bits == 0 {
2079                from_bitwise_digits_le(buf, bits)
2080            } else {
2081                from_inexact_bitwise_digits_le(buf, bits)
2082            }
2083        } else {
2084            let mut v = Vec::from(buf);
2085            v.reverse();
2086            from_radix_digits_be(&v, radix)
2087        };
2088
2089        Some(res)
2090    }
2091
2092    /// Returns the byte representation of the `BigUint` in big-endian byte order.
2093    ///
2094    /// # Examples
2095    ///
2096    /// ```
2097    /// use num_bigint::BigUint;
2098    ///
2099    /// let i = BigUint::parse_bytes(b"1125", 10).unwrap();
2100    /// assert_eq!(i.to_bytes_be(), vec![4, 101]);
2101    /// ```
2102    #[inline]
2103    pub fn to_bytes_be(&self) -> Vec<u8> {
2104        let mut v = self.to_bytes_le();
2105        v.reverse();
2106        v
2107    }
2108
2109    /// Returns the byte representation of the `BigUint` in little-endian byte order.
2110    ///
2111    /// # Examples
2112    ///
2113    /// ```
2114    /// use num_bigint::BigUint;
2115    ///
2116    /// let i = BigUint::parse_bytes(b"1125", 10).unwrap();
2117    /// assert_eq!(i.to_bytes_le(), vec![101, 4]);
2118    /// ```
2119    #[inline]
2120    pub fn to_bytes_le(&self) -> Vec<u8> {
2121        if self.is_zero() {
2122            vec![0]
2123        } else {
2124            to_bitwise_digits_le(self, 8)
2125        }
2126    }
2127
2128    /// Returns the `u32` digits representation of the `BigUint` ordered least significant digit
2129    /// first.
2130    ///
2131    /// # Examples
2132    ///
2133    /// ```
2134    /// use num_bigint::BigUint;
2135    ///
2136    /// assert_eq!(BigUint::from(1125u32).to_u32_digits(), vec![1125]);
2137    /// assert_eq!(BigUint::from(4294967295u32).to_u32_digits(), vec![4294967295]);
2138    /// assert_eq!(BigUint::from(4294967296u64).to_u32_digits(), vec![0, 1]);
2139    /// assert_eq!(BigUint::from(112500000000u64).to_u32_digits(), vec![830850304, 26]);
2140    /// ```
2141    #[inline]
2142    pub fn to_u32_digits(&self) -> Vec<u32> {
2143        self.data.clone()
2144    }
2145
2146    /// Returns the integer formatted as a string in the given radix.
2147    /// `radix` must be in the range `2...36`.
2148    ///
2149    /// # Examples
2150    ///
2151    /// ```
2152    /// use num_bigint::BigUint;
2153    ///
2154    /// let i = BigUint::parse_bytes(b"ff", 16).unwrap();
2155    /// assert_eq!(i.to_str_radix(16), "ff");
2156    /// ```
2157    #[inline]
2158    pub fn to_str_radix(&self, radix: u32) -> String {
2159        let mut v = to_str_radix_reversed(self, radix);
2160        v.reverse();
2161        unsafe { String::from_utf8_unchecked(v) }
2162    }
2163
2164    /// Returns the integer in the requested base in big-endian digit order.
2165    /// The output is not given in a human readable alphabet but as a zero
2166    /// based u8 number.
2167    /// `radix` must be in the range `2...256`.
2168    ///
2169    /// # Examples
2170    ///
2171    /// ```
2172    /// use num_bigint::BigUint;
2173    ///
2174    /// assert_eq!(BigUint::from(0xFFFFu64).to_radix_be(159),
2175    ///            vec![2, 94, 27]);
2176    /// // 0xFFFF = 65535 = 2*(159^2) + 94*159 + 27
2177    /// ```
2178    #[inline]
2179    pub fn to_radix_be(&self, radix: u32) -> Vec<u8> {
2180        let mut v = to_radix_le(self, radix);
2181        v.reverse();
2182        v
2183    }
2184
2185    /// Returns the integer in the requested base in little-endian digit order.
2186    /// The output is not given in a human readable alphabet but as a zero
2187    /// based u8 number.
2188    /// `radix` must be in the range `2...256`.
2189    ///
2190    /// # Examples
2191    ///
2192    /// ```
2193    /// use num_bigint::BigUint;
2194    ///
2195    /// assert_eq!(BigUint::from(0xFFFFu64).to_radix_le(159),
2196    ///            vec![27, 94, 2]);
2197    /// // 0xFFFF = 65535 = 27 + 94*159 + 2*(159^2)
2198    /// ```
2199    #[inline]
2200    pub fn to_radix_le(&self, radix: u32) -> Vec<u8> {
2201        to_radix_le(self, radix)
2202    }
2203
2204    /// Determines the fewest bits necessary to express the `BigUint`.
2205    #[inline]
2206    pub fn bits(&self) -> usize {
2207        if self.is_zero() {
2208            return 0;
2209        }
2210        let zeros = self.data.last().unwrap().leading_zeros();
2211        self.data.len() * big_digit::BITS - zeros as usize
2212    }
2213
2214    /// Strips off trailing zero bigdigits - comparisons require the last element in the vector to
2215    /// be nonzero.
2216    #[inline]
2217    fn normalize(&mut self) {
2218        while let Some(&0) = self.data.last() {
2219            self.data.pop();
2220        }
2221    }
2222
2223    /// Returns a normalized `BigUint`.
2224    #[inline]
2225    fn normalized(mut self) -> BigUint {
2226        self.normalize();
2227        self
2228    }
2229
2230    /// Returns `(self ^ exponent) % modulus`.
2231    ///
2232    /// Panics if the modulus is zero.
2233    pub fn modpow(&self, exponent: &Self, modulus: &Self) -> Self {
2234        assert!(!modulus.is_zero(), "divide by zero!");
2235
2236        if modulus.is_odd() {
2237            // For an odd modulus, we can use Montgomery multiplication in base 2^32.
2238            monty_modpow(self, exponent, modulus)
2239        } else {
2240            // Otherwise do basically the same as `num::pow`, but with a modulus.
2241            plain_modpow(self, &exponent.data, modulus)
2242        }
2243    }
2244
2245    /// Returns the truncated principal square root of `self` --
2246    /// see [Roots::sqrt](https://docs.rs/num-integer/0.1/num_integer/trait.Roots.html#method.sqrt)
2247    pub fn sqrt(&self) -> Self {
2248        Roots::sqrt(self)
2249    }
2250
2251    /// Returns the truncated principal cube root of `self` --
2252    /// see [Roots::cbrt](https://docs.rs/num-integer/0.1/num_integer/trait.Roots.html#method.cbrt).
2253    pub fn cbrt(&self) -> Self {
2254        Roots::cbrt(self)
2255    }
2256
2257    /// Returns the truncated principal `n`th root of `self` --
2258    /// see [Roots::nth_root](https://docs.rs/num-integer/0.1/num_integer/trait.Roots.html#tymethod.nth_root).
2259    pub fn nth_root(&self, n: u32) -> Self {
2260        Roots::nth_root(self, n)
2261    }
2262}
2263
2264fn plain_modpow(base: &BigUint, exp_data: &[BigDigit], modulus: &BigUint) -> BigUint {
2265    assert!(!modulus.is_zero(), "divide by zero!");
2266
2267    let i = match exp_data.iter().position(|&r| r != 0) {
2268        None => return BigUint::one(),
2269        Some(i) => i,
2270    };
2271
2272    let mut base = base % modulus;
2273    for _ in 0..i {
2274        for _ in 0..big_digit::BITS {
2275            base = &base * &base % modulus;
2276        }
2277    }
2278
2279    let mut r = exp_data[i];
2280    let mut b = 0usize;
2281    while r.is_even() {
2282        base = &base * &base % modulus;
2283        r >>= 1;
2284        b += 1;
2285    }
2286
2287    let mut exp_iter = exp_data[i + 1..].iter();
2288    if exp_iter.len() == 0 && r.is_one() {
2289        return base;
2290    }
2291
2292    let mut acc = base.clone();
2293    r >>= 1;
2294    b += 1;
2295
2296    {
2297        let mut unit = |exp_is_odd| {
2298            base = &base * &base % modulus;
2299            if exp_is_odd {
2300                acc = &acc * &base % modulus;
2301            }
2302        };
2303
2304        if let Some(&last) = exp_iter.next_back() {
2305            // consume exp_data[i]
2306            for _ in b..big_digit::BITS {
2307                unit(r.is_odd());
2308                r >>= 1;
2309            }
2310
2311            // consume all other digits before the last
2312            for &r in exp_iter {
2313                let mut r = r;
2314                for _ in 0..big_digit::BITS {
2315                    unit(r.is_odd());
2316                    r >>= 1;
2317                }
2318            }
2319            r = last;
2320        }
2321
2322        debug_assert_ne!(r, 0);
2323        while !r.is_zero() {
2324            unit(r.is_odd());
2325            r >>= 1;
2326        }
2327    }
2328    acc
2329}
2330
2331#[test]
2332fn test_plain_modpow() {
2333    let two = BigUint::from(2u32);
2334    let modulus = BigUint::from(0x1100u32);
2335
2336    let exp = vec![0, 0b1];
2337    assert_eq!(
2338        two.pow(0b1_00000000_u32) % &modulus,
2339        plain_modpow(&two, &exp, &modulus)
2340    );
2341    let exp = vec![0, 0b10];
2342    assert_eq!(
2343        two.pow(0b10_00000000_u32) % &modulus,
2344        plain_modpow(&two, &exp, &modulus)
2345    );
2346    let exp = vec![0, 0b110010];
2347    assert_eq!(
2348        two.pow(0b110010_00000000_u32) % &modulus,
2349        plain_modpow(&two, &exp, &modulus)
2350    );
2351    let exp = vec![0b1, 0b1];
2352    assert_eq!(
2353        two.pow(0b1_00000001_u32) % &modulus,
2354        plain_modpow(&two, &exp, &modulus)
2355    );
2356    let exp = vec![0b1100, 0, 0b1];
2357    assert_eq!(
2358        two.pow(0b1_00000000_00001100_u32) % &modulus,
2359        plain_modpow(&two, &exp, &modulus)
2360    );
2361}
2362
2363/// Returns the number of least-significant bits that are zero,
2364/// or `None` if the entire number is zero.
2365pub fn trailing_zeros(u: &BigUint) -> Option<usize> {
2366    u.data
2367        .iter()
2368        .enumerate()
2369        .find(|&(_, &digit)| digit != 0)
2370        .map(|(i, digit)| i * big_digit::BITS + digit.trailing_zeros() as usize)
2371}
2372
2373impl_sum_iter_type!(BigUint);
2374impl_product_iter_type!(BigUint);
2375
2376pub trait IntDigits {
2377    fn digits(&self) -> &[BigDigit];
2378    fn digits_mut(&mut self) -> &mut Vec<BigDigit>;
2379    fn normalize(&mut self);
2380    fn capacity(&self) -> usize;
2381    fn len(&self) -> usize;
2382}
2383
2384impl IntDigits for BigUint {
2385    #[inline]
2386    fn digits(&self) -> &[BigDigit] {
2387        &self.data
2388    }
2389    #[inline]
2390    fn digits_mut(&mut self) -> &mut Vec<BigDigit> {
2391        &mut self.data
2392    }
2393    #[inline]
2394    fn normalize(&mut self) {
2395        self.normalize();
2396    }
2397    #[inline]
2398    fn capacity(&self) -> usize {
2399        self.data.capacity()
2400    }
2401    #[inline]
2402    fn len(&self) -> usize {
2403        self.data.len()
2404    }
2405}
2406
2407/// Combine four `u32`s into a single `u128`.
2408#[cfg(has_i128)]
2409#[inline]
2410fn u32_to_u128(a: u32, b: u32, c: u32, d: u32) -> u128 {
2411    u128::from(d) | (u128::from(c) << 32) | (u128::from(b) << 64) | (u128::from(a) << 96)
2412}
2413
2414/// Split a single `u128` into four `u32`.
2415#[cfg(has_i128)]
2416#[inline]
2417fn u32_from_u128(n: u128) -> (u32, u32, u32, u32) {
2418    (
2419        (n >> 96) as u32,
2420        (n >> 64) as u32,
2421        (n >> 32) as u32,
2422        n as u32,
2423    )
2424}
2425
2426#[cfg(feature = "serde")]
2427impl serde::Serialize for BigUint {
2428    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
2429    where
2430        S: serde::Serializer,
2431    {
2432        // Note: do not change the serialization format, or it may break forward
2433        // and backward compatibility of serialized data!  If we ever change the
2434        // internal representation, we should still serialize in base-`u32`.
2435        let data: &Vec<u32> = &self.data;
2436        data.serialize(serializer)
2437    }
2438}
2439
2440#[cfg(feature = "serde")]
2441impl<'de> serde::Deserialize<'de> for BigUint {
2442    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
2443    where
2444        D: serde::Deserializer<'de>,
2445    {
2446        let data: Vec<u32> = Vec::deserialize(deserializer)?;
2447        Ok(BigUint::new(data))
2448    }
2449}
2450
2451/// Returns the greatest power of the radix <= big_digit::BASE
2452#[inline]
2453fn get_radix_base(radix: u32) -> (BigDigit, usize) {
2454    debug_assert!(
2455        2 <= radix && radix <= 256,
2456        "The radix must be within 2...256"
2457    );
2458    debug_assert!(!radix.is_power_of_two());
2459
2460    // To generate this table:
2461    //    for radix in 2u64..257 {
2462    //        let mut power = big_digit::BITS / fls(radix as u64);
2463    //        let mut base = radix.pow(power as u32);
2464    //
2465    //        while let Some(b) = base.checked_mul(radix) {
2466    //            if b > big_digit::MAX {
2467    //                break;
2468    //            }
2469    //            base = b;
2470    //            power += 1;
2471    //        }
2472    //
2473    //        println!("({:10}, {:2}), // {:2}", base, power, radix);
2474    //    }
2475    // and
2476    //    for radix in 2u64..257 {
2477    //        let mut power = 64 / fls(radix as u64);
2478    //        let mut base = radix.pow(power as u32);
2479    //
2480    //        while let Some(b) = base.checked_mul(radix) {
2481    //            base = b;
2482    //            power += 1;
2483    //        }
2484    //
2485    //        println!("({:20}, {:2}), // {:2}", base, power, radix);
2486    //    }
2487    match big_digit::BITS {
2488        32 => {
2489            const BASES: [(u32, usize); 257] = [
2490                (0, 0),
2491                (0, 0),
2492                (0, 0),           //  2
2493                (3486784401, 20), //  3
2494                (0, 0),           //  4
2495                (1220703125, 13), //  5
2496                (2176782336, 12), //  6
2497                (1977326743, 11), //  7
2498                (0, 0),           //  8
2499                (3486784401, 10), //  9
2500                (1000000000, 9),  // 10
2501                (2357947691, 9),  // 11
2502                (429981696, 8),   // 12
2503                (815730721, 8),   // 13
2504                (1475789056, 8),  // 14
2505                (2562890625, 8),  // 15
2506                (0, 0),           // 16
2507                (410338673, 7),   // 17
2508                (612220032, 7),   // 18
2509                (893871739, 7),   // 19
2510                (1280000000, 7),  // 20
2511                (1801088541, 7),  // 21
2512                (2494357888, 7),  // 22
2513                (3404825447, 7),  // 23
2514                (191102976, 6),   // 24
2515                (244140625, 6),   // 25
2516                (308915776, 6),   // 26
2517                (387420489, 6),   // 27
2518                (481890304, 6),   // 28
2519                (594823321, 6),   // 29
2520                (729000000, 6),   // 30
2521                (887503681, 6),   // 31
2522                (0, 0),           // 32
2523                (1291467969, 6),  // 33
2524                (1544804416, 6),  // 34
2525                (1838265625, 6),  // 35
2526                (2176782336, 6),  // 36
2527                (2565726409, 6),  // 37
2528                (3010936384, 6),  // 38
2529                (3518743761, 6),  // 39
2530                (4096000000, 6),  // 40
2531                (115856201, 5),   // 41
2532                (130691232, 5),   // 42
2533                (147008443, 5),   // 43
2534                (164916224, 5),   // 44
2535                (184528125, 5),   // 45
2536                (205962976, 5),   // 46
2537                (229345007, 5),   // 47
2538                (254803968, 5),   // 48
2539                (282475249, 5),   // 49
2540                (312500000, 5),   // 50
2541                (345025251, 5),   // 51
2542                (380204032, 5),   // 52
2543                (418195493, 5),   // 53
2544                (459165024, 5),   // 54
2545                (503284375, 5),   // 55
2546                (550731776, 5),   // 56
2547                (601692057, 5),   // 57
2548                (656356768, 5),   // 58
2549                (714924299, 5),   // 59
2550                (777600000, 5),   // 60
2551                (844596301, 5),   // 61
2552                (916132832, 5),   // 62
2553                (992436543, 5),   // 63
2554                (0, 0),           // 64
2555                (1160290625, 5),  // 65
2556                (1252332576, 5),  // 66
2557                (1350125107, 5),  // 67
2558                (1453933568, 5),  // 68
2559                (1564031349, 5),  // 69
2560                (1680700000, 5),  // 70
2561                (1804229351, 5),  // 71
2562                (1934917632, 5),  // 72
2563                (2073071593, 5),  // 73
2564                (2219006624, 5),  // 74
2565                (2373046875, 5),  // 75
2566                (2535525376, 5),  // 76
2567                (2706784157, 5),  // 77
2568                (2887174368, 5),  // 78
2569                (3077056399, 5),  // 79
2570                (3276800000, 5),  // 80
2571                (3486784401, 5),  // 81
2572                (3707398432, 5),  // 82
2573                (3939040643, 5),  // 83
2574                (4182119424, 5),  // 84
2575                (52200625, 4),    // 85
2576                (54700816, 4),    // 86
2577                (57289761, 4),    // 87
2578                (59969536, 4),    // 88
2579                (62742241, 4),    // 89
2580                (65610000, 4),    // 90
2581                (68574961, 4),    // 91
2582                (71639296, 4),    // 92
2583                (74805201, 4),    // 93
2584                (78074896, 4),    // 94
2585                (81450625, 4),    // 95
2586                (84934656, 4),    // 96
2587                (88529281, 4),    // 97
2588                (92236816, 4),    // 98
2589                (96059601, 4),    // 99
2590                (100000000, 4),   // 100
2591                (104060401, 4),   // 101
2592                (108243216, 4),   // 102
2593                (112550881, 4),   // 103
2594                (116985856, 4),   // 104
2595                (121550625, 4),   // 105
2596                (126247696, 4),   // 106
2597                (131079601, 4),   // 107
2598                (136048896, 4),   // 108
2599                (141158161, 4),   // 109
2600                (146410000, 4),   // 110
2601                (151807041, 4),   // 111
2602                (157351936, 4),   // 112
2603                (163047361, 4),   // 113
2604                (168896016, 4),   // 114
2605                (174900625, 4),   // 115
2606                (181063936, 4),   // 116
2607                (187388721, 4),   // 117
2608                (193877776, 4),   // 118
2609                (200533921, 4),   // 119
2610                (207360000, 4),   // 120
2611                (214358881, 4),   // 121
2612                (221533456, 4),   // 122
2613                (228886641, 4),   // 123
2614                (236421376, 4),   // 124
2615                (244140625, 4),   // 125
2616                (252047376, 4),   // 126
2617                (260144641, 4),   // 127
2618                (0, 0),           // 128
2619                (276922881, 4),   // 129
2620                (285610000, 4),   // 130
2621                (294499921, 4),   // 131
2622                (303595776, 4),   // 132
2623                (312900721, 4),   // 133
2624                (322417936, 4),   // 134
2625                (332150625, 4),   // 135
2626                (342102016, 4),   // 136
2627                (352275361, 4),   // 137
2628                (362673936, 4),   // 138
2629                (373301041, 4),   // 139
2630                (384160000, 4),   // 140
2631                (395254161, 4),   // 141
2632                (406586896, 4),   // 142
2633                (418161601, 4),   // 143
2634                (429981696, 4),   // 144
2635                (442050625, 4),   // 145
2636                (454371856, 4),   // 146
2637                (466948881, 4),   // 147
2638                (479785216, 4),   // 148
2639                (492884401, 4),   // 149
2640                (506250000, 4),   // 150
2641                (519885601, 4),   // 151
2642                (533794816, 4),   // 152
2643                (547981281, 4),   // 153
2644                (562448656, 4),   // 154
2645                (577200625, 4),   // 155
2646                (592240896, 4),   // 156
2647                (607573201, 4),   // 157
2648                (623201296, 4),   // 158
2649                (639128961, 4),   // 159
2650                (655360000, 4),   // 160
2651                (671898241, 4),   // 161
2652                (688747536, 4),   // 162
2653                (705911761, 4),   // 163
2654                (723394816, 4),   // 164
2655                (741200625, 4),   // 165
2656                (759333136, 4),   // 166
2657                (777796321, 4),   // 167
2658                (796594176, 4),   // 168
2659                (815730721, 4),   // 169
2660                (835210000, 4),   // 170
2661                (855036081, 4),   // 171
2662                (875213056, 4),   // 172
2663                (895745041, 4),   // 173
2664                (916636176, 4),   // 174
2665                (937890625, 4),   // 175
2666                (959512576, 4),   // 176
2667                (981506241, 4),   // 177
2668                (1003875856, 4),  // 178
2669                (1026625681, 4),  // 179
2670                (1049760000, 4),  // 180
2671                (1073283121, 4),  // 181
2672                (1097199376, 4),  // 182
2673                (1121513121, 4),  // 183
2674                (1146228736, 4),  // 184
2675                (1171350625, 4),  // 185
2676                (1196883216, 4),  // 186
2677                (1222830961, 4),  // 187
2678                (1249198336, 4),  // 188
2679                (1275989841, 4),  // 189
2680                (1303210000, 4),  // 190
2681                (1330863361, 4),  // 191
2682                (1358954496, 4),  // 192
2683                (1387488001, 4),  // 193
2684                (1416468496, 4),  // 194
2685                (1445900625, 4),  // 195
2686                (1475789056, 4),  // 196
2687                (1506138481, 4),  // 197
2688                (1536953616, 4),  // 198
2689                (1568239201, 4),  // 199
2690                (1600000000, 4),  // 200
2691                (1632240801, 4),  // 201
2692                (1664966416, 4),  // 202
2693                (1698181681, 4),  // 203
2694                (1731891456, 4),  // 204
2695                (1766100625, 4),  // 205
2696                (1800814096, 4),  // 206
2697                (1836036801, 4),  // 207
2698                (1871773696, 4),  // 208
2699                (1908029761, 4),  // 209
2700                (1944810000, 4),  // 210
2701                (1982119441, 4),  // 211
2702                (2019963136, 4),  // 212
2703                (2058346161, 4),  // 213
2704                (2097273616, 4),  // 214
2705                (2136750625, 4),  // 215
2706                (2176782336, 4),  // 216
2707                (2217373921, 4),  // 217
2708                (2258530576, 4),  // 218
2709                (2300257521, 4),  // 219
2710                (2342560000, 4),  // 220
2711                (2385443281, 4),  // 221
2712                (2428912656, 4),  // 222
2713                (2472973441, 4),  // 223
2714                (2517630976, 4),  // 224
2715                (2562890625, 4),  // 225
2716                (2608757776, 4),  // 226
2717                (2655237841, 4),  // 227
2718                (2702336256, 4),  // 228
2719                (2750058481, 4),  // 229
2720                (2798410000, 4),  // 230
2721                (2847396321, 4),  // 231
2722                (2897022976, 4),  // 232
2723                (2947295521, 4),  // 233
2724                (2998219536, 4),  // 234
2725                (3049800625, 4),  // 235
2726                (3102044416, 4),  // 236
2727                (3154956561, 4),  // 237
2728                (3208542736, 4),  // 238
2729                (3262808641, 4),  // 239
2730                (3317760000, 4),  // 240
2731                (3373402561, 4),  // 241
2732                (3429742096, 4),  // 242
2733                (3486784401, 4),  // 243
2734                (3544535296, 4),  // 244
2735                (3603000625, 4),  // 245
2736                (3662186256, 4),  // 246
2737                (3722098081, 4),  // 247
2738                (3782742016, 4),  // 248
2739                (3844124001, 4),  // 249
2740                (3906250000, 4),  // 250
2741                (3969126001, 4),  // 251
2742                (4032758016, 4),  // 252
2743                (4097152081, 4),  // 253
2744                (4162314256, 4),  // 254
2745                (4228250625, 4),  // 255
2746                (0, 0),           // 256
2747            ];
2748
2749            let (base, power) = BASES[radix as usize];
2750            (base as BigDigit, power)
2751        }
2752        64 => {
2753            const BASES: [(u64, usize); 257] = [
2754                (0, 0),
2755                (0, 0),
2756                (9223372036854775808, 63),  //  2
2757                (12157665459056928801, 40), //  3
2758                (4611686018427387904, 31),  //  4
2759                (7450580596923828125, 27),  //  5
2760                (4738381338321616896, 24),  //  6
2761                (3909821048582988049, 22),  //  7
2762                (9223372036854775808, 21),  //  8
2763                (12157665459056928801, 20), //  9
2764                (10000000000000000000, 19), // 10
2765                (5559917313492231481, 18),  // 11
2766                (2218611106740436992, 17),  // 12
2767                (8650415919381337933, 17),  // 13
2768                (2177953337809371136, 16),  // 14
2769                (6568408355712890625, 16),  // 15
2770                (1152921504606846976, 15),  // 16
2771                (2862423051509815793, 15),  // 17
2772                (6746640616477458432, 15),  // 18
2773                (15181127029874798299, 15), // 19
2774                (1638400000000000000, 14),  // 20
2775                (3243919932521508681, 14),  // 21
2776                (6221821273427820544, 14),  // 22
2777                (11592836324538749809, 14), // 23
2778                (876488338465357824, 13),   // 24
2779                (1490116119384765625, 13),  // 25
2780                (2481152873203736576, 13),  // 26
2781                (4052555153018976267, 13),  // 27
2782                (6502111422497947648, 13),  // 28
2783                (10260628712958602189, 13), // 29
2784                (15943230000000000000, 13), // 30
2785                (787662783788549761, 12),   // 31
2786                (1152921504606846976, 12),  // 32
2787                (1667889514952984961, 12),  // 33
2788                (2386420683693101056, 12),  // 34
2789                (3379220508056640625, 12),  // 35
2790                (4738381338321616896, 12),  // 36
2791                (6582952005840035281, 12),  // 37
2792                (9065737908494995456, 12),  // 38
2793                (12381557655576425121, 12), // 39
2794                (16777216000000000000, 12), // 40
2795                (550329031716248441, 11),   // 41
2796                (717368321110468608, 11),   // 42
2797                (929293739471222707, 11),   // 43
2798                (1196683881290399744, 11),  // 44
2799                (1532278301220703125, 11),  // 45
2800                (1951354384207722496, 11),  // 46
2801                (2472159215084012303, 11),  // 47
2802                (3116402981210161152, 11),  // 48
2803                (3909821048582988049, 11),  // 49
2804                (4882812500000000000, 11),  // 50
2805                (6071163615208263051, 11),  // 51
2806                (7516865509350965248, 11),  // 52
2807                (9269035929372191597, 11),  // 53
2808                (11384956040305711104, 11), // 54
2809                (13931233916552734375, 11), // 55
2810                (16985107389382393856, 11), // 56
2811                (362033331456891249, 10),   // 57
2812                (430804206899405824, 10),   // 58
2813                (511116753300641401, 10),   // 59
2814                (604661760000000000, 10),   // 60
2815                (713342911662882601, 10),   // 61
2816                (839299365868340224, 10),   // 62
2817                (984930291881790849, 10),   // 63
2818                (1152921504606846976, 10),  // 64
2819                (1346274334462890625, 10),  // 65
2820                (1568336880910795776, 10),  // 66
2821                (1822837804551761449, 10),  // 67
2822                (2113922820157210624, 10),  // 68
2823                (2446194060654759801, 10),  // 69
2824                (2824752490000000000, 10),  // 70
2825                (3255243551009881201, 10),  // 71
2826                (3743906242624487424, 10),  // 72
2827                (4297625829703557649, 10),  // 73
2828                (4923990397355877376, 10),  // 74
2829                (5631351470947265625, 10),  // 75
2830                (6428888932339941376, 10),  // 76
2831                (7326680472586200649, 10),  // 77
2832                (8335775831236199424, 10),  // 78
2833                (9468276082626847201, 10),  // 79
2834                (10737418240000000000, 10), // 80
2835                (12157665459056928801, 10), // 81
2836                (13744803133596058624, 10), // 82
2837                (15516041187205853449, 10), // 83
2838                (17490122876598091776, 10), // 84
2839                (231616946283203125, 9),    // 85
2840                (257327417311663616, 9),    // 86
2841                (285544154243029527, 9),    // 87
2842                (316478381828866048, 9),    // 88
2843                (350356403707485209, 9),    // 89
2844                (387420489000000000, 9),    // 90
2845                (427929800129788411, 9),    // 91
2846                (472161363286556672, 9),    // 92
2847                (520411082988487293, 9),    // 93
2848                (572994802228616704, 9),    // 94
2849                (630249409724609375, 9),    // 95
2850                (692533995824480256, 9),    // 96
2851                (760231058654565217, 9),    // 97
2852                (833747762130149888, 9),    // 98
2853                (913517247483640899, 9),    // 99
2854                (1000000000000000000, 9),   // 100
2855                (1093685272684360901, 9),   // 101
2856                (1195092568622310912, 9),   // 102
2857                (1304773183829244583, 9),   // 103
2858                (1423311812421484544, 9),   // 104
2859                (1551328215978515625, 9),   // 105
2860                (1689478959002692096, 9),   // 106
2861                (1838459212420154507, 9),   // 107
2862                (1999004627104432128, 9),   // 108
2863                (2171893279442309389, 9),   // 109
2864                (2357947691000000000, 9),   // 110
2865                (2558036924386500591, 9),   // 111
2866                (2773078757450186752, 9),   // 112
2867                (3004041937984268273, 9),   // 113
2868                (3251948521156637184, 9),   // 114
2869                (3517876291919921875, 9),   // 115
2870                (3802961274698203136, 9),   // 116
2871                (4108400332687853397, 9),   // 117
2872                (4435453859151328768, 9),   // 118
2873                (4785448563124474679, 9),   // 119
2874                (5159780352000000000, 9),   // 120
2875                (5559917313492231481, 9),   // 121
2876                (5987402799531080192, 9),   // 122
2877                (6443858614676334363, 9),   // 123
2878                (6930988311686938624, 9),   // 124
2879                (7450580596923828125, 9),   // 125
2880                (8004512848309157376, 9),   // 126
2881                (8594754748609397887, 9),   // 127
2882                (9223372036854775808, 9),   // 128
2883                (9892530380752880769, 9),   // 129
2884                (10604499373000000000, 9),  // 130
2885                (11361656654439817571, 9),  // 131
2886                (12166492167065567232, 9),  // 132
2887                (13021612539908538853, 9),  // 133
2888                (13929745610903012864, 9),  // 134
2889                (14893745087865234375, 9),  // 135
2890                (15916595351771938816, 9),  // 136
2891                (17001416405572203977, 9),  // 137
2892                (18151468971815029248, 9),  // 138
2893                (139353667211683681, 8),    // 139
2894                (147578905600000000, 8),    // 140
2895                (156225851787813921, 8),    // 141
2896                (165312903998914816, 8),    // 142
2897                (174859124550883201, 8),    // 143
2898                (184884258895036416, 8),    // 144
2899                (195408755062890625, 8),    // 145
2900                (206453783524884736, 8),    // 146
2901                (218041257467152161, 8),    // 147
2902                (230193853492166656, 8),    // 148
2903                (242935032749128801, 8),    // 149
2904                (256289062500000000, 8),    // 150
2905                (270281038127131201, 8),    // 151
2906                (284936905588473856, 8),    // 152
2907                (300283484326400961, 8),    // 153
2908                (316348490636206336, 8),    // 154
2909                (333160561500390625, 8),    // 155
2910                (350749278894882816, 8),    // 156
2911                (369145194573386401, 8),    // 157
2912                (388379855336079616, 8),    // 158
2913                (408485828788939521, 8),    // 159
2914                (429496729600000000, 8),    // 160
2915                (451447246258894081, 8),    // 161
2916                (474373168346071296, 8),    // 162
2917                (498311414318121121, 8),    // 163
2918                (523300059815673856, 8),    // 164
2919                (549378366500390625, 8),    // 165
2920                (576586811427594496, 8),    // 166
2921                (604967116961135041, 8),    // 167
2922                (634562281237118976, 8),    // 168
2923                (665416609183179841, 8),    // 169
2924                (697575744100000000, 8),    // 170
2925                (731086699811838561, 8),    // 171
2926                (765997893392859136, 8),    // 172
2927                (802359178476091681, 8),    // 173
2928                (840221879151902976, 8),    // 174
2929                (879638824462890625, 8),    // 175
2930                (920664383502155776, 8),    // 176
2931                (963354501121950081, 8),    // 177
2932                (1007766734259732736, 8),   // 178
2933                (1053960288888713761, 8),   // 179
2934                (1101996057600000000, 8),   // 180
2935                (1151936657823500641, 8),   // 181
2936                (1203846470694789376, 8),   // 182
2937                (1257791680575160641, 8),   // 183
2938                (1313840315232157696, 8),   // 184
2939                (1372062286687890625, 8),   // 185
2940                (1432529432742502656, 8),   // 186
2941                (1495315559180183521, 8),   // 187
2942                (1560496482665168896, 8),   // 188
2943                (1628150074335205281, 8),   // 189
2944                (1698356304100000000, 8),   // 190
2945                (1771197285652216321, 8),   // 191
2946                (1846757322198614016, 8),   // 192
2947                (1925122952918976001, 8),   // 193
2948                (2006383000160502016, 8),   // 194
2949                (2090628617375390625, 8),   // 195
2950                (2177953337809371136, 8),   // 196
2951                (2268453123948987361, 8),   // 197
2952                (2362226417735475456, 8),   // 198
2953                (2459374191553118401, 8),   // 199
2954                (2560000000000000000, 8),   // 200
2955                (2664210032449121601, 8),   // 201
2956                (2772113166407885056, 8),   // 202
2957                (2883821021683985761, 8),   // 203
2958                (2999448015365799936, 8),   // 204
2959                (3119111417625390625, 8),   // 205
2960                (3242931408352297216, 8),   // 206
2961                (3371031134626313601, 8),   // 207
2962                (3503536769037500416, 8),   // 208
2963                (3640577568861717121, 8),   // 209
2964                (3782285936100000000, 8),   // 210
2965                (3928797478390152481, 8),   // 211
2966                (4080251070798954496, 8),   // 212
2967                (4236788918503437921, 8),   // 213
2968                (4398556620369715456, 8),   // 214
2969                (4565703233437890625, 8),   // 215
2970                (4738381338321616896, 8),   // 216
2971                (4916747105530914241, 8),   // 217
2972                (5100960362726891776, 8),   // 218
2973                (5291184662917065441, 8),   // 219
2974                (5487587353600000000, 8),   // 220
2975                (5690339646868044961, 8),   // 221
2976                (5899616690476974336, 8),   // 222
2977                (6115597639891380481, 8),   // 223
2978                (6338465731314712576, 8),   // 224
2979                (6568408355712890625, 8),   // 225
2980                (6805617133840466176, 8),   // 226
2981                (7050287992278341281, 8),   // 227
2982                (7302621240492097536, 8),   // 228
2983                (7562821648920027361, 8),   // 229
2984                (7831098528100000000, 8),   // 230
2985                (8107665808844335041, 8),   // 231
2986                (8392742123471896576, 8),   // 232
2987                (8686550888106661441, 8),   // 233
2988                (8989320386052055296, 8),   // 234
2989                (9301283852250390625, 8),   // 235
2990                (9622679558836781056, 8),   // 236
2991                (9953750901796946721, 8),   // 237
2992                (10294746488738365696, 8),  // 238
2993                (10645920227784266881, 8),  // 239
2994                (11007531417600000000, 8),  // 240
2995                (11379844838561358721, 8),  // 241
2996                (11763130845074473216, 8),  // 242
2997                (12157665459056928801, 8),  // 243
2998                (12563730464589807616, 8),  // 244
2999                (12981613503750390625, 8),  // 245
3000                (13411608173635297536, 8),  // 246
3001                (13854014124583882561, 8),  // 247
3002                (14309137159611744256, 8),  // 248
3003                (14777289335064248001, 8),  // 249
3004                (15258789062500000000, 8),  // 250
3005                (15753961211814252001, 8),  // 251
3006                (16263137215612256256, 8),  // 252
3007                (16786655174842630561, 8),  // 253
3008                (17324859965700833536, 8),  // 254
3009                (17878103347812890625, 8),  // 255
3010                (72057594037927936, 7),     // 256
3011            ];
3012
3013            let (base, power) = BASES[radix as usize];
3014            (base as BigDigit, power)
3015        }
3016        _ => panic!("Invalid bigdigit size"),
3017    }
3018}
3019
3020#[test]
3021fn test_from_slice() {
3022    fn check(slice: &[BigDigit], data: &[BigDigit]) {
3023        assert!(BigUint::from_slice(slice).data == data);
3024    }
3025    check(&[1], &[1]);
3026    check(&[0, 0, 0], &[]);
3027    check(&[1, 2, 0, 0], &[1, 2]);
3028    check(&[0, 0, 1, 2], &[0, 0, 1, 2]);
3029    check(&[0, 0, 1, 2, 0, 0], &[0, 0, 1, 2]);
3030    check(&[-1i32 as BigDigit], &[-1i32 as BigDigit]);
3031}
3032
3033#[test]
3034fn test_assign_from_slice() {
3035    fn check(slice: &[BigDigit], data: &[BigDigit]) {
3036        let mut p = BigUint::from_slice(&[2627_u32, 0_u32, 9182_u32, 42_u32]);
3037        p.assign_from_slice(slice);
3038        assert!(p.data == data);
3039    }
3040    check(&[1], &[1]);
3041    check(&[0, 0, 0], &[]);
3042    check(&[1, 2, 0, 0], &[1, 2]);
3043    check(&[0, 0, 1, 2], &[0, 0, 1, 2]);
3044    check(&[0, 0, 1, 2, 0, 0], &[0, 0, 1, 2]);
3045    check(&[-1i32 as BigDigit], &[-1i32 as BigDigit]);
3046}
3047
3048#[cfg(has_i128)]
3049#[test]
3050fn test_u32_u128() {
3051    assert_eq!(u32_from_u128(0u128), (0, 0, 0, 0));
3052    assert_eq!(
3053        u32_from_u128(u128::max_value()),
3054        (
3055            u32::max_value(),
3056            u32::max_value(),
3057            u32::max_value(),
3058            u32::max_value()
3059        )
3060    );
3061
3062    assert_eq!(
3063        u32_from_u128(u32::max_value() as u128),
3064        (0, 0, 0, u32::max_value())
3065    );
3066
3067    assert_eq!(
3068        u32_from_u128(u64::max_value() as u128),
3069        (0, 0, u32::max_value(), u32::max_value())
3070    );
3071
3072    assert_eq!(
3073        u32_from_u128((u64::max_value() as u128) + u32::max_value() as u128),
3074        (0, 1, 0, u32::max_value() - 1)
3075    );
3076
3077    assert_eq!(u32_from_u128(36_893_488_151_714_070_528), (0, 2, 1, 0));
3078}
3079
3080#[cfg(has_i128)]
3081#[test]
3082fn test_u128_u32_roundtrip() {
3083    // roundtrips
3084    let values = vec![
3085        0u128,
3086        1u128,
3087        u64::max_value() as u128 * 3,
3088        u32::max_value() as u128,
3089        u64::max_value() as u128,
3090        (u64::max_value() as u128) + u32::max_value() as u128,
3091        u128::max_value(),
3092    ];
3093
3094    for val in &values {
3095        let (a, b, c, d) = u32_from_u128(*val);
3096        assert_eq!(u32_to_u128(a, b, c, d), *val);
3097    }
3098}
3099
3100#[test]
3101fn test_pow_biguint() {
3102    let base = BigUint::from(5u8);
3103    let exponent = BigUint::from(3u8);
3104
3105    assert_eq!(BigUint::from(125u8), base.pow(exponent));
3106}