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