1#[allow(deprecated, unused_imports)]
2use std::ascii::AsciiExt;
3use std::borrow::Cow;
4use std::cmp;
5use std::cmp::Ordering::{self, Equal, Greater, Less};
6use std::default::Default;
7use std::fmt;
8use std::iter::{Product, Sum};
9use std::mem;
10use std::ops::{
11 Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Div, DivAssign,
12 Mul, MulAssign, Neg, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign, Sub, SubAssign,
13};
14use std::str::{self, FromStr};
15use std::{f32, f64};
16use std::{u64, u8};
17
18#[cfg(feature = "serde")]
19use serde;
20
21use integer::{Integer, Roots};
22use traits::{
23 CheckedAdd, CheckedDiv, CheckedMul, CheckedSub, Float, FromPrimitive, Num, One, Pow,
24 ToPrimitive, Unsigned, Zero,
25};
26
27use big_digit::{self, BigDigit};
28
29#[path = "algorithms.rs"]
30mod algorithms;
31#[path = "monty.rs"]
32mod monty;
33
34use self::algorithms::{__add2, __sub2rev, add2, sub2, sub2rev};
35use self::algorithms::{biguint_shl, biguint_shr};
36use self::algorithms::{cmp_slice, fls, ilog2};
37use self::algorithms::{div_rem, div_rem_digit, div_rem_ref, rem_digit};
38use self::algorithms::{mac_with_carry, mul3, scalar_mul};
39use self::monty::monty_modpow;
40
41use UsizePromotion;
42
43use ParseBigIntError;
44
45#[cfg(feature = "quickcheck")]
46use quickcheck::{Arbitrary, Gen};
47
48#[derive(Clone, Debug, Hash)]
50pub struct BigUint {
51 data: Vec<BigDigit>,
52}
53
54#[cfg(feature = "quickcheck")]
55impl Arbitrary for BigUint {
56 fn arbitrary<G: Gen>(g: &mut G) -> Self {
57 Self::new(Vec::<u32>::arbitrary(g))
59 }
60
61 #[allow(bare_trait_objects)] fn shrink(&self) -> Box<Iterator<Item = Self>> {
63 Box::new(self.data.shrink().map(BigUint::new))
65 }
66}
67
68impl PartialEq for BigUint {
69 #[inline]
70 fn eq(&self, other: &BigUint) -> bool {
71 match self.cmp(other) {
72 Equal => true,
73 _ => false,
74 }
75 }
76}
77impl Eq for BigUint {}
78
79impl PartialOrd for BigUint {
80 #[inline]
81 fn partial_cmp(&self, other: &BigUint) -> Option<Ordering> {
82 Some(self.cmp(other))
83 }
84}
85
86impl Ord for BigUint {
87 #[inline]
88 fn cmp(&self, other: &BigUint) -> Ordering {
89 cmp_slice(&self.data[..], &other.data[..])
90 }
91}
92
93impl Default for BigUint {
94 #[inline]
95 fn default() -> BigUint {
96 Zero::zero()
97 }
98}
99
100impl fmt::Display for BigUint {
101 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
102 f.pad_integral(true, "", &self.to_str_radix(10))
103 }
104}
105
106impl fmt::LowerHex for BigUint {
107 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
108 f.pad_integral(true, "0x", &self.to_str_radix(16))
109 }
110}
111
112impl fmt::UpperHex for BigUint {
113 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
114 let mut s = self.to_str_radix(16);
115 s.make_ascii_uppercase();
116 f.pad_integral(true, "0x", &s)
117 }
118}
119
120impl fmt::Binary for BigUint {
121 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
122 f.pad_integral(true, "0b", &self.to_str_radix(2))
123 }
124}
125
126impl fmt::Octal for BigUint {
127 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
128 f.pad_integral(true, "0o", &self.to_str_radix(8))
129 }
130}
131
132impl FromStr for BigUint {
133 type Err = ParseBigIntError;
134
135 #[inline]
136 fn from_str(s: &str) -> Result<BigUint, ParseBigIntError> {
137 BigUint::from_str_radix(s, 10)
138 }
139}
140
141fn 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
162fn 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; 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 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
197fn 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 let bits = f64::from(radix).log2() * v.len() as f64;
204 let big_digits = (bits / big_digit::BITS as f64).ceil();
205 let mut data = Vec::with_capacity(big_digits as usize);
206
207 let (base, power) = get_radix_base(radix);
208 let radix = radix as BigDigit;
209
210 let r = v.len() % power;
211 let i = if r == 0 { power } else { r };
212 let (head, tail) = v.split_at(i);
213
214 let first = head
215 .iter()
216 .fold(0, |acc, &d| acc * radix + BigDigit::from(d));
217 data.push(first);
218
219 debug_assert!(tail.len() % power == 0);
220 for chunk in tail.chunks(power) {
221 if data.last() != Some(&0) {
222 data.push(0);
223 }
224
225 let mut carry = 0;
226 for d in data.iter_mut() {
227 *d = mac_with_carry(0, *d, base, &mut carry);
228 }
229 debug_assert!(carry == 0);
230
231 let n = chunk
232 .iter()
233 .fold(0, |acc, &d| acc * radix + BigDigit::from(d));
234 add2(&mut data, &[n]);
235 }
236
237 BigUint::new(data)
238}
239
240impl Num for BigUint {
241 type FromStrRadixErr = ParseBigIntError;
242
243 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 return Err(ParseBigIntError::invalid());
261 }
262
263 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 let bits = ilog2(radix);
284 v.reverse();
285 if big_digit::BITS % bits == 0 {
286 from_bitwise_digits_le(&v, bits)
287 } else {
288 from_inexact_bitwise_digits_le(&v, bits)
289 }
290 } else {
291 from_radix_digits_be(&v, radix)
292 };
293 Ok(res)
294 }
295}
296
297forward_val_val_binop!(impl BitAnd for BigUint, bitand);
298forward_ref_val_binop!(impl BitAnd for BigUint, bitand);
299
300impl<'a, 'b> BitAnd<&'b BigUint> for &'a BigUint {
303 type Output = BigUint;
304
305 #[inline]
306 fn bitand(self, other: &BigUint) -> BigUint {
307 if self.data.len() <= other.data.len() {
309 self.clone() & other
310 } else {
311 other.clone() & self
312 }
313 }
314}
315
316forward_val_assign!(impl BitAndAssign for BigUint, bitand_assign);
317
318impl<'a> BitAnd<&'a BigUint> for BigUint {
319 type Output = BigUint;
320
321 #[inline]
322 fn bitand(mut self, other: &BigUint) -> BigUint {
323 self &= other;
324 self
325 }
326}
327impl<'a> BitAndAssign<&'a BigUint> for BigUint {
328 #[inline]
329 fn bitand_assign(&mut self, other: &BigUint) {
330 for (ai, &bi) in self.data.iter_mut().zip(other.data.iter()) {
331 *ai &= bi;
332 }
333 self.data.truncate(other.data.len());
334 self.normalize();
335 }
336}
337
338forward_all_binop_to_val_ref_commutative!(impl BitOr for BigUint, bitor);
339forward_val_assign!(impl BitOrAssign for BigUint, bitor_assign);
340
341impl<'a> BitOr<&'a BigUint> for BigUint {
342 type Output = BigUint;
343
344 fn bitor(mut self, other: &BigUint) -> BigUint {
345 self |= other;
346 self
347 }
348}
349impl<'a> BitOrAssign<&'a BigUint> for BigUint {
350 #[inline]
351 fn bitor_assign(&mut self, other: &BigUint) {
352 for (ai, &bi) in self.data.iter_mut().zip(other.data.iter()) {
353 *ai |= bi;
354 }
355 if other.data.len() > self.data.len() {
356 let extra = &other.data[self.data.len()..];
357 self.data.extend(extra.iter().cloned());
358 }
359 }
360}
361
362forward_all_binop_to_val_ref_commutative!(impl BitXor for BigUint, bitxor);
363forward_val_assign!(impl BitXorAssign for BigUint, bitxor_assign);
364
365impl<'a> BitXor<&'a BigUint> for BigUint {
366 type Output = BigUint;
367
368 fn bitxor(mut self, other: &BigUint) -> BigUint {
369 self ^= other;
370 self
371 }
372}
373impl<'a> BitXorAssign<&'a BigUint> for BigUint {
374 #[inline]
375 fn bitxor_assign(&mut self, other: &BigUint) {
376 for (ai, &bi) in self.data.iter_mut().zip(other.data.iter()) {
377 *ai ^= bi;
378 }
379 if other.data.len() > self.data.len() {
380 let extra = &other.data[self.data.len()..];
381 self.data.extend(extra.iter().cloned());
382 }
383 self.normalize();
384 }
385}
386
387impl Shl<usize> for BigUint {
388 type Output = BigUint;
389
390 #[inline]
391 fn shl(self, rhs: usize) -> BigUint {
392 biguint_shl(Cow::Owned(self), rhs)
393 }
394}
395impl<'a> Shl<usize> for &'a BigUint {
396 type Output = BigUint;
397
398 #[inline]
399 fn shl(self, rhs: usize) -> BigUint {
400 biguint_shl(Cow::Borrowed(self), rhs)
401 }
402}
403
404impl ShlAssign<usize> for BigUint {
405 #[inline]
406 fn shl_assign(&mut self, rhs: usize) {
407 let n = mem::replace(self, BigUint::zero());
408 *self = n << rhs;
409 }
410}
411
412impl Shr<usize> for BigUint {
413 type Output = BigUint;
414
415 #[inline]
416 fn shr(self, rhs: usize) -> BigUint {
417 biguint_shr(Cow::Owned(self), rhs)
418 }
419}
420impl<'a> Shr<usize> for &'a BigUint {
421 type Output = BigUint;
422
423 #[inline]
424 fn shr(self, rhs: usize) -> BigUint {
425 biguint_shr(Cow::Borrowed(self), rhs)
426 }
427}
428
429impl ShrAssign<usize> for BigUint {
430 #[inline]
431 fn shr_assign(&mut self, rhs: usize) {
432 let n = mem::replace(self, BigUint::zero());
433 *self = n >> rhs;
434 }
435}
436
437impl Zero for BigUint {
438 #[inline]
439 fn zero() -> BigUint {
440 BigUint::new(Vec::new())
441 }
442
443 #[inline]
444 fn set_zero(&mut self) {
445 self.data.clear();
446 }
447
448 #[inline]
449 fn is_zero(&self) -> bool {
450 self.data.is_empty()
451 }
452}
453
454impl One for BigUint {
455 #[inline]
456 fn one() -> BigUint {
457 BigUint::new(vec![1])
458 }
459
460 #[inline]
461 fn set_one(&mut self) {
462 self.data.clear();
463 self.data.push(1);
464 }
465
466 #[inline]
467 fn is_one(&self) -> bool {
468 self.data[..] == [1]
469 }
470}
471
472impl Unsigned for BigUint {}
473
474impl<'a> Pow<BigUint> for &'a BigUint {
475 type Output = BigUint;
476
477 #[inline]
478 fn pow(self, exp: BigUint) -> Self::Output {
479 self.pow(&exp)
480 }
481}
482
483impl<'a, 'b> Pow<&'b BigUint> for &'a BigUint {
484 type Output = BigUint;
485
486 #[inline]
487 fn pow(self, exp: &BigUint) -> Self::Output {
488 if self.is_one() || exp.is_zero() {
489 BigUint::one()
490 } else if self.is_zero() {
491 BigUint::zero()
492 } else if let Some(exp) = exp.to_u64() {
493 self.pow(exp)
494 } else {
495 panic!("memory overflow")
498 }
499 }
500}
501
502macro_rules! pow_impl {
503 ($T:ty) => {
504 impl<'a> Pow<$T> for &'a BigUint {
505 type Output = BigUint;
506
507 #[inline]
508 fn pow(self, mut exp: $T) -> Self::Output {
509 if exp == 0 {
510 return BigUint::one();
511 }
512 let mut base = self.clone();
513
514 while exp & 1 == 0 {
515 base = &base * &base;
516 exp >>= 1;
517 }
518
519 if exp == 1 {
520 return base;
521 }
522
523 let mut acc = base.clone();
524 while exp > 1 {
525 exp >>= 1;
526 base = &base * &base;
527 if exp & 1 == 1 {
528 acc = &acc * &base;
529 }
530 }
531 acc
532 }
533 }
534
535 impl<'a, 'b> Pow<&'b $T> for &'a BigUint {
536 type Output = BigUint;
537
538 #[inline]
539 fn pow(self, exp: &$T) -> Self::Output {
540 self.pow(*exp)
541 }
542 }
543 };
544}
545
546pow_impl!(u8);
547pow_impl!(u16);
548pow_impl!(u32);
549pow_impl!(u64);
550pow_impl!(usize);
551#[cfg(has_i128)]
552pow_impl!(u128);
553
554forward_all_binop_to_val_ref_commutative!(impl Add for BigUint, add);
555forward_val_assign!(impl AddAssign for BigUint, add_assign);
556
557impl<'a> Add<&'a BigUint> for BigUint {
558 type Output = BigUint;
559
560 fn add(mut self, other: &BigUint) -> BigUint {
561 self += other;
562 self
563 }
564}
565impl<'a> AddAssign<&'a BigUint> for BigUint {
566 #[inline]
567 fn add_assign(&mut self, other: &BigUint) {
568 let self_len = self.data.len();
569 let carry = if self_len < other.data.len() {
570 let lo_carry = __add2(&mut self.data[..], &other.data[..self_len]);
571 self.data.extend_from_slice(&other.data[self_len..]);
572 __add2(&mut self.data[self_len..], &[lo_carry])
573 } else {
574 __add2(&mut self.data[..], &other.data[..])
575 };
576 if carry != 0 {
577 self.data.push(carry);
578 }
579 }
580}
581
582promote_unsigned_scalars!(impl Add for BigUint, add);
583promote_unsigned_scalars_assign!(impl AddAssign for BigUint, add_assign);
584forward_all_scalar_binop_to_val_val_commutative!(impl Add<u32> for BigUint, add);
585forward_all_scalar_binop_to_val_val_commutative!(impl Add<u64> for BigUint, add);
586#[cfg(has_i128)]
587forward_all_scalar_binop_to_val_val_commutative!(impl Add<u128> for BigUint, add);
588
589impl Add<u32> for BigUint {
590 type Output = BigUint;
591
592 #[inline]
593 fn add(mut self, other: u32) -> BigUint {
594 self += other;
595 self
596 }
597}
598
599impl AddAssign<u32> for BigUint {
600 #[inline]
601 fn add_assign(&mut self, other: u32) {
602 if other != 0 {
603 if self.data.is_empty() {
604 self.data.push(0);
605 }
606
607 let carry = __add2(&mut self.data, &[other as BigDigit]);
608 if carry != 0 {
609 self.data.push(carry);
610 }
611 }
612 }
613}
614
615impl Add<u64> for BigUint {
616 type Output = BigUint;
617
618 #[inline]
619 fn add(mut self, other: u64) -> BigUint {
620 self += other;
621 self
622 }
623}
624
625impl AddAssign<u64> for BigUint {
626 #[inline]
627 fn add_assign(&mut self, other: u64) {
628 let (hi, lo) = big_digit::from_doublebigdigit(other);
629 if hi == 0 {
630 *self += lo;
631 } else {
632 while self.data.len() < 2 {
633 self.data.push(0);
634 }
635
636 let carry = __add2(&mut self.data, &[lo, hi]);
637 if carry != 0 {
638 self.data.push(carry);
639 }
640 }
641 }
642}
643
644#[cfg(has_i128)]
645impl Add<u128> for BigUint {
646 type Output = BigUint;
647
648 #[inline]
649 fn add(mut self, other: u128) -> BigUint {
650 self += other;
651 self
652 }
653}
654
655#[cfg(has_i128)]
656impl AddAssign<u128> for BigUint {
657 #[inline]
658 fn add_assign(&mut self, other: u128) {
659 if other <= u128::from(u64::max_value()) {
660 *self += other as u64
661 } else {
662 let (a, b, c, d) = u32_from_u128(other);
663 let carry = if a > 0 {
664 while self.data.len() < 4 {
665 self.data.push(0);
666 }
667 __add2(&mut self.data, &[d, c, b, a])
668 } else {
669 debug_assert!(b > 0);
670 while self.data.len() < 3 {
671 self.data.push(0);
672 }
673 __add2(&mut self.data, &[d, c, b])
674 };
675
676 if carry != 0 {
677 self.data.push(carry);
678 }
679 }
680 }
681}
682
683forward_val_val_binop!(impl Sub for BigUint, sub);
684forward_ref_ref_binop!(impl Sub for BigUint, sub);
685forward_val_assign!(impl SubAssign for BigUint, sub_assign);
686
687impl<'a> Sub<&'a BigUint> for BigUint {
688 type Output = BigUint;
689
690 fn sub(mut self, other: &BigUint) -> BigUint {
691 self -= other;
692 self
693 }
694}
695impl<'a> SubAssign<&'a BigUint> for BigUint {
696 fn sub_assign(&mut self, other: &'a BigUint) {
697 sub2(&mut self.data[..], &other.data[..]);
698 self.normalize();
699 }
700}
701
702impl<'a> Sub<BigUint> for &'a BigUint {
703 type Output = BigUint;
704
705 fn sub(self, mut other: BigUint) -> BigUint {
706 let other_len = other.data.len();
707 if other_len < self.data.len() {
708 let lo_borrow = __sub2rev(&self.data[..other_len], &mut other.data);
709 other.data.extend_from_slice(&self.data[other_len..]);
710 if lo_borrow != 0 {
711 sub2(&mut other.data[other_len..], &[1])
712 }
713 } else {
714 sub2rev(&self.data[..], &mut other.data[..]);
715 }
716 other.normalized()
717 }
718}
719
720promote_unsigned_scalars!(impl Sub for BigUint, sub);
721promote_unsigned_scalars_assign!(impl SubAssign for BigUint, sub_assign);
722forward_all_scalar_binop_to_val_val!(impl Sub<u32> for BigUint, sub);
723forward_all_scalar_binop_to_val_val!(impl Sub<u64> for BigUint, sub);
724#[cfg(has_i128)]
725forward_all_scalar_binop_to_val_val!(impl Sub<u128> for BigUint, sub);
726
727impl Sub<u32> for BigUint {
728 type Output = BigUint;
729
730 #[inline]
731 fn sub(mut self, other: u32) -> BigUint {
732 self -= other;
733 self
734 }
735}
736impl SubAssign<u32> for BigUint {
737 fn sub_assign(&mut self, other: u32) {
738 sub2(&mut self.data[..], &[other as BigDigit]);
739 self.normalize();
740 }
741}
742
743impl Sub<BigUint> for u32 {
744 type Output = BigUint;
745
746 #[inline]
747 fn sub(self, mut other: BigUint) -> BigUint {
748 if other.data.is_empty() {
749 other.data.push(self as BigDigit);
750 } else {
751 sub2rev(&[self as BigDigit], &mut other.data[..]);
752 }
753 other.normalized()
754 }
755}
756
757impl Sub<u64> for BigUint {
758 type Output = BigUint;
759
760 #[inline]
761 fn sub(mut self, other: u64) -> BigUint {
762 self -= other;
763 self
764 }
765}
766
767impl SubAssign<u64> for BigUint {
768 #[inline]
769 fn sub_assign(&mut self, other: u64) {
770 let (hi, lo) = big_digit::from_doublebigdigit(other);
771 sub2(&mut self.data[..], &[lo, hi]);
772 self.normalize();
773 }
774}
775
776impl Sub<BigUint> for u64 {
777 type Output = BigUint;
778
779 #[inline]
780 fn sub(self, mut other: BigUint) -> BigUint {
781 while other.data.len() < 2 {
782 other.data.push(0);
783 }
784
785 let (hi, lo) = big_digit::from_doublebigdigit(self);
786 sub2rev(&[lo, hi], &mut other.data[..]);
787 other.normalized()
788 }
789}
790
791#[cfg(has_i128)]
792impl Sub<u128> for BigUint {
793 type Output = BigUint;
794
795 #[inline]
796 fn sub(mut self, other: u128) -> BigUint {
797 self -= other;
798 self
799 }
800}
801#[cfg(has_i128)]
802impl SubAssign<u128> for BigUint {
803 fn sub_assign(&mut self, other: u128) {
804 let (a, b, c, d) = u32_from_u128(other);
805 sub2(&mut self.data[..], &[d, c, b, a]);
806 self.normalize();
807 }
808}
809
810#[cfg(has_i128)]
811impl Sub<BigUint> for u128 {
812 type Output = BigUint;
813
814 #[inline]
815 fn sub(self, mut other: BigUint) -> BigUint {
816 while other.data.len() < 4 {
817 other.data.push(0);
818 }
819
820 let (a, b, c, d) = u32_from_u128(self);
821 sub2rev(&[d, c, b, a], &mut other.data[..]);
822 other.normalized()
823 }
824}
825
826forward_all_binop_to_ref_ref!(impl Mul for BigUint, mul);
827forward_val_assign!(impl MulAssign for BigUint, mul_assign);
828
829impl<'a, 'b> Mul<&'b BigUint> for &'a BigUint {
830 type Output = BigUint;
831
832 #[inline]
833 fn mul(self, other: &BigUint) -> BigUint {
834 mul3(&self.data[..], &other.data[..])
835 }
836}
837impl<'a> MulAssign<&'a BigUint> for BigUint {
838 #[inline]
839 fn mul_assign(&mut self, other: &'a BigUint) {
840 *self = &*self * other
841 }
842}
843
844promote_unsigned_scalars!(impl Mul for BigUint, mul);
845promote_unsigned_scalars_assign!(impl MulAssign for BigUint, mul_assign);
846forward_all_scalar_binop_to_val_val_commutative!(impl Mul<u32> for BigUint, mul);
847forward_all_scalar_binop_to_val_val_commutative!(impl Mul<u64> for BigUint, mul);
848#[cfg(has_i128)]
849forward_all_scalar_binop_to_val_val_commutative!(impl Mul<u128> for BigUint, mul);
850
851impl Mul<u32> for BigUint {
852 type Output = BigUint;
853
854 #[inline]
855 fn mul(mut self, other: u32) -> BigUint {
856 self *= other;
857 self
858 }
859}
860impl MulAssign<u32> for BigUint {
861 #[inline]
862 fn mul_assign(&mut self, other: u32) {
863 if other == 0 {
864 self.data.clear();
865 } else {
866 let carry = scalar_mul(&mut self.data[..], other as BigDigit);
867 if carry != 0 {
868 self.data.push(carry);
869 }
870 }
871 }
872}
873
874impl Mul<u64> for BigUint {
875 type Output = BigUint;
876
877 #[inline]
878 fn mul(mut self, other: u64) -> BigUint {
879 self *= other;
880 self
881 }
882}
883impl MulAssign<u64> for BigUint {
884 #[inline]
885 fn mul_assign(&mut self, other: u64) {
886 if other == 0 {
887 self.data.clear();
888 } else if other <= u64::from(BigDigit::max_value()) {
889 *self *= other as BigDigit
890 } else {
891 let (hi, lo) = big_digit::from_doublebigdigit(other);
892 *self = mul3(&self.data[..], &[lo, hi])
893 }
894 }
895}
896
897#[cfg(has_i128)]
898impl Mul<u128> for BigUint {
899 type Output = BigUint;
900
901 #[inline]
902 fn mul(mut self, other: u128) -> BigUint {
903 self *= other;
904 self
905 }
906}
907#[cfg(has_i128)]
908impl MulAssign<u128> for BigUint {
909 #[inline]
910 fn mul_assign(&mut self, other: u128) {
911 if other == 0 {
912 self.data.clear();
913 } else if other <= u128::from(BigDigit::max_value()) {
914 *self *= other as BigDigit
915 } else {
916 let (a, b, c, d) = u32_from_u128(other);
917 *self = mul3(&self.data[..], &[d, c, b, a])
918 }
919 }
920}
921
922forward_val_ref_binop!(impl Div for BigUint, div);
923forward_ref_val_binop!(impl Div for BigUint, div);
924forward_val_assign!(impl DivAssign for BigUint, div_assign);
925
926impl Div<BigUint> for BigUint {
927 type Output = BigUint;
928
929 #[inline]
930 fn div(self, other: BigUint) -> BigUint {
931 let (q, _) = div_rem(self, other);
932 q
933 }
934}
935
936impl<'a, 'b> Div<&'b BigUint> for &'a BigUint {
937 type Output = BigUint;
938
939 #[inline]
940 fn div(self, other: &BigUint) -> BigUint {
941 let (q, _) = self.div_rem(other);
942 q
943 }
944}
945impl<'a> DivAssign<&'a BigUint> for BigUint {
946 #[inline]
947 fn div_assign(&mut self, other: &'a BigUint) {
948 *self = &*self / other;
949 }
950}
951
952promote_unsigned_scalars!(impl Div for BigUint, div);
953promote_unsigned_scalars_assign!(impl DivAssign for BigUint, div_assign);
954forward_all_scalar_binop_to_val_val!(impl Div<u32> for BigUint, div);
955forward_all_scalar_binop_to_val_val!(impl Div<u64> for BigUint, div);
956#[cfg(has_i128)]
957forward_all_scalar_binop_to_val_val!(impl Div<u128> for BigUint, div);
958
959impl Div<u32> for BigUint {
960 type Output = BigUint;
961
962 #[inline]
963 fn div(self, other: u32) -> BigUint {
964 let (q, _) = div_rem_digit(self, other as BigDigit);
965 q
966 }
967}
968impl DivAssign<u32> for BigUint {
969 #[inline]
970 fn div_assign(&mut self, other: u32) {
971 *self = &*self / other;
972 }
973}
974
975impl Div<BigUint> for u32 {
976 type Output = BigUint;
977
978 #[inline]
979 fn div(self, other: BigUint) -> BigUint {
980 match other.data.len() {
981 0 => panic!(),
982 1 => From::from(self as BigDigit / other.data[0]),
983 _ => Zero::zero(),
984 }
985 }
986}
987
988impl Div<u64> for BigUint {
989 type Output = BigUint;
990
991 #[inline]
992 fn div(self, other: u64) -> BigUint {
993 let (q, _) = div_rem(self, From::from(other));
994 q
995 }
996}
997impl DivAssign<u64> for BigUint {
998 #[inline]
999 fn div_assign(&mut self, other: u64) {
1000 let temp = mem::replace(self, Zero::zero());
1002 *self = temp / other;
1003 }
1004}
1005
1006impl Div<BigUint> for u64 {
1007 type Output = BigUint;
1008
1009 #[inline]
1010 fn div(self, other: BigUint) -> BigUint {
1011 match other.data.len() {
1012 0 => panic!(),
1013 1 => From::from(self / u64::from(other.data[0])),
1014 2 => From::from(self / big_digit::to_doublebigdigit(other.data[1], other.data[0])),
1015 _ => Zero::zero(),
1016 }
1017 }
1018}
1019
1020#[cfg(has_i128)]
1021impl Div<u128> for BigUint {
1022 type Output = BigUint;
1023
1024 #[inline]
1025 fn div(self, other: u128) -> BigUint {
1026 let (q, _) = div_rem(self, From::from(other));
1027 q
1028 }
1029}
1030#[cfg(has_i128)]
1031impl DivAssign<u128> for BigUint {
1032 #[inline]
1033 fn div_assign(&mut self, other: u128) {
1034 *self = &*self / other;
1035 }
1036}
1037
1038#[cfg(has_i128)]
1039impl Div<BigUint> for u128 {
1040 type Output = BigUint;
1041
1042 #[inline]
1043 fn div(self, other: BigUint) -> BigUint {
1044 match other.data.len() {
1045 0 => panic!(),
1046 1 => From::from(self / u128::from(other.data[0])),
1047 2 => From::from(
1048 self / u128::from(big_digit::to_doublebigdigit(other.data[1], other.data[0])),
1049 ),
1050 3 => From::from(self / u32_to_u128(0, other.data[2], other.data[1], other.data[0])),
1051 4 => From::from(
1052 self / u32_to_u128(other.data[3], other.data[2], other.data[1], other.data[0]),
1053 ),
1054 _ => Zero::zero(),
1055 }
1056 }
1057}
1058
1059forward_val_ref_binop!(impl Rem for BigUint, rem);
1060forward_ref_val_binop!(impl Rem for BigUint, rem);
1061forward_val_assign!(impl RemAssign for BigUint, rem_assign);
1062
1063impl Rem<BigUint> for BigUint {
1064 type Output = BigUint;
1065
1066 #[inline]
1067 fn rem(self, other: BigUint) -> BigUint {
1068 let (_, r) = div_rem(self, other);
1069 r
1070 }
1071}
1072
1073impl<'a, 'b> Rem<&'b BigUint> for &'a BigUint {
1074 type Output = BigUint;
1075
1076 #[inline]
1077 fn rem(self, other: &BigUint) -> BigUint {
1078 let (_, r) = self.div_rem(other);
1079 r
1080 }
1081}
1082impl<'a> RemAssign<&'a BigUint> for BigUint {
1083 #[inline]
1084 fn rem_assign(&mut self, other: &BigUint) {
1085 *self = &*self % other;
1086 }
1087}
1088
1089promote_unsigned_scalars!(impl Rem for BigUint, rem);
1090promote_unsigned_scalars_assign!(impl RemAssign for BigUint, rem_assign);
1091forward_all_scalar_binop_to_ref_val!(impl Rem<u32> for BigUint, rem);
1092forward_all_scalar_binop_to_val_val!(impl Rem<u64> for BigUint, rem);
1093#[cfg(has_i128)]
1094forward_all_scalar_binop_to_val_val!(impl Rem<u128> for BigUint, rem);
1095
1096impl<'a> Rem<u32> for &'a BigUint {
1097 type Output = BigUint;
1098
1099 #[inline]
1100 fn rem(self, other: u32) -> BigUint {
1101 From::from(rem_digit(self, other as BigDigit))
1102 }
1103}
1104impl RemAssign<u32> for BigUint {
1105 #[inline]
1106 fn rem_assign(&mut self, other: u32) {
1107 *self = &*self % other;
1108 }
1109}
1110
1111impl<'a> Rem<&'a BigUint> for u32 {
1112 type Output = BigUint;
1113
1114 #[inline]
1115 fn rem(mut self, other: &'a BigUint) -> BigUint {
1116 self %= other;
1117 From::from(self)
1118 }
1119}
1120
1121macro_rules! impl_rem_assign_scalar {
1122 ($scalar:ty, $to_scalar:ident) => {
1123 forward_val_assign_scalar!(impl RemAssign for BigUint, $scalar, rem_assign);
1124 impl<'a> RemAssign<&'a BigUint> for $scalar {
1125 #[inline]
1126 fn rem_assign(&mut self, other: &BigUint) {
1127 *self = match other.$to_scalar() {
1128 None => *self,
1129 Some(0) => panic!(),
1130 Some(v) => *self % v
1131 };
1132 }
1133 }
1134 }
1135}
1136#[cfg(has_i128)]
1138impl_rem_assign_scalar!(u128, to_u128);
1139impl_rem_assign_scalar!(usize, to_usize);
1140impl_rem_assign_scalar!(u64, to_u64);
1141impl_rem_assign_scalar!(u32, to_u32);
1142impl_rem_assign_scalar!(u16, to_u16);
1143impl_rem_assign_scalar!(u8, to_u8);
1144#[cfg(has_i128)]
1145impl_rem_assign_scalar!(i128, to_i128);
1146impl_rem_assign_scalar!(isize, to_isize);
1147impl_rem_assign_scalar!(i64, to_i64);
1148impl_rem_assign_scalar!(i32, to_i32);
1149impl_rem_assign_scalar!(i16, to_i16);
1150impl_rem_assign_scalar!(i8, to_i8);
1151
1152impl Rem<u64> for BigUint {
1153 type Output = BigUint;
1154
1155 #[inline]
1156 fn rem(self, other: u64) -> BigUint {
1157 let (_, r) = div_rem(self, From::from(other));
1158 r
1159 }
1160}
1161impl RemAssign<u64> for BigUint {
1162 #[inline]
1163 fn rem_assign(&mut self, other: u64) {
1164 *self = &*self % other;
1165 }
1166}
1167
1168impl Rem<BigUint> for u64 {
1169 type Output = BigUint;
1170
1171 #[inline]
1172 fn rem(mut self, other: BigUint) -> BigUint {
1173 self %= other;
1174 From::from(self)
1175 }
1176}
1177
1178#[cfg(has_i128)]
1179impl Rem<u128> for BigUint {
1180 type Output = BigUint;
1181
1182 #[inline]
1183 fn rem(self, other: u128) -> BigUint {
1184 let (_, r) = div_rem(self, From::from(other));
1185 r
1186 }
1187}
1188#[cfg(has_i128)]
1189impl RemAssign<u128> for BigUint {
1190 #[inline]
1191 fn rem_assign(&mut self, other: u128) {
1192 *self = &*self % other;
1193 }
1194}
1195
1196#[cfg(has_i128)]
1197impl Rem<BigUint> for u128 {
1198 type Output = BigUint;
1199
1200 #[inline]
1201 fn rem(mut self, other: BigUint) -> BigUint {
1202 self %= other;
1203 From::from(self)
1204 }
1205}
1206
1207impl Neg for BigUint {
1208 type Output = BigUint;
1209
1210 #[inline]
1211 fn neg(self) -> BigUint {
1212 panic!()
1213 }
1214}
1215
1216impl<'a> Neg for &'a BigUint {
1217 type Output = BigUint;
1218
1219 #[inline]
1220 fn neg(self) -> BigUint {
1221 panic!()
1222 }
1223}
1224
1225impl CheckedAdd for BigUint {
1226 #[inline]
1227 fn checked_add(&self, v: &BigUint) -> Option<BigUint> {
1228 Some(self.add(v))
1229 }
1230}
1231
1232impl CheckedSub for BigUint {
1233 #[inline]
1234 fn checked_sub(&self, v: &BigUint) -> Option<BigUint> {
1235 match self.cmp(v) {
1236 Less => None,
1237 Equal => Some(Zero::zero()),
1238 Greater => Some(self.sub(v)),
1239 }
1240 }
1241}
1242
1243impl CheckedMul for BigUint {
1244 #[inline]
1245 fn checked_mul(&self, v: &BigUint) -> Option<BigUint> {
1246 Some(self.mul(v))
1247 }
1248}
1249
1250impl CheckedDiv for BigUint {
1251 #[inline]
1252 fn checked_div(&self, v: &BigUint) -> Option<BigUint> {
1253 if v.is_zero() {
1254 return None;
1255 }
1256 Some(self.div(v))
1257 }
1258}
1259
1260impl Integer for BigUint {
1261 #[inline]
1262 fn div_rem(&self, other: &BigUint) -> (BigUint, BigUint) {
1263 div_rem_ref(self, other)
1264 }
1265
1266 #[inline]
1267 fn div_floor(&self, other: &BigUint) -> BigUint {
1268 let (d, _) = div_rem_ref(self, other);
1269 d
1270 }
1271
1272 #[inline]
1273 fn mod_floor(&self, other: &BigUint) -> BigUint {
1274 let (_, m) = div_rem_ref(self, other);
1275 m
1276 }
1277
1278 #[inline]
1279 fn div_mod_floor(&self, other: &BigUint) -> (BigUint, BigUint) {
1280 div_rem_ref(self, other)
1281 }
1282
1283 #[inline]
1287 fn gcd(&self, other: &Self) -> Self {
1288 #[inline]
1289 fn twos(x: &BigUint) -> usize {
1290 trailing_zeros(x).unwrap_or(0)
1291 }
1292
1293 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 let shift = cmp::min(twos(&n), twos(&m));
1305
1306 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 #[inline]
1323 fn lcm(&self, other: &BigUint) -> BigUint {
1324 if self.is_zero() && other.is_zero() {
1325 Self::zero()
1326 } else {
1327 self / self.gcd(other) * other
1328 }
1329 }
1330
1331 #[inline]
1333 fn divides(&self, other: &BigUint) -> bool {
1334 self.is_multiple_of(other)
1335 }
1336
1337 #[inline]
1339 fn is_multiple_of(&self, other: &BigUint) -> bool {
1340 (self % other).is_zero()
1341 }
1342
1343 #[inline]
1345 fn is_even(&self) -> bool {
1346 match self.data.first() {
1348 Some(x) => x.is_even(),
1349 None => true,
1350 }
1351 }
1352
1353 #[inline]
1355 fn is_odd(&self) -> bool {
1356 !self.is_even()
1357 }
1358}
1359
1360#[inline]
1361fn fixpoint<F>(mut x: BigUint, max_bits: usize, f: F) -> BigUint
1362where
1363 F: Fn(&BigUint) -> BigUint,
1364{
1365 let mut xn = f(&x);
1366
1367 while x < xn {
1370 x = if xn.bits() > max_bits {
1374 BigUint::one() << max_bits
1375 } else {
1376 xn
1377 };
1378 xn = f(&x);
1379 }
1380
1381 while x > xn {
1383 x = xn;
1384 xn = f(&x);
1385 }
1386 x
1387}
1388
1389impl Roots for BigUint {
1390 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 1 => return self.clone(),
1405 2 => return self.sqrt(),
1406 3 => return self.cbrt(),
1407 _ => (),
1408 }
1409
1410 let bits = self.bits();
1412 if bits <= n as usize {
1413 return BigUint::one();
1414 }
1415
1416 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 BigUint::from_f64((f.ln() / f64::from(n)).exp()).unwrap()
1426 } else {
1427 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 fn sqrt(&self) -> Self {
1451 if self.is_zero() || self.is_one() {
1452 return self.clone();
1453 }
1454
1455 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 BigUint::from_f64(f.sqrt()).unwrap()
1466 } else {
1467 let extra_bits = bits - (f64::MAX_EXP as usize - 1);
1470 let root_scale = (extra_bits + 1) / 2;
1471 let scale = root_scale * 2;
1472 (self >> scale).sqrt() << root_scale
1473 };
1474
1475 fixpoint(guess, max_bits, move |s| {
1476 let q = self / s;
1477 let t = s + q;
1478 t >> 1
1479 })
1480 }
1481
1482 fn cbrt(&self) -> Self {
1483 if self.is_zero() || self.is_one() {
1484 return self.clone();
1485 }
1486
1487 if 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 BigUint::from_f64(f.cbrt()).unwrap()
1498 } else {
1499 let extra_bits = bits - (f64::MAX_EXP as usize - 1);
1502 let root_scale = (extra_bits + 2) / 3;
1503 let scale = root_scale * 3;
1504 (self >> scale).cbrt() << root_scale
1505 };
1506
1507 fixpoint(guess, max_bits, move |s| {
1508 let q = self / (s * s);
1509 let t = (s << 1) + q;
1510 t / 3u32
1511 })
1512 }
1513}
1514
1515fn high_bits_to_u64(v: &BigUint) -> u64 {
1516 match v.data.len() {
1517 0 => 0,
1518 1 => u64::from(v.data[0]),
1519 _ => {
1520 let mut bits = v.bits();
1521 let mut ret = 0u64;
1522 let mut ret_bits = 0;
1523
1524 for d in v.data.iter().rev() {
1525 let digit_bits = (bits - 1) % big_digit::BITS + 1;
1526 let bits_want = cmp::min(64 - ret_bits, digit_bits);
1527
1528 if bits_want != 64 {
1529 ret <<= bits_want;
1530 }
1531 ret |= u64::from(*d) >> (digit_bits - bits_want);
1532 ret_bits += bits_want;
1533 bits -= bits_want;
1534
1535 if ret_bits == 64 {
1536 break;
1537 }
1538 }
1539
1540 ret
1541 }
1542 }
1543}
1544
1545impl ToPrimitive for BigUint {
1546 #[inline]
1547 fn to_i64(&self) -> Option<i64> {
1548 self.to_u64().as_ref().and_then(u64::to_i64)
1549 }
1550
1551 #[inline]
1552 #[cfg(has_i128)]
1553 fn to_i128(&self) -> Option<i128> {
1554 self.to_u128().as_ref().and_then(u128::to_i128)
1555 }
1556
1557 #[inline]
1558 fn to_u64(&self) -> Option<u64> {
1559 let mut ret: u64 = 0;
1560 let mut bits = 0;
1561
1562 for i in self.data.iter() {
1563 if bits >= 64 {
1564 return None;
1565 }
1566
1567 ret += u64::from(*i) << bits;
1568 bits += big_digit::BITS;
1569 }
1570
1571 Some(ret)
1572 }
1573
1574 #[inline]
1575 #[cfg(has_i128)]
1576 fn to_u128(&self) -> Option<u128> {
1577 let mut ret: u128 = 0;
1578 let mut bits = 0;
1579
1580 for i in self.data.iter() {
1581 if bits >= 128 {
1582 return None;
1583 }
1584
1585 ret |= u128::from(*i) << bits;
1586 bits += big_digit::BITS;
1587 }
1588
1589 Some(ret)
1590 }
1591
1592 #[inline]
1593 fn to_f32(&self) -> Option<f32> {
1594 let mantissa = high_bits_to_u64(self);
1595 let exponent = self.bits() - fls(mantissa);
1596
1597 if exponent > f32::MAX_EXP as usize {
1598 None
1599 } else {
1600 let ret = (mantissa as f32) * 2.0f32.powi(exponent as i32);
1601 if ret.is_infinite() {
1602 None
1603 } else {
1604 Some(ret)
1605 }
1606 }
1607 }
1608
1609 #[inline]
1610 fn to_f64(&self) -> Option<f64> {
1611 let mantissa = high_bits_to_u64(self);
1612 let exponent = self.bits() - fls(mantissa);
1613
1614 if exponent > f64::MAX_EXP as usize {
1615 None
1616 } else {
1617 let ret = (mantissa as f64) * 2.0f64.powi(exponent as i32);
1618 if ret.is_infinite() {
1619 None
1620 } else {
1621 Some(ret)
1622 }
1623 }
1624 }
1625}
1626
1627impl FromPrimitive for BigUint {
1628 #[inline]
1629 fn from_i64(n: i64) -> Option<BigUint> {
1630 if n >= 0 {
1631 Some(BigUint::from(n as u64))
1632 } else {
1633 None
1634 }
1635 }
1636
1637 #[inline]
1638 #[cfg(has_i128)]
1639 fn from_i128(n: i128) -> Option<BigUint> {
1640 if n >= 0 {
1641 Some(BigUint::from(n as u128))
1642 } else {
1643 None
1644 }
1645 }
1646
1647 #[inline]
1648 fn from_u64(n: u64) -> Option<BigUint> {
1649 Some(BigUint::from(n))
1650 }
1651
1652 #[inline]
1653 #[cfg(has_i128)]
1654 fn from_u128(n: u128) -> Option<BigUint> {
1655 Some(BigUint::from(n))
1656 }
1657
1658 #[inline]
1659 fn from_f64(mut n: f64) -> Option<BigUint> {
1660 if !n.is_finite() {
1662 return None;
1663 }
1664
1665 n = n.trunc();
1667
1668 if n.is_zero() {
1670 return Some(BigUint::zero());
1671 }
1672
1673 let (mantissa, exponent, sign) = Float::integer_decode(n);
1674
1675 if sign == -1 {
1676 return None;
1677 }
1678
1679 let mut ret = BigUint::from(mantissa);
1680 if exponent > 0 {
1681 ret <<= exponent as usize;
1682 } else if exponent < 0 {
1683 ret >>= (-exponent) as usize;
1684 }
1685 Some(ret)
1686 }
1687}
1688
1689impl From<u64> for BigUint {
1690 #[inline]
1691 fn from(mut n: u64) -> Self {
1692 let mut ret: BigUint = Zero::zero();
1693
1694 while n != 0 {
1695 ret.data.push(n as BigDigit);
1696 n = (n >> 1) >> (big_digit::BITS - 1);
1698 }
1699
1700 ret
1701 }
1702}
1703
1704#[cfg(has_i128)]
1705impl From<u128> for BigUint {
1706 #[inline]
1707 fn from(mut n: u128) -> Self {
1708 let mut ret: BigUint = Zero::zero();
1709
1710 while n != 0 {
1711 ret.data.push(n as BigDigit);
1712 n >>= big_digit::BITS;
1713 }
1714
1715 ret
1716 }
1717}
1718
1719macro_rules! impl_biguint_from_uint {
1720 ($T:ty) => {
1721 impl From<$T> for BigUint {
1722 #[inline]
1723 fn from(n: $T) -> Self {
1724 BigUint::from(n as u64)
1725 }
1726 }
1727 };
1728}
1729
1730impl_biguint_from_uint!(u8);
1731impl_biguint_from_uint!(u16);
1732impl_biguint_from_uint!(u32);
1733impl_biguint_from_uint!(usize);
1734
1735pub trait ToBigUint {
1737 fn to_biguint(&self) -> Option<BigUint>;
1739}
1740
1741impl ToBigUint for BigUint {
1742 #[inline]
1743 fn to_biguint(&self) -> Option<BigUint> {
1744 Some(self.clone())
1745 }
1746}
1747
1748macro_rules! impl_to_biguint {
1749 ($T:ty, $from_ty:path) => {
1750 impl ToBigUint for $T {
1751 #[inline]
1752 fn to_biguint(&self) -> Option<BigUint> {
1753 $from_ty(*self)
1754 }
1755 }
1756 };
1757}
1758
1759impl_to_biguint!(isize, FromPrimitive::from_isize);
1760impl_to_biguint!(i8, FromPrimitive::from_i8);
1761impl_to_biguint!(i16, FromPrimitive::from_i16);
1762impl_to_biguint!(i32, FromPrimitive::from_i32);
1763impl_to_biguint!(i64, FromPrimitive::from_i64);
1764#[cfg(has_i128)]
1765impl_to_biguint!(i128, FromPrimitive::from_i128);
1766
1767impl_to_biguint!(usize, FromPrimitive::from_usize);
1768impl_to_biguint!(u8, FromPrimitive::from_u8);
1769impl_to_biguint!(u16, FromPrimitive::from_u16);
1770impl_to_biguint!(u32, FromPrimitive::from_u32);
1771impl_to_biguint!(u64, FromPrimitive::from_u64);
1772#[cfg(has_i128)]
1773impl_to_biguint!(u128, FromPrimitive::from_u128);
1774
1775impl_to_biguint!(f32, FromPrimitive::from_f32);
1776impl_to_biguint!(f64, FromPrimitive::from_f64);
1777
1778fn 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
1804fn 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 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#[inline(always)] fn to_radix_digits_le(u: &BigUint, radix: u32) -> Vec<u8> {
1846 debug_assert!(!u.is_zero() && !radix.is_power_of_two());
1847
1848 let radix_digits = ((u.bits() as f64) / f64::from(radix).log2()).ceil();
1850 let mut res = Vec::with_capacity(radix_digits as usize);
1851 let mut digits = u.clone();
1852
1853 let (base, power) = get_radix_base(radix);
1854 let radix = radix as BigDigit;
1855
1856 while digits.data.len() > 1 {
1857 let (q, mut r) = div_rem_digit(digits, base);
1858 for _ in 0..power {
1859 res.push((r % radix) as u8);
1860 r /= radix;
1861 }
1862 digits = q;
1863 }
1864
1865 let mut r = digits.data[0];
1866 while r != 0 {
1867 res.push((r % radix) as u8);
1868 r /= radix;
1869 }
1870
1871 res
1872}
1873
1874pub fn to_radix_le(u: &BigUint, radix: u32) -> Vec<u8> {
1875 if u.is_zero() {
1876 vec![0]
1877 } else if radix.is_power_of_two() {
1878 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 to_radix_digits_le(u, 10)
1889 } else {
1890 to_radix_digits_le(u, radix)
1891 }
1892}
1893
1894pub fn to_str_radix_reversed(u: &BigUint, radix: u32) -> Vec<u8> {
1895 assert!(2 <= radix && radix <= 36, "The radix must be within 2...36");
1896
1897 if u.is_zero() {
1898 return vec![b'0'];
1899 }
1900
1901 let mut res = to_radix_le(u, radix);
1902
1903 for r in &mut res {
1905 debug_assert!(u32::from(*r) < radix);
1906 if *r < 10 {
1907 *r += b'0';
1908 } else {
1909 *r += b'a' - 10;
1910 }
1911 }
1912 res
1913}
1914
1915impl BigUint {
1916 #[inline]
1920 pub fn new(digits: Vec<u32>) -> BigUint {
1921 BigUint { data: digits }.normalized()
1922 }
1923
1924 #[inline]
1928 pub fn from_slice(slice: &[u32]) -> BigUint {
1929 BigUint::new(slice.to_vec())
1930 }
1931
1932 #[inline]
1936 pub fn assign_from_slice(&mut self, slice: &[u32]) {
1937 self.data.resize(slice.len(), 0);
1938 self.data.clone_from_slice(slice);
1939 self.normalize();
1940 }
1941
1942 #[inline]
1961 pub fn from_bytes_be(bytes: &[u8]) -> BigUint {
1962 if bytes.is_empty() {
1963 Zero::zero()
1964 } else {
1965 let mut v = bytes.to_vec();
1966 v.reverse();
1967 BigUint::from_bytes_le(&*v)
1968 }
1969 }
1970
1971 #[inline]
1975 pub fn from_bytes_le(bytes: &[u8]) -> BigUint {
1976 if bytes.is_empty() {
1977 Zero::zero()
1978 } else {
1979 from_bitwise_digits_le(bytes, 8)
1980 }
1981 }
1982
1983 #[inline]
2000 pub fn parse_bytes(buf: &[u8], radix: u32) -> Option<BigUint> {
2001 str::from_utf8(buf)
2002 .ok()
2003 .and_then(|s| BigUint::from_str_radix(s, radix).ok())
2004 }
2005
2006 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 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 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 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 #[inline]
2103 pub fn to_bytes_be(&self) -> Vec<u8> {
2104 let mut v = self.to_bytes_le();
2105 v.reverse();
2106 v
2107 }
2108
2109 #[inline]
2120 pub fn to_bytes_le(&self) -> Vec<u8> {
2121 if self.is_zero() {
2122 vec![0]
2123 } else {
2124 to_bitwise_digits_le(self, 8)
2125 }
2126 }
2127
2128 #[inline]
2142 pub fn to_u32_digits(&self) -> Vec<u32> {
2143 self.data.clone()
2144 }
2145
2146 #[inline]
2158 pub fn to_str_radix(&self, radix: u32) -> String {
2159 let mut v = to_str_radix_reversed(self, radix);
2160 v.reverse();
2161 unsafe { String::from_utf8_unchecked(v) }
2162 }
2163
2164 #[inline]
2179 pub fn to_radix_be(&self, radix: u32) -> Vec<u8> {
2180 let mut v = to_radix_le(self, radix);
2181 v.reverse();
2182 v
2183 }
2184
2185 #[inline]
2200 pub fn to_radix_le(&self, radix: u32) -> Vec<u8> {
2201 to_radix_le(self, radix)
2202 }
2203
2204 #[inline]
2206 pub fn bits(&self) -> usize {
2207 if self.is_zero() {
2208 return 0;
2209 }
2210 let zeros = self.data.last().unwrap().leading_zeros();
2211 self.data.len() * big_digit::BITS - zeros as usize
2212 }
2213
2214 #[inline]
2217 fn normalize(&mut self) {
2218 while let Some(&0) = self.data.last() {
2219 self.data.pop();
2220 }
2221 }
2222
2223 #[inline]
2225 fn normalized(mut self) -> BigUint {
2226 self.normalize();
2227 self
2228 }
2229
2230 pub fn modpow(&self, exponent: &Self, modulus: &Self) -> Self {
2234 assert!(!modulus.is_zero(), "divide by zero!");
2235
2236 if modulus.is_odd() {
2237 monty_modpow(self, exponent, modulus)
2239 } else {
2240 plain_modpow(self, &exponent.data, modulus)
2242 }
2243 }
2244
2245 pub fn sqrt(&self) -> Self {
2248 Roots::sqrt(self)
2249 }
2250
2251 pub fn cbrt(&self) -> Self {
2254 Roots::cbrt(self)
2255 }
2256
2257 pub fn nth_root(&self, n: u32) -> Self {
2260 Roots::nth_root(self, n)
2261 }
2262}
2263
2264fn plain_modpow(base: &BigUint, exp_data: &[BigDigit], modulus: &BigUint) -> BigUint {
2265 assert!(!modulus.is_zero(), "divide by zero!");
2266
2267 let i = match exp_data.iter().position(|&r| r != 0) {
2268 None => return BigUint::one(),
2269 Some(i) => i,
2270 };
2271
2272 let mut base = base % modulus;
2273 for _ in 0..i {
2274 for _ in 0..big_digit::BITS {
2275 base = &base * &base % modulus;
2276 }
2277 }
2278
2279 let mut r = exp_data[i];
2280 let mut b = 0usize;
2281 while r.is_even() {
2282 base = &base * &base % modulus;
2283 r >>= 1;
2284 b += 1;
2285 }
2286
2287 let mut exp_iter = exp_data[i + 1..].iter();
2288 if exp_iter.len() == 0 && r.is_one() {
2289 return base;
2290 }
2291
2292 let mut acc = base.clone();
2293 r >>= 1;
2294 b += 1;
2295
2296 {
2297 let mut unit = |exp_is_odd| {
2298 base = &base * &base % modulus;
2299 if exp_is_odd {
2300 acc = &acc * &base % modulus;
2301 }
2302 };
2303
2304 if let Some(&last) = exp_iter.next_back() {
2305 for _ in b..big_digit::BITS {
2307 unit(r.is_odd());
2308 r >>= 1;
2309 }
2310
2311 for &r in exp_iter {
2313 let mut r = r;
2314 for _ in 0..big_digit::BITS {
2315 unit(r.is_odd());
2316 r >>= 1;
2317 }
2318 }
2319 r = last;
2320 }
2321
2322 debug_assert_ne!(r, 0);
2323 while !r.is_zero() {
2324 unit(r.is_odd());
2325 r >>= 1;
2326 }
2327 }
2328 acc
2329}
2330
2331#[test]
2332fn test_plain_modpow() {
2333 let two = BigUint::from(2u32);
2334 let modulus = BigUint::from(0x1100u32);
2335
2336 let exp = vec![0, 0b1];
2337 assert_eq!(
2338 two.pow(0b1_00000000_u32) % &modulus,
2339 plain_modpow(&two, &exp, &modulus)
2340 );
2341 let exp = vec![0, 0b10];
2342 assert_eq!(
2343 two.pow(0b10_00000000_u32) % &modulus,
2344 plain_modpow(&two, &exp, &modulus)
2345 );
2346 let exp = vec![0, 0b110010];
2347 assert_eq!(
2348 two.pow(0b110010_00000000_u32) % &modulus,
2349 plain_modpow(&two, &exp, &modulus)
2350 );
2351 let exp = vec![0b1, 0b1];
2352 assert_eq!(
2353 two.pow(0b1_00000001_u32) % &modulus,
2354 plain_modpow(&two, &exp, &modulus)
2355 );
2356 let exp = vec![0b1100, 0, 0b1];
2357 assert_eq!(
2358 two.pow(0b1_00000000_00001100_u32) % &modulus,
2359 plain_modpow(&two, &exp, &modulus)
2360 );
2361}
2362
2363pub fn trailing_zeros(u: &BigUint) -> Option<usize> {
2366 u.data
2367 .iter()
2368 .enumerate()
2369 .find(|&(_, &digit)| digit != 0)
2370 .map(|(i, digit)| i * big_digit::BITS + digit.trailing_zeros() as usize)
2371}
2372
2373impl_sum_iter_type!(BigUint);
2374impl_product_iter_type!(BigUint);
2375
2376pub trait IntDigits {
2377 fn digits(&self) -> &[BigDigit];
2378 fn digits_mut(&mut self) -> &mut Vec<BigDigit>;
2379 fn normalize(&mut self);
2380 fn capacity(&self) -> usize;
2381 fn len(&self) -> usize;
2382}
2383
2384impl IntDigits for BigUint {
2385 #[inline]
2386 fn digits(&self) -> &[BigDigit] {
2387 &self.data
2388 }
2389 #[inline]
2390 fn digits_mut(&mut self) -> &mut Vec<BigDigit> {
2391 &mut self.data
2392 }
2393 #[inline]
2394 fn normalize(&mut self) {
2395 self.normalize();
2396 }
2397 #[inline]
2398 fn capacity(&self) -> usize {
2399 self.data.capacity()
2400 }
2401 #[inline]
2402 fn len(&self) -> usize {
2403 self.data.len()
2404 }
2405}
2406
2407#[cfg(has_i128)]
2409#[inline]
2410fn u32_to_u128(a: u32, b: u32, c: u32, d: u32) -> u128 {
2411 u128::from(d) | (u128::from(c) << 32) | (u128::from(b) << 64) | (u128::from(a) << 96)
2412}
2413
2414#[cfg(has_i128)]
2416#[inline]
2417fn u32_from_u128(n: u128) -> (u32, u32, u32, u32) {
2418 (
2419 (n >> 96) as u32,
2420 (n >> 64) as u32,
2421 (n >> 32) as u32,
2422 n as u32,
2423 )
2424}
2425
2426#[cfg(feature = "serde")]
2427impl serde::Serialize for BigUint {
2428 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
2429 where
2430 S: serde::Serializer,
2431 {
2432 let data: &Vec<u32> = &self.data;
2436 data.serialize(serializer)
2437 }
2438}
2439
2440#[cfg(feature = "serde")]
2441impl<'de> serde::Deserialize<'de> for BigUint {
2442 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
2443 where
2444 D: serde::Deserializer<'de>,
2445 {
2446 let data: Vec<u32> = Vec::deserialize(deserializer)?;
2447 Ok(BigUint::new(data))
2448 }
2449}
2450
2451#[inline]
2453fn get_radix_base(radix: u32) -> (BigDigit, usize) {
2454 debug_assert!(
2455 2 <= radix && radix <= 256,
2456 "The radix must be within 2...256"
2457 );
2458 debug_assert!(!radix.is_power_of_two());
2459
2460 match big_digit::BITS {
2488 32 => {
2489 const BASES: [(u32, usize); 257] = [
2490 (0, 0),
2491 (0, 0),
2492 (0, 0), (3486784401, 20), (0, 0), (1220703125, 13), (2176782336, 12), (1977326743, 11), (0, 0), (3486784401, 10), (1000000000, 9), (2357947691, 9), (429981696, 8), (815730721, 8), (1475789056, 8), (2562890625, 8), (0, 0), (410338673, 7), (612220032, 7), (893871739, 7), (1280000000, 7), (1801088541, 7), (2494357888, 7), (3404825447, 7), (191102976, 6), (244140625, 6), (308915776, 6), (387420489, 6), (481890304, 6), (594823321, 6), (729000000, 6), (887503681, 6), (0, 0), (1291467969, 6), (1544804416, 6), (1838265625, 6), (2176782336, 6), (2565726409, 6), (3010936384, 6), (3518743761, 6), (4096000000, 6), (115856201, 5), (130691232, 5), (147008443, 5), (164916224, 5), (184528125, 5), (205962976, 5), (229345007, 5), (254803968, 5), (282475249, 5), (312500000, 5), (345025251, 5), (380204032, 5), (418195493, 5), (459165024, 5), (503284375, 5), (550731776, 5), (601692057, 5), (656356768, 5), (714924299, 5), (777600000, 5), (844596301, 5), (916132832, 5), (992436543, 5), (0, 0), (1160290625, 5), (1252332576, 5), (1350125107, 5), (1453933568, 5), (1564031349, 5), (1680700000, 5), (1804229351, 5), (1934917632, 5), (2073071593, 5), (2219006624, 5), (2373046875, 5), (2535525376, 5), (2706784157, 5), (2887174368, 5), (3077056399, 5), (3276800000, 5), (3486784401, 5), (3707398432, 5), (3939040643, 5), (4182119424, 5), (52200625, 4), (54700816, 4), (57289761, 4), (59969536, 4), (62742241, 4), (65610000, 4), (68574961, 4), (71639296, 4), (74805201, 4), (78074896, 4), (81450625, 4), (84934656, 4), (88529281, 4), (92236816, 4), (96059601, 4), (100000000, 4), (104060401, 4), (108243216, 4), (112550881, 4), (116985856, 4), (121550625, 4), (126247696, 4), (131079601, 4), (136048896, 4), (141158161, 4), (146410000, 4), (151807041, 4), (157351936, 4), (163047361, 4), (168896016, 4), (174900625, 4), (181063936, 4), (187388721, 4), (193877776, 4), (200533921, 4), (207360000, 4), (214358881, 4), (221533456, 4), (228886641, 4), (236421376, 4), (244140625, 4), (252047376, 4), (260144641, 4), (0, 0), (276922881, 4), (285610000, 4), (294499921, 4), (303595776, 4), (312900721, 4), (322417936, 4), (332150625, 4), (342102016, 4), (352275361, 4), (362673936, 4), (373301041, 4), (384160000, 4), (395254161, 4), (406586896, 4), (418161601, 4), (429981696, 4), (442050625, 4), (454371856, 4), (466948881, 4), (479785216, 4), (492884401, 4), (506250000, 4), (519885601, 4), (533794816, 4), (547981281, 4), (562448656, 4), (577200625, 4), (592240896, 4), (607573201, 4), (623201296, 4), (639128961, 4), (655360000, 4), (671898241, 4), (688747536, 4), (705911761, 4), (723394816, 4), (741200625, 4), (759333136, 4), (777796321, 4), (796594176, 4), (815730721, 4), (835210000, 4), (855036081, 4), (875213056, 4), (895745041, 4), (916636176, 4), (937890625, 4), (959512576, 4), (981506241, 4), (1003875856, 4), (1026625681, 4), (1049760000, 4), (1073283121, 4), (1097199376, 4), (1121513121, 4), (1146228736, 4), (1171350625, 4), (1196883216, 4), (1222830961, 4), (1249198336, 4), (1275989841, 4), (1303210000, 4), (1330863361, 4), (1358954496, 4), (1387488001, 4), (1416468496, 4), (1445900625, 4), (1475789056, 4), (1506138481, 4), (1536953616, 4), (1568239201, 4), (1600000000, 4), (1632240801, 4), (1664966416, 4), (1698181681, 4), (1731891456, 4), (1766100625, 4), (1800814096, 4), (1836036801, 4), (1871773696, 4), (1908029761, 4), (1944810000, 4), (1982119441, 4), (2019963136, 4), (2058346161, 4), (2097273616, 4), (2136750625, 4), (2176782336, 4), (2217373921, 4), (2258530576, 4), (2300257521, 4), (2342560000, 4), (2385443281, 4), (2428912656, 4), (2472973441, 4), (2517630976, 4), (2562890625, 4), (2608757776, 4), (2655237841, 4), (2702336256, 4), (2750058481, 4), (2798410000, 4), (2847396321, 4), (2897022976, 4), (2947295521, 4), (2998219536, 4), (3049800625, 4), (3102044416, 4), (3154956561, 4), (3208542736, 4), (3262808641, 4), (3317760000, 4), (3373402561, 4), (3429742096, 4), (3486784401, 4), (3544535296, 4), (3603000625, 4), (3662186256, 4), (3722098081, 4), (3782742016, 4), (3844124001, 4), (3906250000, 4), (3969126001, 4), (4032758016, 4), (4097152081, 4), (4162314256, 4), (4228250625, 4), (0, 0), ];
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), (12157665459056928801, 40), (4611686018427387904, 31), (7450580596923828125, 27), (4738381338321616896, 24), (3909821048582988049, 22), (9223372036854775808, 21), (12157665459056928801, 20), (10000000000000000000, 19), (5559917313492231481, 18), (2218611106740436992, 17), (8650415919381337933, 17), (2177953337809371136, 16), (6568408355712890625, 16), (1152921504606846976, 15), (2862423051509815793, 15), (6746640616477458432, 15), (15181127029874798299, 15), (1638400000000000000, 14), (3243919932521508681, 14), (6221821273427820544, 14), (11592836324538749809, 14), (876488338465357824, 13), (1490116119384765625, 13), (2481152873203736576, 13), (4052555153018976267, 13), (6502111422497947648, 13), (10260628712958602189, 13), (15943230000000000000, 13), (787662783788549761, 12), (1152921504606846976, 12), (1667889514952984961, 12), (2386420683693101056, 12), (3379220508056640625, 12), (4738381338321616896, 12), (6582952005840035281, 12), (9065737908494995456, 12), (12381557655576425121, 12), (16777216000000000000, 12), (550329031716248441, 11), (717368321110468608, 11), (929293739471222707, 11), (1196683881290399744, 11), (1532278301220703125, 11), (1951354384207722496, 11), (2472159215084012303, 11), (3116402981210161152, 11), (3909821048582988049, 11), (4882812500000000000, 11), (6071163615208263051, 11), (7516865509350965248, 11), (9269035929372191597, 11), (11384956040305711104, 11), (13931233916552734375, 11), (16985107389382393856, 11), (362033331456891249, 10), (430804206899405824, 10), (511116753300641401, 10), (604661760000000000, 10), (713342911662882601, 10), (839299365868340224, 10), (984930291881790849, 10), (1152921504606846976, 10), (1346274334462890625, 10), (1568336880910795776, 10), (1822837804551761449, 10), (2113922820157210624, 10), (2446194060654759801, 10), (2824752490000000000, 10), (3255243551009881201, 10), (3743906242624487424, 10), (4297625829703557649, 10), (4923990397355877376, 10), (5631351470947265625, 10), (6428888932339941376, 10), (7326680472586200649, 10), (8335775831236199424, 10), (9468276082626847201, 10), (10737418240000000000, 10), (12157665459056928801, 10), (13744803133596058624, 10), (15516041187205853449, 10), (17490122876598091776, 10), (231616946283203125, 9), (257327417311663616, 9), (285544154243029527, 9), (316478381828866048, 9), (350356403707485209, 9), (387420489000000000, 9), (427929800129788411, 9), (472161363286556672, 9), (520411082988487293, 9), (572994802228616704, 9), (630249409724609375, 9), (692533995824480256, 9), (760231058654565217, 9), (833747762130149888, 9), (913517247483640899, 9), (1000000000000000000, 9), (1093685272684360901, 9), (1195092568622310912, 9), (1304773183829244583, 9), (1423311812421484544, 9), (1551328215978515625, 9), (1689478959002692096, 9), (1838459212420154507, 9), (1999004627104432128, 9), (2171893279442309389, 9), (2357947691000000000, 9), (2558036924386500591, 9), (2773078757450186752, 9), (3004041937984268273, 9), (3251948521156637184, 9), (3517876291919921875, 9), (3802961274698203136, 9), (4108400332687853397, 9), (4435453859151328768, 9), (4785448563124474679, 9), (5159780352000000000, 9), (5559917313492231481, 9), (5987402799531080192, 9), (6443858614676334363, 9), (6930988311686938624, 9), (7450580596923828125, 9), (8004512848309157376, 9), (8594754748609397887, 9), (9223372036854775808, 9), (9892530380752880769, 9), (10604499373000000000, 9), (11361656654439817571, 9), (12166492167065567232, 9), (13021612539908538853, 9), (13929745610903012864, 9), (14893745087865234375, 9), (15916595351771938816, 9), (17001416405572203977, 9), (18151468971815029248, 9), (139353667211683681, 8), (147578905600000000, 8), (156225851787813921, 8), (165312903998914816, 8), (174859124550883201, 8), (184884258895036416, 8), (195408755062890625, 8), (206453783524884736, 8), (218041257467152161, 8), (230193853492166656, 8), (242935032749128801, 8), (256289062500000000, 8), (270281038127131201, 8), (284936905588473856, 8), (300283484326400961, 8), (316348490636206336, 8), (333160561500390625, 8), (350749278894882816, 8), (369145194573386401, 8), (388379855336079616, 8), (408485828788939521, 8), (429496729600000000, 8), (451447246258894081, 8), (474373168346071296, 8), (498311414318121121, 8), (523300059815673856, 8), (549378366500390625, 8), (576586811427594496, 8), (604967116961135041, 8), (634562281237118976, 8), (665416609183179841, 8), (697575744100000000, 8), (731086699811838561, 8), (765997893392859136, 8), (802359178476091681, 8), (840221879151902976, 8), (879638824462890625, 8), (920664383502155776, 8), (963354501121950081, 8), (1007766734259732736, 8), (1053960288888713761, 8), (1101996057600000000, 8), (1151936657823500641, 8), (1203846470694789376, 8), (1257791680575160641, 8), (1313840315232157696, 8), (1372062286687890625, 8), (1432529432742502656, 8), (1495315559180183521, 8), (1560496482665168896, 8), (1628150074335205281, 8), (1698356304100000000, 8), (1771197285652216321, 8), (1846757322198614016, 8), (1925122952918976001, 8), (2006383000160502016, 8), (2090628617375390625, 8), (2177953337809371136, 8), (2268453123948987361, 8), (2362226417735475456, 8), (2459374191553118401, 8), (2560000000000000000, 8), (2664210032449121601, 8), (2772113166407885056, 8), (2883821021683985761, 8), (2999448015365799936, 8), (3119111417625390625, 8), (3242931408352297216, 8), (3371031134626313601, 8), (3503536769037500416, 8), (3640577568861717121, 8), (3782285936100000000, 8), (3928797478390152481, 8), (4080251070798954496, 8), (4236788918503437921, 8), (4398556620369715456, 8), (4565703233437890625, 8), (4738381338321616896, 8), (4916747105530914241, 8), (5100960362726891776, 8), (5291184662917065441, 8), (5487587353600000000, 8), (5690339646868044961, 8), (5899616690476974336, 8), (6115597639891380481, 8), (6338465731314712576, 8), (6568408355712890625, 8), (6805617133840466176, 8), (7050287992278341281, 8), (7302621240492097536, 8), (7562821648920027361, 8), (7831098528100000000, 8), (8107665808844335041, 8), (8392742123471896576, 8), (8686550888106661441, 8), (8989320386052055296, 8), (9301283852250390625, 8), (9622679558836781056, 8), (9953750901796946721, 8), (10294746488738365696, 8), (10645920227784266881, 8), (11007531417600000000, 8), (11379844838561358721, 8), (11763130845074473216, 8), (12157665459056928801, 8), (12563730464589807616, 8), (12981613503750390625, 8), (13411608173635297536, 8), (13854014124583882561, 8), (14309137159611744256, 8), (14777289335064248001, 8), (15258789062500000000, 8), (15753961211814252001, 8), (16263137215612256256, 8), (16786655174842630561, 8), (17324859965700833536, 8), (17878103347812890625, 8), (72057594037927936, 7), ];
3012
3013 let (base, power) = BASES[radix as usize];
3014 (base as BigDigit, power)
3015 }
3016 _ => panic!("Invalid bigdigit size"),
3017 }
3018}
3019
3020#[test]
3021fn test_from_slice() {
3022 fn check(slice: &[BigDigit], data: &[BigDigit]) {
3023 assert!(BigUint::from_slice(slice).data == data);
3024 }
3025 check(&[1], &[1]);
3026 check(&[0, 0, 0], &[]);
3027 check(&[1, 2, 0, 0], &[1, 2]);
3028 check(&[0, 0, 1, 2], &[0, 0, 1, 2]);
3029 check(&[0, 0, 1, 2, 0, 0], &[0, 0, 1, 2]);
3030 check(&[-1i32 as BigDigit], &[-1i32 as BigDigit]);
3031}
3032
3033#[test]
3034fn test_assign_from_slice() {
3035 fn check(slice: &[BigDigit], data: &[BigDigit]) {
3036 let mut p = BigUint::from_slice(&[2627_u32, 0_u32, 9182_u32, 42_u32]);
3037 p.assign_from_slice(slice);
3038 assert!(p.data == data);
3039 }
3040 check(&[1], &[1]);
3041 check(&[0, 0, 0], &[]);
3042 check(&[1, 2, 0, 0], &[1, 2]);
3043 check(&[0, 0, 1, 2], &[0, 0, 1, 2]);
3044 check(&[0, 0, 1, 2, 0, 0], &[0, 0, 1, 2]);
3045 check(&[-1i32 as BigDigit], &[-1i32 as BigDigit]);
3046}
3047
3048#[cfg(has_i128)]
3049#[test]
3050fn test_u32_u128() {
3051 assert_eq!(u32_from_u128(0u128), (0, 0, 0, 0));
3052 assert_eq!(
3053 u32_from_u128(u128::max_value()),
3054 (
3055 u32::max_value(),
3056 u32::max_value(),
3057 u32::max_value(),
3058 u32::max_value()
3059 )
3060 );
3061
3062 assert_eq!(
3063 u32_from_u128(u32::max_value() as u128),
3064 (0, 0, 0, u32::max_value())
3065 );
3066
3067 assert_eq!(
3068 u32_from_u128(u64::max_value() as u128),
3069 (0, 0, u32::max_value(), u32::max_value())
3070 );
3071
3072 assert_eq!(
3073 u32_from_u128((u64::max_value() as u128) + u32::max_value() as u128),
3074 (0, 1, 0, u32::max_value() - 1)
3075 );
3076
3077 assert_eq!(u32_from_u128(36_893_488_151_714_070_528), (0, 2, 1, 0));
3078}
3079
3080#[cfg(has_i128)]
3081#[test]
3082fn test_u128_u32_roundtrip() {
3083 let values = vec![
3085 0u128,
3086 1u128,
3087 u64::max_value() as u128 * 3,
3088 u32::max_value() as u128,
3089 u64::max_value() as u128,
3090 (u64::max_value() as u128) + u32::max_value() as u128,
3091 u128::max_value(),
3092 ];
3093
3094 for val in &values {
3095 let (a, b, c, d) = u32_from_u128(*val);
3096 assert_eq!(u32_to_u128(a, b, c, d), *val);
3097 }
3098}
3099
3100#[test]
3101fn test_pow_biguint() {
3102 let base = BigUint::from(5u8);
3103 let exponent = BigUint::from(3u8);
3104
3105 assert_eq!(BigUint::from(125u8), base.pow(exponent));
3106}