1 #[allow(deprecated, unused_imports)]
2 use std::ascii::AsciiExt;
3 use std::borrow::Cow;
4 use std::cmp;
5 use std::cmp::Ordering::{self, Equal, Greater, Less};
6 use std::default::Default;
7 use std::fmt;
8 use std::iter::{Product, Sum};
9 use std::mem;
10 use 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 };
14 use std::str::{self, FromStr};
15 use std::{f32, f64};
16 use std::{u64, u8};
17 
18 #[cfg(feature = "serde")]
19 use serde;
20 
21 use integer::{Integer, Roots};
22 use traits::{
23     CheckedAdd, CheckedDiv, CheckedMul, CheckedSub, Float, FromPrimitive, Num, One, Pow,
24     ToPrimitive, Unsigned, Zero,
25 };
26 
27 use big_digit::{self, BigDigit};
28 
29 #[path = "algorithms.rs"]
30 mod algorithms;
31 #[path = "monty.rs"]
32 mod monty;
33 
34 use self::algorithms::{__add2, __sub2rev, add2, sub2, sub2rev};
35 use self::algorithms::{biguint_shl, biguint_shr};
36 use self::algorithms::{cmp_slice, fls, ilog2};
37 use self::algorithms::{div_rem, div_rem_digit, div_rem_ref, rem_digit};
38 use self::algorithms::{mac_with_carry, mul3, scalar_mul};
39 use self::monty::monty_modpow;
40 
41 use UsizePromotion;
42 
43 use ParseBigIntError;
44 
45 #[cfg(feature = "quickcheck")]
46 use quickcheck::{Arbitrary, Gen};
47 
48 /// A big unsigned integer type.
49 #[derive(Clone, Debug, Hash)]
50 pub struct BigUint {
51     data: Vec<BigDigit>,
52 }
53 
54 #[cfg(feature = "quickcheck")]
55 impl Arbitrary for BigUint {
arbitrary<G: Gen>(g: &mut G) -> Self56     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
shrink(&self) -> Box<Iterator<Item = Self>>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 
68 impl PartialEq for BigUint {
69     #[inline]
eq(&self, other: &BigUint) -> bool70     fn eq(&self, other: &BigUint) -> bool {
71         match self.cmp(other) {
72             Equal => true,
73             _ => false,
74         }
75     }
76 }
77 impl Eq for BigUint {}
78 
79 impl PartialOrd for BigUint {
80     #[inline]
partial_cmp(&self, other: &BigUint) -> Option<Ordering>81     fn partial_cmp(&self, other: &BigUint) -> Option<Ordering> {
82         Some(self.cmp(other))
83     }
84 }
85 
86 impl Ord for BigUint {
87     #[inline]
cmp(&self, other: &BigUint) -> Ordering88     fn cmp(&self, other: &BigUint) -> Ordering {
89         cmp_slice(&self.data[..], &other.data[..])
90     }
91 }
92 
93 impl Default for BigUint {
94     #[inline]
default() -> BigUint95     fn default() -> BigUint {
96         Zero::zero()
97     }
98 }
99 
100 impl fmt::Display for BigUint {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result101     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
102         f.pad_integral(true, "", &self.to_str_radix(10))
103     }
104 }
105 
106 impl fmt::LowerHex for BigUint {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result107     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
108         f.pad_integral(true, "0x", &self.to_str_radix(16))
109     }
110 }
111 
112 impl fmt::UpperHex for BigUint {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result113     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 
120 impl fmt::Binary for BigUint {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result121     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
122         f.pad_integral(true, "0b", &self.to_str_radix(2))
123     }
124 }
125 
126 impl fmt::Octal for BigUint {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result127     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
128         f.pad_integral(true, "0o", &self.to_str_radix(8))
129     }
130 }
131 
132 impl FromStr for BigUint {
133     type Err = ParseBigIntError;
134 
135     #[inline]
from_str(s: &str) -> Result<BigUint, ParseBigIntError>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
from_bitwise_digits_le(v: &[u8], bits: usize) -> BigUint143 fn 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
from_inexact_bitwise_digits_le(v: &[u8], bits: usize) -> BigUint164 fn 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
from_radix_digits_be(v: &[u8], radix: u32) -> BigUint198 fn 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 
240 impl Num for BigUint {
241     type FromStrRadixErr = ParseBigIntError;
242 
243     /// Creates and initializes a `BigUint`.
from_str_radix(s: &str, radix: u32) -> Result<BigUint, ParseBigIntError>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 
297 forward_val_val_binop!(impl BitAnd for BigUint, bitand);
298 forward_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
302 impl<'a, 'b> BitAnd<&'b BigUint> for &'a BigUint {
303     type Output = BigUint;
304 
305     #[inline]
bitand(self, other: &BigUint) -> BigUint306     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 
316 forward_val_assign!(impl BitAndAssign for BigUint, bitand_assign);
317 
318 impl<'a> BitAnd<&'a BigUint> for BigUint {
319     type Output = BigUint;
320 
321     #[inline]
bitand(mut self, other: &BigUint) -> BigUint322     fn bitand(mut self, other: &BigUint) -> BigUint {
323         self &= other;
324         self
325     }
326 }
327 impl<'a> BitAndAssign<&'a BigUint> for BigUint {
328     #[inline]
bitand_assign(&mut self, other: &BigUint)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 
338 forward_all_binop_to_val_ref_commutative!(impl BitOr for BigUint, bitor);
339 forward_val_assign!(impl BitOrAssign for BigUint, bitor_assign);
340 
341 impl<'a> BitOr<&'a BigUint> for BigUint {
342     type Output = BigUint;
343 
bitor(mut self, other: &BigUint) -> BigUint344     fn bitor(mut self, other: &BigUint) -> BigUint {
345         self |= other;
346         self
347     }
348 }
349 impl<'a> BitOrAssign<&'a BigUint> for BigUint {
350     #[inline]
bitor_assign(&mut self, other: &BigUint)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 
362 forward_all_binop_to_val_ref_commutative!(impl BitXor for BigUint, bitxor);
363 forward_val_assign!(impl BitXorAssign for BigUint, bitxor_assign);
364 
365 impl<'a> BitXor<&'a BigUint> for BigUint {
366     type Output = BigUint;
367 
bitxor(mut self, other: &BigUint) -> BigUint368     fn bitxor(mut self, other: &BigUint) -> BigUint {
369         self ^= other;
370         self
371     }
372 }
373 impl<'a> BitXorAssign<&'a BigUint> for BigUint {
374     #[inline]
bitxor_assign(&mut self, other: &BigUint)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 
387 impl Shl<usize> for BigUint {
388     type Output = BigUint;
389 
390     #[inline]
shl(self, rhs: usize) -> BigUint391     fn shl(self, rhs: usize) -> BigUint {
392         biguint_shl(Cow::Owned(self), rhs)
393     }
394 }
395 impl<'a> Shl<usize> for &'a BigUint {
396     type Output = BigUint;
397 
398     #[inline]
shl(self, rhs: usize) -> BigUint399     fn shl(self, rhs: usize) -> BigUint {
400         biguint_shl(Cow::Borrowed(self), rhs)
401     }
402 }
403 
404 impl ShlAssign<usize> for BigUint {
405     #[inline]
shl_assign(&mut self, rhs: usize)406     fn shl_assign(&mut self, rhs: usize) {
407         let n = mem::replace(self, BigUint::zero());
408         *self = n << rhs;
409     }
410 }
411 
412 impl Shr<usize> for BigUint {
413     type Output = BigUint;
414 
415     #[inline]
shr(self, rhs: usize) -> BigUint416     fn shr(self, rhs: usize) -> BigUint {
417         biguint_shr(Cow::Owned(self), rhs)
418     }
419 }
420 impl<'a> Shr<usize> for &'a BigUint {
421     type Output = BigUint;
422 
423     #[inline]
shr(self, rhs: usize) -> BigUint424     fn shr(self, rhs: usize) -> BigUint {
425         biguint_shr(Cow::Borrowed(self), rhs)
426     }
427 }
428 
429 impl ShrAssign<usize> for BigUint {
430     #[inline]
shr_assign(&mut self, rhs: usize)431     fn shr_assign(&mut self, rhs: usize) {
432         let n = mem::replace(self, BigUint::zero());
433         *self = n >> rhs;
434     }
435 }
436 
437 impl Zero for BigUint {
438     #[inline]
zero() -> BigUint439     fn zero() -> BigUint {
440         BigUint::new(Vec::new())
441     }
442 
443     #[inline]
set_zero(&mut self)444     fn set_zero(&mut self) {
445         self.data.clear();
446     }
447 
448     #[inline]
is_zero(&self) -> bool449     fn is_zero(&self) -> bool {
450         self.data.is_empty()
451     }
452 }
453 
454 impl One for BigUint {
455     #[inline]
one() -> BigUint456     fn one() -> BigUint {
457         BigUint::new(vec![1])
458     }
459 
460     #[inline]
set_one(&mut self)461     fn set_one(&mut self) {
462         self.data.clear();
463         self.data.push(1);
464     }
465 
466     #[inline]
is_one(&self) -> bool467     fn is_one(&self) -> bool {
468         self.data[..] == [1]
469     }
470 }
471 
472 impl Unsigned for BigUint {}
473 
474 impl<'a> Pow<BigUint> for &'a BigUint {
475     type Output = BigUint;
476 
477     #[inline]
pow(self, exp: BigUint) -> Self::Output478     fn pow(self, exp: BigUint) -> Self::Output {
479         self.pow(&exp)
480     }
481 }
482 
483 impl<'a, 'b> Pow<&'b BigUint> for &'a BigUint {
484     type Output = BigUint;
485 
486     #[inline]
pow(self, exp: &BigUint) -> Self::Output487     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 
502 macro_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 
546 pow_impl!(u8);
547 pow_impl!(u16);
548 pow_impl!(u32);
549 pow_impl!(u64);
550 pow_impl!(usize);
551 #[cfg(has_i128)]
552 pow_impl!(u128);
553 
554 forward_all_binop_to_val_ref_commutative!(impl Add for BigUint, add);
555 forward_val_assign!(impl AddAssign for BigUint, add_assign);
556 
557 impl<'a> Add<&'a BigUint> for BigUint {
558     type Output = BigUint;
559 
add(mut self, other: &BigUint) -> BigUint560     fn add(mut self, other: &BigUint) -> BigUint {
561         self += other;
562         self
563     }
564 }
565 impl<'a> AddAssign<&'a BigUint> for BigUint {
566     #[inline]
add_assign(&mut self, other: &BigUint)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 
582 promote_unsigned_scalars!(impl Add for BigUint, add);
583 promote_unsigned_scalars_assign!(impl AddAssign for BigUint, add_assign);
584 forward_all_scalar_binop_to_val_val_commutative!(impl Add<u32> for BigUint, add);
585 forward_all_scalar_binop_to_val_val_commutative!(impl Add<u64> for BigUint, add);
586 #[cfg(has_i128)]
587 forward_all_scalar_binop_to_val_val_commutative!(impl Add<u128> for BigUint, add);
588 
589 impl Add<u32> for BigUint {
590     type Output = BigUint;
591 
592     #[inline]
add(mut self, other: u32) -> BigUint593     fn add(mut self, other: u32) -> BigUint {
594         self += other;
595         self
596     }
597 }
598 
599 impl AddAssign<u32> for BigUint {
600     #[inline]
add_assign(&mut self, other: u32)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 
615 impl Add<u64> for BigUint {
616     type Output = BigUint;
617 
618     #[inline]
add(mut self, other: u64) -> BigUint619     fn add(mut self, other: u64) -> BigUint {
620         self += other;
621         self
622     }
623 }
624 
625 impl AddAssign<u64> for BigUint {
626     #[inline]
add_assign(&mut self, other: u64)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)]
645 impl Add<u128> for BigUint {
646     type Output = BigUint;
647 
648     #[inline]
add(mut self, other: u128) -> BigUint649     fn add(mut self, other: u128) -> BigUint {
650         self += other;
651         self
652     }
653 }
654 
655 #[cfg(has_i128)]
656 impl AddAssign<u128> for BigUint {
657     #[inline]
add_assign(&mut self, other: u128)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 
683 forward_val_val_binop!(impl Sub for BigUint, sub);
684 forward_ref_ref_binop!(impl Sub for BigUint, sub);
685 forward_val_assign!(impl SubAssign for BigUint, sub_assign);
686 
687 impl<'a> Sub<&'a BigUint> for BigUint {
688     type Output = BigUint;
689 
sub(mut self, other: &BigUint) -> BigUint690     fn sub(mut self, other: &BigUint) -> BigUint {
691         self -= other;
692         self
693     }
694 }
695 impl<'a> SubAssign<&'a BigUint> for BigUint {
sub_assign(&mut self, other: &'a BigUint)696     fn sub_assign(&mut self, other: &'a BigUint) {
697         sub2(&mut self.data[..], &other.data[..]);
698         self.normalize();
699     }
700 }
701 
702 impl<'a> Sub<BigUint> for &'a BigUint {
703     type Output = BigUint;
704 
sub(self, mut other: BigUint) -> BigUint705     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 
720 promote_unsigned_scalars!(impl Sub for BigUint, sub);
721 promote_unsigned_scalars_assign!(impl SubAssign for BigUint, sub_assign);
722 forward_all_scalar_binop_to_val_val!(impl Sub<u32> for BigUint, sub);
723 forward_all_scalar_binop_to_val_val!(impl Sub<u64> for BigUint, sub);
724 #[cfg(has_i128)]
725 forward_all_scalar_binop_to_val_val!(impl Sub<u128> for BigUint, sub);
726 
727 impl Sub<u32> for BigUint {
728     type Output = BigUint;
729 
730     #[inline]
sub(mut self, other: u32) -> BigUint731     fn sub(mut self, other: u32) -> BigUint {
732         self -= other;
733         self
734     }
735 }
736 impl SubAssign<u32> for BigUint {
sub_assign(&mut self, other: u32)737     fn sub_assign(&mut self, other: u32) {
738         sub2(&mut self.data[..], &[other as BigDigit]);
739         self.normalize();
740     }
741 }
742 
743 impl Sub<BigUint> for u32 {
744     type Output = BigUint;
745 
746     #[inline]
sub(self, mut other: BigUint) -> BigUint747     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 
757 impl Sub<u64> for BigUint {
758     type Output = BigUint;
759 
760     #[inline]
sub(mut self, other: u64) -> BigUint761     fn sub(mut self, other: u64) -> BigUint {
762         self -= other;
763         self
764     }
765 }
766 
767 impl SubAssign<u64> for BigUint {
768     #[inline]
sub_assign(&mut self, other: u64)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 
776 impl Sub<BigUint> for u64 {
777     type Output = BigUint;
778 
779     #[inline]
sub(self, mut other: BigUint) -> BigUint780     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)]
792 impl Sub<u128> for BigUint {
793     type Output = BigUint;
794 
795     #[inline]
sub(mut self, other: u128) -> BigUint796     fn sub(mut self, other: u128) -> BigUint {
797         self -= other;
798         self
799     }
800 }
801 #[cfg(has_i128)]
802 impl SubAssign<u128> for BigUint {
sub_assign(&mut self, other: u128)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)]
811 impl Sub<BigUint> for u128 {
812     type Output = BigUint;
813 
814     #[inline]
sub(self, mut other: BigUint) -> BigUint815     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 
826 forward_all_binop_to_ref_ref!(impl Mul for BigUint, mul);
827 forward_val_assign!(impl MulAssign for BigUint, mul_assign);
828 
829 impl<'a, 'b> Mul<&'b BigUint> for &'a BigUint {
830     type Output = BigUint;
831 
832     #[inline]
mul(self, other: &BigUint) -> BigUint833     fn mul(self, other: &BigUint) -> BigUint {
834         mul3(&self.data[..], &other.data[..])
835     }
836 }
837 impl<'a> MulAssign<&'a BigUint> for BigUint {
838     #[inline]
mul_assign(&mut self, other: &'a BigUint)839     fn mul_assign(&mut self, other: &'a BigUint) {
840         *self = &*self * other
841     }
842 }
843 
844 promote_unsigned_scalars!(impl Mul for BigUint, mul);
845 promote_unsigned_scalars_assign!(impl MulAssign for BigUint, mul_assign);
846 forward_all_scalar_binop_to_val_val_commutative!(impl Mul<u32> for BigUint, mul);
847 forward_all_scalar_binop_to_val_val_commutative!(impl Mul<u64> for BigUint, mul);
848 #[cfg(has_i128)]
849 forward_all_scalar_binop_to_val_val_commutative!(impl Mul<u128> for BigUint, mul);
850 
851 impl Mul<u32> for BigUint {
852     type Output = BigUint;
853 
854     #[inline]
mul(mut self, other: u32) -> BigUint855     fn mul(mut self, other: u32) -> BigUint {
856         self *= other;
857         self
858     }
859 }
860 impl MulAssign<u32> for BigUint {
861     #[inline]
mul_assign(&mut self, other: u32)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 
874 impl Mul<u64> for BigUint {
875     type Output = BigUint;
876 
877     #[inline]
mul(mut self, other: u64) -> BigUint878     fn mul(mut self, other: u64) -> BigUint {
879         self *= other;
880         self
881     }
882 }
883 impl MulAssign<u64> for BigUint {
884     #[inline]
mul_assign(&mut self, other: u64)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)]
898 impl Mul<u128> for BigUint {
899     type Output = BigUint;
900 
901     #[inline]
mul(mut self, other: u128) -> BigUint902     fn mul(mut self, other: u128) -> BigUint {
903         self *= other;
904         self
905     }
906 }
907 #[cfg(has_i128)]
908 impl MulAssign<u128> for BigUint {
909     #[inline]
mul_assign(&mut self, other: u128)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 
922 forward_val_ref_binop!(impl Div for BigUint, div);
923 forward_ref_val_binop!(impl Div for BigUint, div);
924 forward_val_assign!(impl DivAssign for BigUint, div_assign);
925 
926 impl Div<BigUint> for BigUint {
927     type Output = BigUint;
928 
929     #[inline]
div(self, other: BigUint) -> BigUint930     fn div(self, other: BigUint) -> BigUint {
931         let (q, _) = div_rem(self, other);
932         q
933     }
934 }
935 
936 impl<'a, 'b> Div<&'b BigUint> for &'a BigUint {
937     type Output = BigUint;
938 
939     #[inline]
div(self, other: &BigUint) -> BigUint940     fn div(self, other: &BigUint) -> BigUint {
941         let (q, _) = self.div_rem(other);
942         q
943     }
944 }
945 impl<'a> DivAssign<&'a BigUint> for BigUint {
946     #[inline]
div_assign(&mut self, other: &'a BigUint)947     fn div_assign(&mut self, other: &'a BigUint) {
948         *self = &*self / other;
949     }
950 }
951 
952 promote_unsigned_scalars!(impl Div for BigUint, div);
953 promote_unsigned_scalars_assign!(impl DivAssign for BigUint, div_assign);
954 forward_all_scalar_binop_to_val_val!(impl Div<u32> for BigUint, div);
955 forward_all_scalar_binop_to_val_val!(impl Div<u64> for BigUint, div);
956 #[cfg(has_i128)]
957 forward_all_scalar_binop_to_val_val!(impl Div<u128> for BigUint, div);
958 
959 impl Div<u32> for BigUint {
960     type Output = BigUint;
961 
962     #[inline]
div(self, other: u32) -> BigUint963     fn div(self, other: u32) -> BigUint {
964         let (q, _) = div_rem_digit(self, other as BigDigit);
965         q
966     }
967 }
968 impl DivAssign<u32> for BigUint {
969     #[inline]
div_assign(&mut self, other: u32)970     fn div_assign(&mut self, other: u32) {
971         *self = &*self / other;
972     }
973 }
974 
975 impl Div<BigUint> for u32 {
976     type Output = BigUint;
977 
978     #[inline]
div(self, other: BigUint) -> BigUint979     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 
988 impl Div<u64> for BigUint {
989     type Output = BigUint;
990 
991     #[inline]
div(self, other: u64) -> BigUint992     fn div(self, other: u64) -> BigUint {
993         let (q, _) = div_rem(self, From::from(other));
994         q
995     }
996 }
997 impl DivAssign<u64> for BigUint {
998     #[inline]
div_assign(&mut self, other: u64)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 
1006 impl Div<BigUint> for u64 {
1007     type Output = BigUint;
1008 
1009     #[inline]
div(self, other: BigUint) -> BigUint1010     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)]
1021 impl Div<u128> for BigUint {
1022     type Output = BigUint;
1023 
1024     #[inline]
div(self, other: u128) -> BigUint1025     fn div(self, other: u128) -> BigUint {
1026         let (q, _) = div_rem(self, From::from(other));
1027         q
1028     }
1029 }
1030 #[cfg(has_i128)]
1031 impl DivAssign<u128> for BigUint {
1032     #[inline]
div_assign(&mut self, other: u128)1033     fn div_assign(&mut self, other: u128) {
1034         *self = &*self / other;
1035     }
1036 }
1037 
1038 #[cfg(has_i128)]
1039 impl Div<BigUint> for u128 {
1040     type Output = BigUint;
1041 
1042     #[inline]
div(self, other: BigUint) -> BigUint1043     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 
1059 forward_val_ref_binop!(impl Rem for BigUint, rem);
1060 forward_ref_val_binop!(impl Rem for BigUint, rem);
1061 forward_val_assign!(impl RemAssign for BigUint, rem_assign);
1062 
1063 impl Rem<BigUint> for BigUint {
1064     type Output = BigUint;
1065 
1066     #[inline]
rem(self, other: BigUint) -> BigUint1067     fn rem(self, other: BigUint) -> BigUint {
1068         let (_, r) = div_rem(self, other);
1069         r
1070     }
1071 }
1072 
1073 impl<'a, 'b> Rem<&'b BigUint> for &'a BigUint {
1074     type Output = BigUint;
1075 
1076     #[inline]
rem(self, other: &BigUint) -> BigUint1077     fn rem(self, other: &BigUint) -> BigUint {
1078         let (_, r) = self.div_rem(other);
1079         r
1080     }
1081 }
1082 impl<'a> RemAssign<&'a BigUint> for BigUint {
1083     #[inline]
rem_assign(&mut self, other: &BigUint)1084     fn rem_assign(&mut self, other: &BigUint) {
1085         *self = &*self % other;
1086     }
1087 }
1088 
1089 promote_unsigned_scalars!(impl Rem for BigUint, rem);
1090 promote_unsigned_scalars_assign!(impl RemAssign for BigUint, rem_assign);
1091 forward_all_scalar_binop_to_ref_val!(impl Rem<u32> for BigUint, rem);
1092 forward_all_scalar_binop_to_val_val!(impl Rem<u64> for BigUint, rem);
1093 #[cfg(has_i128)]
1094 forward_all_scalar_binop_to_val_val!(impl Rem<u128> for BigUint, rem);
1095 
1096 impl<'a> Rem<u32> for &'a BigUint {
1097     type Output = BigUint;
1098 
1099     #[inline]
rem(self, other: u32) -> BigUint1100     fn rem(self, other: u32) -> BigUint {
1101         From::from(rem_digit(self, other as BigDigit))
1102     }
1103 }
1104 impl RemAssign<u32> for BigUint {
1105     #[inline]
rem_assign(&mut self, other: u32)1106     fn rem_assign(&mut self, other: u32) {
1107         *self = &*self % other;
1108     }
1109 }
1110 
1111 impl<'a> Rem<&'a BigUint> for u32 {
1112     type Output = BigUint;
1113 
1114     #[inline]
rem(mut self, other: &'a BigUint) -> BigUint1115     fn rem(mut self, other: &'a BigUint) -> BigUint {
1116         self %= other;
1117         From::from(self)
1118     }
1119 }
1120 
1121 macro_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)]
1138 impl_rem_assign_scalar!(u128, to_u128);
1139 impl_rem_assign_scalar!(usize, to_usize);
1140 impl_rem_assign_scalar!(u64, to_u64);
1141 impl_rem_assign_scalar!(u32, to_u32);
1142 impl_rem_assign_scalar!(u16, to_u16);
1143 impl_rem_assign_scalar!(u8, to_u8);
1144 #[cfg(has_i128)]
1145 impl_rem_assign_scalar!(i128, to_i128);
1146 impl_rem_assign_scalar!(isize, to_isize);
1147 impl_rem_assign_scalar!(i64, to_i64);
1148 impl_rem_assign_scalar!(i32, to_i32);
1149 impl_rem_assign_scalar!(i16, to_i16);
1150 impl_rem_assign_scalar!(i8, to_i8);
1151 
1152 impl Rem<u64> for BigUint {
1153     type Output = BigUint;
1154 
1155     #[inline]
rem(self, other: u64) -> BigUint1156     fn rem(self, other: u64) -> BigUint {
1157         let (_, r) = div_rem(self, From::from(other));
1158         r
1159     }
1160 }
1161 impl RemAssign<u64> for BigUint {
1162     #[inline]
rem_assign(&mut self, other: u64)1163     fn rem_assign(&mut self, other: u64) {
1164         *self = &*self % other;
1165     }
1166 }
1167 
1168 impl Rem<BigUint> for u64 {
1169     type Output = BigUint;
1170 
1171     #[inline]
rem(mut self, other: BigUint) -> BigUint1172     fn rem(mut self, other: BigUint) -> BigUint {
1173         self %= other;
1174         From::from(self)
1175     }
1176 }
1177 
1178 #[cfg(has_i128)]
1179 impl Rem<u128> for BigUint {
1180     type Output = BigUint;
1181 
1182     #[inline]
rem(self, other: u128) -> BigUint1183     fn rem(self, other: u128) -> BigUint {
1184         let (_, r) = div_rem(self, From::from(other));
1185         r
1186     }
1187 }
1188 #[cfg(has_i128)]
1189 impl RemAssign<u128> for BigUint {
1190     #[inline]
rem_assign(&mut self, other: u128)1191     fn rem_assign(&mut self, other: u128) {
1192         *self = &*self % other;
1193     }
1194 }
1195 
1196 #[cfg(has_i128)]
1197 impl Rem<BigUint> for u128 {
1198     type Output = BigUint;
1199 
1200     #[inline]
rem(mut self, other: BigUint) -> BigUint1201     fn rem(mut self, other: BigUint) -> BigUint {
1202         self %= other;
1203         From::from(self)
1204     }
1205 }
1206 
1207 impl Neg for BigUint {
1208     type Output = BigUint;
1209 
1210     #[inline]
neg(self) -> BigUint1211     fn neg(self) -> BigUint {
1212         panic!()
1213     }
1214 }
1215 
1216 impl<'a> Neg for &'a BigUint {
1217     type Output = BigUint;
1218 
1219     #[inline]
neg(self) -> BigUint1220     fn neg(self) -> BigUint {
1221         panic!()
1222     }
1223 }
1224 
1225 impl CheckedAdd for BigUint {
1226     #[inline]
checked_add(&self, v: &BigUint) -> Option<BigUint>1227     fn checked_add(&self, v: &BigUint) -> Option<BigUint> {
1228         Some(self.add(v))
1229     }
1230 }
1231 
1232 impl CheckedSub for BigUint {
1233     #[inline]
checked_sub(&self, v: &BigUint) -> Option<BigUint>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 
1243 impl CheckedMul for BigUint {
1244     #[inline]
checked_mul(&self, v: &BigUint) -> Option<BigUint>1245     fn checked_mul(&self, v: &BigUint) -> Option<BigUint> {
1246         Some(self.mul(v))
1247     }
1248 }
1249 
1250 impl CheckedDiv for BigUint {
1251     #[inline]
checked_div(&self, v: &BigUint) -> Option<BigUint>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 
1260 impl Integer for BigUint {
1261     #[inline]
div_rem(&self, other: &BigUint) -> (BigUint, BigUint)1262     fn div_rem(&self, other: &BigUint) -> (BigUint, BigUint) {
1263         div_rem_ref(self, other)
1264     }
1265 
1266     #[inline]
div_floor(&self, other: &BigUint) -> BigUint1267     fn div_floor(&self, other: &BigUint) -> BigUint {
1268         let (d, _) = div_rem_ref(self, other);
1269         d
1270     }
1271 
1272     #[inline]
mod_floor(&self, other: &BigUint) -> BigUint1273     fn mod_floor(&self, other: &BigUint) -> BigUint {
1274         let (_, m) = div_rem_ref(self, other);
1275         m
1276     }
1277 
1278     #[inline]
div_mod_floor(&self, other: &BigUint) -> (BigUint, BigUint)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]
gcd(&self, other: &Self) -> Self1287     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]
lcm(&self, other: &BigUint) -> BigUint1323     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]
divides(&self, other: &BigUint) -> bool1333     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]
is_multiple_of(&self, other: &BigUint) -> bool1339     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]
is_even(&self) -> bool1345     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]
is_odd(&self) -> bool1355     fn is_odd(&self) -> bool {
1356         !self.is_even()
1357     }
1358 }
1359 
1360 #[inline]
fixpoint<F>(mut x: BigUint, max_bits: usize, f: F) -> BigUint where F: Fn(&BigUint) -> BigUint,1361 fn fixpoint<F>(mut x: BigUint, max_bits: usize, f: F) -> BigUint
1362 where
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 
1389 impl 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
nth_root(&self, n: u32) -> Self1395     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
sqrt(&self) -> Self1450     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 
cbrt(&self) -> Self1482     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 
high_bits_to_u64(v: &BigUint) -> u641515 fn 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 
1545 impl ToPrimitive for BigUint {
1546     #[inline]
to_i64(&self) -> Option<i64>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)]
to_i128(&self) -> Option<i128>1553     fn to_i128(&self) -> Option<i128> {
1554         self.to_u128().as_ref().and_then(u128::to_i128)
1555     }
1556 
1557     #[inline]
to_u64(&self) -> Option<u64>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)]
to_u128(&self) -> Option<u128>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]
to_f32(&self) -> Option<f32>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]
to_f64(&self) -> Option<f64>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 
1627 impl FromPrimitive for BigUint {
1628     #[inline]
from_i64(n: i64) -> Option<BigUint>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)]
from_i128(n: i128) -> Option<BigUint>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]
from_u64(n: u64) -> Option<BigUint>1648     fn from_u64(n: u64) -> Option<BigUint> {
1649         Some(BigUint::from(n))
1650     }
1651 
1652     #[inline]
1653     #[cfg(has_i128)]
from_u128(n: u128) -> Option<BigUint>1654     fn from_u128(n: u128) -> Option<BigUint> {
1655         Some(BigUint::from(n))
1656     }
1657 
1658     #[inline]
from_f64(mut n: f64) -> Option<BigUint>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 
1689 impl From<u64> for BigUint {
1690     #[inline]
from(mut n: u64) -> Self1691     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)]
1705 impl From<u128> for BigUint {
1706     #[inline]
from(mut n: u128) -> Self1707     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 
1719 macro_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 
1730 impl_biguint_from_uint!(u8);
1731 impl_biguint_from_uint!(u16);
1732 impl_biguint_from_uint!(u32);
1733 impl_biguint_from_uint!(usize);
1734 
1735 /// A generic trait for converting a value to a `BigUint`.
1736 pub trait ToBigUint {
1737     /// Converts the value of `self` to a `BigUint`.
to_biguint(&self) -> Option<BigUint>1738     fn to_biguint(&self) -> Option<BigUint>;
1739 }
1740 
1741 impl ToBigUint for BigUint {
1742     #[inline]
to_biguint(&self) -> Option<BigUint>1743     fn to_biguint(&self) -> Option<BigUint> {
1744         Some(self.clone())
1745     }
1746 }
1747 
1748 macro_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 
1759 impl_to_biguint!(isize, FromPrimitive::from_isize);
1760 impl_to_biguint!(i8, FromPrimitive::from_i8);
1761 impl_to_biguint!(i16, FromPrimitive::from_i16);
1762 impl_to_biguint!(i32, FromPrimitive::from_i32);
1763 impl_to_biguint!(i64, FromPrimitive::from_i64);
1764 #[cfg(has_i128)]
1765 impl_to_biguint!(i128, FromPrimitive::from_i128);
1766 
1767 impl_to_biguint!(usize, FromPrimitive::from_usize);
1768 impl_to_biguint!(u8, FromPrimitive::from_u8);
1769 impl_to_biguint!(u16, FromPrimitive::from_u16);
1770 impl_to_biguint!(u32, FromPrimitive::from_u32);
1771 impl_to_biguint!(u64, FromPrimitive::from_u64);
1772 #[cfg(has_i128)]
1773 impl_to_biguint!(u128, FromPrimitive::from_u128);
1774 
1775 impl_to_biguint!(f32, FromPrimitive::from_f32);
1776 impl_to_biguint!(f64, FromPrimitive::from_f64);
1777 
1778 // Extract bitwise digits that evenly divide BigDigit
to_bitwise_digits_le(u: &BigUint, bits: usize) -> Vec<u8>1779 fn 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
to_inexact_bitwise_digits_le(u: &BigUint, bits: usize) -> Vec<u8>1805 fn 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
to_radix_digits_le(u: &BigUint, radix: u32) -> Vec<u8>1845 fn 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 
to_radix_le(u: &BigUint, radix: u32) -> Vec<u8>1874 pub 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 
to_str_radix_reversed(u: &BigUint, radix: u32) -> Vec<u8>1894 pub 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 
1915 impl BigUint {
1916     /// Creates and initializes a `BigUint`.
1917     ///
1918     /// The base 2<sup>32</sup> digits are ordered least significant digit first.
1919     #[inline]
new(digits: Vec<u32>) -> BigUint1920     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]
from_slice(slice: &[u32]) -> BigUint1928     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]
assign_from_slice(&mut self, slice: &[u32])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]
from_bytes_be(bytes: &[u8]) -> BigUint1961     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]
from_bytes_le(bytes: &[u8]) -> BigUint1975     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]
parse_bytes(buf: &[u8], radix: u32) -> Option<BigUint>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     /// ```
from_radix_be(buf: &[u8], radix: u32) -> Option<BigUint>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     /// ```
from_radix_le(buf: &[u8], radix: u32) -> Option<BigUint>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]
to_bytes_be(&self) -> Vec<u8>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]
to_bytes_le(&self) -> Vec<u8>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]
to_u32_digits(&self) -> Vec<u32>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]
to_str_radix(&self, radix: u32) -> String2158     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]
to_radix_be(&self, radix: u32) -> Vec<u8>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]
to_radix_le(&self, radix: u32) -> Vec<u8>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]
bits(&self) -> usize2206     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]
normalize(&mut self)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]
normalized(mut self) -> BigUint2225     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.
modpow(&self, exponent: &Self, modulus: &Self) -> Self2233     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)
sqrt(&self) -> Self2247     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).
cbrt(&self) -> Self2253     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).
nth_root(&self, n: u32) -> Self2259     pub fn nth_root(&self, n: u32) -> Self {
2260         Roots::nth_root(self, n)
2261     }
2262 }
2263 
plain_modpow(base: &BigUint, exp_data: &[BigDigit], modulus: &BigUint) -> BigUint2264 fn 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]
test_plain_modpow()2332 fn 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.
trailing_zeros(u: &BigUint) -> Option<usize>2365 pub 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 
2373 impl_sum_iter_type!(BigUint);
2374 impl_product_iter_type!(BigUint);
2375 
2376 pub trait IntDigits {
digits(&self) -> &[BigDigit]2377     fn digits(&self) -> &[BigDigit];
digits_mut(&mut self) -> &mut Vec<BigDigit>2378     fn digits_mut(&mut self) -> &mut Vec<BigDigit>;
normalize(&mut self)2379     fn normalize(&mut self);
capacity(&self) -> usize2380     fn capacity(&self) -> usize;
len(&self) -> usize2381     fn len(&self) -> usize;
2382 }
2383 
2384 impl IntDigits for BigUint {
2385     #[inline]
digits(&self) -> &[BigDigit]2386     fn digits(&self) -> &[BigDigit] {
2387         &self.data
2388     }
2389     #[inline]
digits_mut(&mut self) -> &mut Vec<BigDigit>2390     fn digits_mut(&mut self) -> &mut Vec<BigDigit> {
2391         &mut self.data
2392     }
2393     #[inline]
normalize(&mut self)2394     fn normalize(&mut self) {
2395         self.normalize();
2396     }
2397     #[inline]
capacity(&self) -> usize2398     fn capacity(&self) -> usize {
2399         self.data.capacity()
2400     }
2401     #[inline]
len(&self) -> usize2402     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]
u32_to_u128(a: u32, b: u32, c: u32, d: u32) -> u1282410 fn 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]
u32_from_u128(n: u128) -> (u32, u32, u32, u32)2417 fn 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")]
2427 impl serde::Serialize for BigUint {
serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> where S: serde::Serializer,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")]
2441 impl<'de> serde::Deserialize<'de> for BigUint {
deserialize<D>(deserializer: D) -> Result<Self, D::Error> where D: serde::Deserializer<'de>,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]
get_radix_base(radix: u32) -> (BigDigit, usize)2453 fn 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]
test_from_slice()3021 fn 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]
test_assign_from_slice()3034 fn 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]
test_u32_u128()3050 fn 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]
test_u128_u32_roundtrip()3082 fn 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]
test_pow_biguint()3101 fn 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 }
3107