summaryrefslogtreecommitdiffstats
path: root/rust/vendor/num-bigint-0.2.6/src/biguint.rs
diff options
context:
space:
mode:
Diffstat (limited to 'rust/vendor/num-bigint-0.2.6/src/biguint.rs')
-rw-r--r--rust/vendor/num-bigint-0.2.6/src/biguint.rs3106
1 files changed, 3106 insertions, 0 deletions
diff --git a/rust/vendor/num-bigint-0.2.6/src/biguint.rs b/rust/vendor/num-bigint-0.2.6/src/biguint.rs
new file mode 100644
index 0000000..6836342
--- /dev/null
+++ b/rust/vendor/num-bigint-0.2.6/src/biguint.rs
@@ -0,0 +1,3106 @@
+#[allow(deprecated, unused_imports)]
+use std::ascii::AsciiExt;
+use std::borrow::Cow;
+use std::cmp;
+use std::cmp::Ordering::{self, Equal, Greater, Less};
+use std::default::Default;
+use std::fmt;
+use std::iter::{Product, Sum};
+use std::mem;
+use std::ops::{
+ Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Div, DivAssign,
+ Mul, MulAssign, Neg, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign, Sub, SubAssign,
+};
+use std::str::{self, FromStr};
+use std::{f32, f64};
+use std::{u64, u8};
+
+#[cfg(feature = "serde")]
+use serde;
+
+use integer::{Integer, Roots};
+use traits::{
+ CheckedAdd, CheckedDiv, CheckedMul, CheckedSub, Float, FromPrimitive, Num, One, Pow,
+ ToPrimitive, Unsigned, Zero,
+};
+
+use big_digit::{self, BigDigit};
+
+#[path = "algorithms.rs"]
+mod algorithms;
+#[path = "monty.rs"]
+mod monty;
+
+use self::algorithms::{__add2, __sub2rev, add2, sub2, sub2rev};
+use self::algorithms::{biguint_shl, biguint_shr};
+use self::algorithms::{cmp_slice, fls, ilog2};
+use self::algorithms::{div_rem, div_rem_digit, div_rem_ref, rem_digit};
+use self::algorithms::{mac_with_carry, mul3, scalar_mul};
+use self::monty::monty_modpow;
+
+use UsizePromotion;
+
+use ParseBigIntError;
+
+#[cfg(feature = "quickcheck")]
+use quickcheck::{Arbitrary, Gen};
+
+/// A big unsigned integer type.
+#[derive(Clone, Debug, Hash)]
+pub struct BigUint {
+ data: Vec<BigDigit>,
+}
+
+#[cfg(feature = "quickcheck")]
+impl Arbitrary for BigUint {
+ fn arbitrary<G: Gen>(g: &mut G) -> Self {
+ // Use arbitrary from Vec
+ Self::new(Vec::<u32>::arbitrary(g))
+ }
+
+ #[allow(bare_trait_objects)] // `dyn` needs Rust 1.27 to parse, even when cfg-disabled
+ fn shrink(&self) -> Box<Iterator<Item = Self>> {
+ // Use shrinker from Vec
+ Box::new(self.data.shrink().map(BigUint::new))
+ }
+}
+
+impl PartialEq for BigUint {
+ #[inline]
+ fn eq(&self, other: &BigUint) -> bool {
+ match self.cmp(other) {
+ Equal => true,
+ _ => false,
+ }
+ }
+}
+impl Eq for BigUint {}
+
+impl PartialOrd for BigUint {
+ #[inline]
+ fn partial_cmp(&self, other: &BigUint) -> Option<Ordering> {
+ Some(self.cmp(other))
+ }
+}
+
+impl Ord for BigUint {
+ #[inline]
+ fn cmp(&self, other: &BigUint) -> Ordering {
+ cmp_slice(&self.data[..], &other.data[..])
+ }
+}
+
+impl Default for BigUint {
+ #[inline]
+ fn default() -> BigUint {
+ Zero::zero()
+ }
+}
+
+impl fmt::Display for BigUint {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ f.pad_integral(true, "", &self.to_str_radix(10))
+ }
+}
+
+impl fmt::LowerHex for BigUint {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ f.pad_integral(true, "0x", &self.to_str_radix(16))
+ }
+}
+
+impl fmt::UpperHex for BigUint {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ let mut s = self.to_str_radix(16);
+ s.make_ascii_uppercase();
+ f.pad_integral(true, "0x", &s)
+ }
+}
+
+impl fmt::Binary for BigUint {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ f.pad_integral(true, "0b", &self.to_str_radix(2))
+ }
+}
+
+impl fmt::Octal for BigUint {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ f.pad_integral(true, "0o", &self.to_str_radix(8))
+ }
+}
+
+impl FromStr for BigUint {
+ type Err = ParseBigIntError;
+
+ #[inline]
+ fn from_str(s: &str) -> Result<BigUint, ParseBigIntError> {
+ BigUint::from_str_radix(s, 10)
+ }
+}
+
+// Convert from a power of two radix (bits == ilog2(radix)) where bits evenly divides
+// BigDigit::BITS
+fn from_bitwise_digits_le(v: &[u8], bits: usize) -> BigUint {
+ debug_assert!(!v.is_empty() && bits <= 8 && big_digit::BITS % bits == 0);
+ debug_assert!(v.iter().all(|&c| BigDigit::from(c) < (1 << bits)));
+
+ let digits_per_big_digit = big_digit::BITS / bits;
+
+ let data = v
+ .chunks(digits_per_big_digit)
+ .map(|chunk| {
+ chunk
+ .iter()
+ .rev()
+ .fold(0, |acc, &c| (acc << bits) | BigDigit::from(c))
+ })
+ .collect();
+
+ BigUint::new(data)
+}
+
+// Convert from a power of two radix (bits == ilog2(radix)) where bits doesn't evenly divide
+// BigDigit::BITS
+fn from_inexact_bitwise_digits_le(v: &[u8], bits: usize) -> BigUint {
+ debug_assert!(!v.is_empty() && bits <= 8 && big_digit::BITS % bits != 0);
+ debug_assert!(v.iter().all(|&c| BigDigit::from(c) < (1 << bits)));
+
+ let big_digits = (v.len() * bits + big_digit::BITS - 1) / big_digit::BITS;
+ let mut data = Vec::with_capacity(big_digits);
+
+ let mut d = 0;
+ let mut dbits = 0; // number of bits we currently have in d
+
+ // walk v accumululating bits in d; whenever we accumulate big_digit::BITS in d, spit out a
+ // big_digit:
+ for &c in v {
+ d |= BigDigit::from(c) << dbits;
+ dbits += bits;
+
+ if dbits >= big_digit::BITS {
+ data.push(d);
+ dbits -= big_digit::BITS;
+ // if dbits was > big_digit::BITS, we dropped some of the bits in c (they couldn't fit
+ // in d) - grab the bits we lost here:
+ d = BigDigit::from(c) >> (bits - dbits);
+ }
+ }
+
+ if dbits > 0 {
+ debug_assert!(dbits < big_digit::BITS);
+ data.push(d as BigDigit);
+ }
+
+ BigUint::new(data)
+}
+
+// Read little-endian radix digits
+fn from_radix_digits_be(v: &[u8], radix: u32) -> BigUint {
+ debug_assert!(!v.is_empty() && !radix.is_power_of_two());
+ debug_assert!(v.iter().all(|&c| u32::from(c) < radix));
+
+ // Estimate how big the result will be, so we can pre-allocate it.
+ let bits = f64::from(radix).log2() * v.len() as f64;
+ let big_digits = (bits / big_digit::BITS as f64).ceil();
+ let mut data = Vec::with_capacity(big_digits as usize);
+
+ let (base, power) = get_radix_base(radix);
+ let radix = radix as BigDigit;
+
+ let r = v.len() % power;
+ let i = if r == 0 { power } else { r };
+ let (head, tail) = v.split_at(i);
+
+ let first = head
+ .iter()
+ .fold(0, |acc, &d| acc * radix + BigDigit::from(d));
+ data.push(first);
+
+ debug_assert!(tail.len() % power == 0);
+ for chunk in tail.chunks(power) {
+ if data.last() != Some(&0) {
+ data.push(0);
+ }
+
+ let mut carry = 0;
+ for d in data.iter_mut() {
+ *d = mac_with_carry(0, *d, base, &mut carry);
+ }
+ debug_assert!(carry == 0);
+
+ let n = chunk
+ .iter()
+ .fold(0, |acc, &d| acc * radix + BigDigit::from(d));
+ add2(&mut data, &[n]);
+ }
+
+ BigUint::new(data)
+}
+
+impl Num for BigUint {
+ type FromStrRadixErr = ParseBigIntError;
+
+ /// Creates and initializes a `BigUint`.
+ fn from_str_radix(s: &str, radix: u32) -> Result<BigUint, ParseBigIntError> {
+ assert!(2 <= radix && radix <= 36, "The radix must be within 2...36");
+ let mut s = s;
+ if s.starts_with('+') {
+ let tail = &s[1..];
+ if !tail.starts_with('+') {
+ s = tail
+ }
+ }
+
+ if s.is_empty() {
+ return Err(ParseBigIntError::empty());
+ }
+
+ if s.starts_with('_') {
+ // Must lead with a real digit!
+ return Err(ParseBigIntError::invalid());
+ }
+
+ // First normalize all characters to plain digit values
+ let mut v = Vec::with_capacity(s.len());
+ for b in s.bytes() {
+ #[allow(unknown_lints, ellipsis_inclusive_range_patterns)]
+ let d = match b {
+ b'0'...b'9' => b - b'0',
+ b'a'...b'z' => b - b'a' + 10,
+ b'A'...b'Z' => b - b'A' + 10,
+ b'_' => continue,
+ _ => u8::MAX,
+ };
+ if d < radix as u8 {
+ v.push(d);
+ } else {
+ return Err(ParseBigIntError::invalid());
+ }
+ }
+
+ let res = if radix.is_power_of_two() {
+ // Powers of two can use bitwise masks and shifting instead of multiplication
+ let bits = ilog2(radix);
+ v.reverse();
+ if big_digit::BITS % bits == 0 {
+ from_bitwise_digits_le(&v, bits)
+ } else {
+ from_inexact_bitwise_digits_le(&v, bits)
+ }
+ } else {
+ from_radix_digits_be(&v, radix)
+ };
+ Ok(res)
+ }
+}
+
+forward_val_val_binop!(impl BitAnd for BigUint, bitand);
+forward_ref_val_binop!(impl BitAnd for BigUint, bitand);
+
+// do not use forward_ref_ref_binop_commutative! for bitand so that we can
+// clone the smaller value rather than the larger, avoiding over-allocation
+impl<'a, 'b> BitAnd<&'b BigUint> for &'a BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn bitand(self, other: &BigUint) -> BigUint {
+ // forward to val-ref, choosing the smaller to clone
+ if self.data.len() <= other.data.len() {
+ self.clone() & other
+ } else {
+ other.clone() & self
+ }
+ }
+}
+
+forward_val_assign!(impl BitAndAssign for BigUint, bitand_assign);
+
+impl<'a> BitAnd<&'a BigUint> for BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn bitand(mut self, other: &BigUint) -> BigUint {
+ self &= other;
+ self
+ }
+}
+impl<'a> BitAndAssign<&'a BigUint> for BigUint {
+ #[inline]
+ fn bitand_assign(&mut self, other: &BigUint) {
+ for (ai, &bi) in self.data.iter_mut().zip(other.data.iter()) {
+ *ai &= bi;
+ }
+ self.data.truncate(other.data.len());
+ self.normalize();
+ }
+}
+
+forward_all_binop_to_val_ref_commutative!(impl BitOr for BigUint, bitor);
+forward_val_assign!(impl BitOrAssign for BigUint, bitor_assign);
+
+impl<'a> BitOr<&'a BigUint> for BigUint {
+ type Output = BigUint;
+
+ fn bitor(mut self, other: &BigUint) -> BigUint {
+ self |= other;
+ self
+ }
+}
+impl<'a> BitOrAssign<&'a BigUint> for BigUint {
+ #[inline]
+ fn bitor_assign(&mut self, other: &BigUint) {
+ for (ai, &bi) in self.data.iter_mut().zip(other.data.iter()) {
+ *ai |= bi;
+ }
+ if other.data.len() > self.data.len() {
+ let extra = &other.data[self.data.len()..];
+ self.data.extend(extra.iter().cloned());
+ }
+ }
+}
+
+forward_all_binop_to_val_ref_commutative!(impl BitXor for BigUint, bitxor);
+forward_val_assign!(impl BitXorAssign for BigUint, bitxor_assign);
+
+impl<'a> BitXor<&'a BigUint> for BigUint {
+ type Output = BigUint;
+
+ fn bitxor(mut self, other: &BigUint) -> BigUint {
+ self ^= other;
+ self
+ }
+}
+impl<'a> BitXorAssign<&'a BigUint> for BigUint {
+ #[inline]
+ fn bitxor_assign(&mut self, other: &BigUint) {
+ for (ai, &bi) in self.data.iter_mut().zip(other.data.iter()) {
+ *ai ^= bi;
+ }
+ if other.data.len() > self.data.len() {
+ let extra = &other.data[self.data.len()..];
+ self.data.extend(extra.iter().cloned());
+ }
+ self.normalize();
+ }
+}
+
+impl Shl<usize> for BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn shl(self, rhs: usize) -> BigUint {
+ biguint_shl(Cow::Owned(self), rhs)
+ }
+}
+impl<'a> Shl<usize> for &'a BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn shl(self, rhs: usize) -> BigUint {
+ biguint_shl(Cow::Borrowed(self), rhs)
+ }
+}
+
+impl ShlAssign<usize> for BigUint {
+ #[inline]
+ fn shl_assign(&mut self, rhs: usize) {
+ let n = mem::replace(self, BigUint::zero());
+ *self = n << rhs;
+ }
+}
+
+impl Shr<usize> for BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn shr(self, rhs: usize) -> BigUint {
+ biguint_shr(Cow::Owned(self), rhs)
+ }
+}
+impl<'a> Shr<usize> for &'a BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn shr(self, rhs: usize) -> BigUint {
+ biguint_shr(Cow::Borrowed(self), rhs)
+ }
+}
+
+impl ShrAssign<usize> for BigUint {
+ #[inline]
+ fn shr_assign(&mut self, rhs: usize) {
+ let n = mem::replace(self, BigUint::zero());
+ *self = n >> rhs;
+ }
+}
+
+impl Zero for BigUint {
+ #[inline]
+ fn zero() -> BigUint {
+ BigUint::new(Vec::new())
+ }
+
+ #[inline]
+ fn set_zero(&mut self) {
+ self.data.clear();
+ }
+
+ #[inline]
+ fn is_zero(&self) -> bool {
+ self.data.is_empty()
+ }
+}
+
+impl One for BigUint {
+ #[inline]
+ fn one() -> BigUint {
+ BigUint::new(vec![1])
+ }
+
+ #[inline]
+ fn set_one(&mut self) {
+ self.data.clear();
+ self.data.push(1);
+ }
+
+ #[inline]
+ fn is_one(&self) -> bool {
+ self.data[..] == [1]
+ }
+}
+
+impl Unsigned for BigUint {}
+
+impl<'a> Pow<BigUint> for &'a BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn pow(self, exp: BigUint) -> Self::Output {
+ self.pow(&exp)
+ }
+}
+
+impl<'a, 'b> Pow<&'b BigUint> for &'a BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn pow(self, exp: &BigUint) -> Self::Output {
+ if self.is_one() || exp.is_zero() {
+ BigUint::one()
+ } else if self.is_zero() {
+ BigUint::zero()
+ } else if let Some(exp) = exp.to_u64() {
+ self.pow(exp)
+ } else {
+ // At this point, `self >= 2` and `exp >= 2⁶⁴`. The smallest possible result
+ // given `2.pow(2⁶⁴)` would take 2.3 exabytes of memory!
+ panic!("memory overflow")
+ }
+ }
+}
+
+macro_rules! pow_impl {
+ ($T:ty) => {
+ impl<'a> Pow<$T> for &'a BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn pow(self, mut exp: $T) -> Self::Output {
+ if exp == 0 {
+ return BigUint::one();
+ }
+ let mut base = self.clone();
+
+ while exp & 1 == 0 {
+ base = &base * &base;
+ exp >>= 1;
+ }
+
+ if exp == 1 {
+ return base;
+ }
+
+ let mut acc = base.clone();
+ while exp > 1 {
+ exp >>= 1;
+ base = &base * &base;
+ if exp & 1 == 1 {
+ acc = &acc * &base;
+ }
+ }
+ acc
+ }
+ }
+
+ impl<'a, 'b> Pow<&'b $T> for &'a BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn pow(self, exp: &$T) -> Self::Output {
+ self.pow(*exp)
+ }
+ }
+ };
+}
+
+pow_impl!(u8);
+pow_impl!(u16);
+pow_impl!(u32);
+pow_impl!(u64);
+pow_impl!(usize);
+#[cfg(has_i128)]
+pow_impl!(u128);
+
+forward_all_binop_to_val_ref_commutative!(impl Add for BigUint, add);
+forward_val_assign!(impl AddAssign for BigUint, add_assign);
+
+impl<'a> Add<&'a BigUint> for BigUint {
+ type Output = BigUint;
+
+ fn add(mut self, other: &BigUint) -> BigUint {
+ self += other;
+ self
+ }
+}
+impl<'a> AddAssign<&'a BigUint> for BigUint {
+ #[inline]
+ fn add_assign(&mut self, other: &BigUint) {
+ let self_len = self.data.len();
+ let carry = if self_len < other.data.len() {
+ let lo_carry = __add2(&mut self.data[..], &other.data[..self_len]);
+ self.data.extend_from_slice(&other.data[self_len..]);
+ __add2(&mut self.data[self_len..], &[lo_carry])
+ } else {
+ __add2(&mut self.data[..], &other.data[..])
+ };
+ if carry != 0 {
+ self.data.push(carry);
+ }
+ }
+}
+
+promote_unsigned_scalars!(impl Add for BigUint, add);
+promote_unsigned_scalars_assign!(impl AddAssign for BigUint, add_assign);
+forward_all_scalar_binop_to_val_val_commutative!(impl Add<u32> for BigUint, add);
+forward_all_scalar_binop_to_val_val_commutative!(impl Add<u64> for BigUint, add);
+#[cfg(has_i128)]
+forward_all_scalar_binop_to_val_val_commutative!(impl Add<u128> for BigUint, add);
+
+impl Add<u32> for BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn add(mut self, other: u32) -> BigUint {
+ self += other;
+ self
+ }
+}
+
+impl AddAssign<u32> for BigUint {
+ #[inline]
+ fn add_assign(&mut self, other: u32) {
+ if other != 0 {
+ if self.data.is_empty() {
+ self.data.push(0);
+ }
+
+ let carry = __add2(&mut self.data, &[other as BigDigit]);
+ if carry != 0 {
+ self.data.push(carry);
+ }
+ }
+ }
+}
+
+impl Add<u64> for BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn add(mut self, other: u64) -> BigUint {
+ self += other;
+ self
+ }
+}
+
+impl AddAssign<u64> for BigUint {
+ #[inline]
+ fn add_assign(&mut self, other: u64) {
+ let (hi, lo) = big_digit::from_doublebigdigit(other);
+ if hi == 0 {
+ *self += lo;
+ } else {
+ while self.data.len() < 2 {
+ self.data.push(0);
+ }
+
+ let carry = __add2(&mut self.data, &[lo, hi]);
+ if carry != 0 {
+ self.data.push(carry);
+ }
+ }
+ }
+}
+
+#[cfg(has_i128)]
+impl Add<u128> for BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn add(mut self, other: u128) -> BigUint {
+ self += other;
+ self
+ }
+}
+
+#[cfg(has_i128)]
+impl AddAssign<u128> for BigUint {
+ #[inline]
+ fn add_assign(&mut self, other: u128) {
+ if other <= u128::from(u64::max_value()) {
+ *self += other as u64
+ } else {
+ let (a, b, c, d) = u32_from_u128(other);
+ let carry = if a > 0 {
+ while self.data.len() < 4 {
+ self.data.push(0);
+ }
+ __add2(&mut self.data, &[d, c, b, a])
+ } else {
+ debug_assert!(b > 0);
+ while self.data.len() < 3 {
+ self.data.push(0);
+ }
+ __add2(&mut self.data, &[d, c, b])
+ };
+
+ if carry != 0 {
+ self.data.push(carry);
+ }
+ }
+ }
+}
+
+forward_val_val_binop!(impl Sub for BigUint, sub);
+forward_ref_ref_binop!(impl Sub for BigUint, sub);
+forward_val_assign!(impl SubAssign for BigUint, sub_assign);
+
+impl<'a> Sub<&'a BigUint> for BigUint {
+ type Output = BigUint;
+
+ fn sub(mut self, other: &BigUint) -> BigUint {
+ self -= other;
+ self
+ }
+}
+impl<'a> SubAssign<&'a BigUint> for BigUint {
+ fn sub_assign(&mut self, other: &'a BigUint) {
+ sub2(&mut self.data[..], &other.data[..]);
+ self.normalize();
+ }
+}
+
+impl<'a> Sub<BigUint> for &'a BigUint {
+ type Output = BigUint;
+
+ fn sub(self, mut other: BigUint) -> BigUint {
+ let other_len = other.data.len();
+ if other_len < self.data.len() {
+ let lo_borrow = __sub2rev(&self.data[..other_len], &mut other.data);
+ other.data.extend_from_slice(&self.data[other_len..]);
+ if lo_borrow != 0 {
+ sub2(&mut other.data[other_len..], &[1])
+ }
+ } else {
+ sub2rev(&self.data[..], &mut other.data[..]);
+ }
+ other.normalized()
+ }
+}
+
+promote_unsigned_scalars!(impl Sub for BigUint, sub);
+promote_unsigned_scalars_assign!(impl SubAssign for BigUint, sub_assign);
+forward_all_scalar_binop_to_val_val!(impl Sub<u32> for BigUint, sub);
+forward_all_scalar_binop_to_val_val!(impl Sub<u64> for BigUint, sub);
+#[cfg(has_i128)]
+forward_all_scalar_binop_to_val_val!(impl Sub<u128> for BigUint, sub);
+
+impl Sub<u32> for BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn sub(mut self, other: u32) -> BigUint {
+ self -= other;
+ self
+ }
+}
+impl SubAssign<u32> for BigUint {
+ fn sub_assign(&mut self, other: u32) {
+ sub2(&mut self.data[..], &[other as BigDigit]);
+ self.normalize();
+ }
+}
+
+impl Sub<BigUint> for u32 {
+ type Output = BigUint;
+
+ #[inline]
+ fn sub(self, mut other: BigUint) -> BigUint {
+ if other.data.is_empty() {
+ other.data.push(self as BigDigit);
+ } else {
+ sub2rev(&[self as BigDigit], &mut other.data[..]);
+ }
+ other.normalized()
+ }
+}
+
+impl Sub<u64> for BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn sub(mut self, other: u64) -> BigUint {
+ self -= other;
+ self
+ }
+}
+
+impl SubAssign<u64> for BigUint {
+ #[inline]
+ fn sub_assign(&mut self, other: u64) {
+ let (hi, lo) = big_digit::from_doublebigdigit(other);
+ sub2(&mut self.data[..], &[lo, hi]);
+ self.normalize();
+ }
+}
+
+impl Sub<BigUint> for u64 {
+ type Output = BigUint;
+
+ #[inline]
+ fn sub(self, mut other: BigUint) -> BigUint {
+ while other.data.len() < 2 {
+ other.data.push(0);
+ }
+
+ let (hi, lo) = big_digit::from_doublebigdigit(self);
+ sub2rev(&[lo, hi], &mut other.data[..]);
+ other.normalized()
+ }
+}
+
+#[cfg(has_i128)]
+impl Sub<u128> for BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn sub(mut self, other: u128) -> BigUint {
+ self -= other;
+ self
+ }
+}
+#[cfg(has_i128)]
+impl SubAssign<u128> for BigUint {
+ fn sub_assign(&mut self, other: u128) {
+ let (a, b, c, d) = u32_from_u128(other);
+ sub2(&mut self.data[..], &[d, c, b, a]);
+ self.normalize();
+ }
+}
+
+#[cfg(has_i128)]
+impl Sub<BigUint> for u128 {
+ type Output = BigUint;
+
+ #[inline]
+ fn sub(self, mut other: BigUint) -> BigUint {
+ while other.data.len() < 4 {
+ other.data.push(0);
+ }
+
+ let (a, b, c, d) = u32_from_u128(self);
+ sub2rev(&[d, c, b, a], &mut other.data[..]);
+ other.normalized()
+ }
+}
+
+forward_all_binop_to_ref_ref!(impl Mul for BigUint, mul);
+forward_val_assign!(impl MulAssign for BigUint, mul_assign);
+
+impl<'a, 'b> Mul<&'b BigUint> for &'a BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn mul(self, other: &BigUint) -> BigUint {
+ mul3(&self.data[..], &other.data[..])
+ }
+}
+impl<'a> MulAssign<&'a BigUint> for BigUint {
+ #[inline]
+ fn mul_assign(&mut self, other: &'a BigUint) {
+ *self = &*self * other
+ }
+}
+
+promote_unsigned_scalars!(impl Mul for BigUint, mul);
+promote_unsigned_scalars_assign!(impl MulAssign for BigUint, mul_assign);
+forward_all_scalar_binop_to_val_val_commutative!(impl Mul<u32> for BigUint, mul);
+forward_all_scalar_binop_to_val_val_commutative!(impl Mul<u64> for BigUint, mul);
+#[cfg(has_i128)]
+forward_all_scalar_binop_to_val_val_commutative!(impl Mul<u128> for BigUint, mul);
+
+impl Mul<u32> for BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn mul(mut self, other: u32) -> BigUint {
+ self *= other;
+ self
+ }
+}
+impl MulAssign<u32> for BigUint {
+ #[inline]
+ fn mul_assign(&mut self, other: u32) {
+ if other == 0 {
+ self.data.clear();
+ } else {
+ let carry = scalar_mul(&mut self.data[..], other as BigDigit);
+ if carry != 0 {
+ self.data.push(carry);
+ }
+ }
+ }
+}
+
+impl Mul<u64> for BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn mul(mut self, other: u64) -> BigUint {
+ self *= other;
+ self
+ }
+}
+impl MulAssign<u64> for BigUint {
+ #[inline]
+ fn mul_assign(&mut self, other: u64) {
+ if other == 0 {
+ self.data.clear();
+ } else if other <= u64::from(BigDigit::max_value()) {
+ *self *= other as BigDigit
+ } else {
+ let (hi, lo) = big_digit::from_doublebigdigit(other);
+ *self = mul3(&self.data[..], &[lo, hi])
+ }
+ }
+}
+
+#[cfg(has_i128)]
+impl Mul<u128> for BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn mul(mut self, other: u128) -> BigUint {
+ self *= other;
+ self
+ }
+}
+#[cfg(has_i128)]
+impl MulAssign<u128> for BigUint {
+ #[inline]
+ fn mul_assign(&mut self, other: u128) {
+ if other == 0 {
+ self.data.clear();
+ } else if other <= u128::from(BigDigit::max_value()) {
+ *self *= other as BigDigit
+ } else {
+ let (a, b, c, d) = u32_from_u128(other);
+ *self = mul3(&self.data[..], &[d, c, b, a])
+ }
+ }
+}
+
+forward_val_ref_binop!(impl Div for BigUint, div);
+forward_ref_val_binop!(impl Div for BigUint, div);
+forward_val_assign!(impl DivAssign for BigUint, div_assign);
+
+impl Div<BigUint> for BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn div(self, other: BigUint) -> BigUint {
+ let (q, _) = div_rem(self, other);
+ q
+ }
+}
+
+impl<'a, 'b> Div<&'b BigUint> for &'a BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn div(self, other: &BigUint) -> BigUint {
+ let (q, _) = self.div_rem(other);
+ q
+ }
+}
+impl<'a> DivAssign<&'a BigUint> for BigUint {
+ #[inline]
+ fn div_assign(&mut self, other: &'a BigUint) {
+ *self = &*self / other;
+ }
+}
+
+promote_unsigned_scalars!(impl Div for BigUint, div);
+promote_unsigned_scalars_assign!(impl DivAssign for BigUint, div_assign);
+forward_all_scalar_binop_to_val_val!(impl Div<u32> for BigUint, div);
+forward_all_scalar_binop_to_val_val!(impl Div<u64> for BigUint, div);
+#[cfg(has_i128)]
+forward_all_scalar_binop_to_val_val!(impl Div<u128> for BigUint, div);
+
+impl Div<u32> for BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn div(self, other: u32) -> BigUint {
+ let (q, _) = div_rem_digit(self, other as BigDigit);
+ q
+ }
+}
+impl DivAssign<u32> for BigUint {
+ #[inline]
+ fn div_assign(&mut self, other: u32) {
+ *self = &*self / other;
+ }
+}
+
+impl Div<BigUint> for u32 {
+ type Output = BigUint;
+
+ #[inline]
+ fn div(self, other: BigUint) -> BigUint {
+ match other.data.len() {
+ 0 => panic!(),
+ 1 => From::from(self as BigDigit / other.data[0]),
+ _ => Zero::zero(),
+ }
+ }
+}
+
+impl Div<u64> for BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn div(self, other: u64) -> BigUint {
+ let (q, _) = div_rem(self, From::from(other));
+ q
+ }
+}
+impl DivAssign<u64> for BigUint {
+ #[inline]
+ fn div_assign(&mut self, other: u64) {
+ // a vec of size 0 does not allocate, so this is fairly cheap
+ let temp = mem::replace(self, Zero::zero());
+ *self = temp / other;
+ }
+}
+
+impl Div<BigUint> for u64 {
+ type Output = BigUint;
+
+ #[inline]
+ fn div(self, other: BigUint) -> BigUint {
+ match other.data.len() {
+ 0 => panic!(),
+ 1 => From::from(self / u64::from(other.data[0])),
+ 2 => From::from(self / big_digit::to_doublebigdigit(other.data[1], other.data[0])),
+ _ => Zero::zero(),
+ }
+ }
+}
+
+#[cfg(has_i128)]
+impl Div<u128> for BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn div(self, other: u128) -> BigUint {
+ let (q, _) = div_rem(self, From::from(other));
+ q
+ }
+}
+#[cfg(has_i128)]
+impl DivAssign<u128> for BigUint {
+ #[inline]
+ fn div_assign(&mut self, other: u128) {
+ *self = &*self / other;
+ }
+}
+
+#[cfg(has_i128)]
+impl Div<BigUint> for u128 {
+ type Output = BigUint;
+
+ #[inline]
+ fn div(self, other: BigUint) -> BigUint {
+ match other.data.len() {
+ 0 => panic!(),
+ 1 => From::from(self / u128::from(other.data[0])),
+ 2 => From::from(
+ self / u128::from(big_digit::to_doublebigdigit(other.data[1], other.data[0])),
+ ),
+ 3 => From::from(self / u32_to_u128(0, other.data[2], other.data[1], other.data[0])),
+ 4 => From::from(
+ self / u32_to_u128(other.data[3], other.data[2], other.data[1], other.data[0]),
+ ),
+ _ => Zero::zero(),
+ }
+ }
+}
+
+forward_val_ref_binop!(impl Rem for BigUint, rem);
+forward_ref_val_binop!(impl Rem for BigUint, rem);
+forward_val_assign!(impl RemAssign for BigUint, rem_assign);
+
+impl Rem<BigUint> for BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn rem(self, other: BigUint) -> BigUint {
+ let (_, r) = div_rem(self, other);
+ r
+ }
+}
+
+impl<'a, 'b> Rem<&'b BigUint> for &'a BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn rem(self, other: &BigUint) -> BigUint {
+ let (_, r) = self.div_rem(other);
+ r
+ }
+}
+impl<'a> RemAssign<&'a BigUint> for BigUint {
+ #[inline]
+ fn rem_assign(&mut self, other: &BigUint) {
+ *self = &*self % other;
+ }
+}
+
+promote_unsigned_scalars!(impl Rem for BigUint, rem);
+promote_unsigned_scalars_assign!(impl RemAssign for BigUint, rem_assign);
+forward_all_scalar_binop_to_ref_val!(impl Rem<u32> for BigUint, rem);
+forward_all_scalar_binop_to_val_val!(impl Rem<u64> for BigUint, rem);
+#[cfg(has_i128)]
+forward_all_scalar_binop_to_val_val!(impl Rem<u128> for BigUint, rem);
+
+impl<'a> Rem<u32> for &'a BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn rem(self, other: u32) -> BigUint {
+ From::from(rem_digit(self, other as BigDigit))
+ }
+}
+impl RemAssign<u32> for BigUint {
+ #[inline]
+ fn rem_assign(&mut self, other: u32) {
+ *self = &*self % other;
+ }
+}
+
+impl<'a> Rem<&'a BigUint> for u32 {
+ type Output = BigUint;
+
+ #[inline]
+ fn rem(mut self, other: &'a BigUint) -> BigUint {
+ self %= other;
+ From::from(self)
+ }
+}
+
+macro_rules! impl_rem_assign_scalar {
+ ($scalar:ty, $to_scalar:ident) => {
+ forward_val_assign_scalar!(impl RemAssign for BigUint, $scalar, rem_assign);
+ impl<'a> RemAssign<&'a BigUint> for $scalar {
+ #[inline]
+ fn rem_assign(&mut self, other: &BigUint) {
+ *self = match other.$to_scalar() {
+ None => *self,
+ Some(0) => panic!(),
+ Some(v) => *self % v
+ };
+ }
+ }
+ }
+}
+// we can scalar %= BigUint for any scalar, including signed types
+#[cfg(has_i128)]
+impl_rem_assign_scalar!(u128, to_u128);
+impl_rem_assign_scalar!(usize, to_usize);
+impl_rem_assign_scalar!(u64, to_u64);
+impl_rem_assign_scalar!(u32, to_u32);
+impl_rem_assign_scalar!(u16, to_u16);
+impl_rem_assign_scalar!(u8, to_u8);
+#[cfg(has_i128)]
+impl_rem_assign_scalar!(i128, to_i128);
+impl_rem_assign_scalar!(isize, to_isize);
+impl_rem_assign_scalar!(i64, to_i64);
+impl_rem_assign_scalar!(i32, to_i32);
+impl_rem_assign_scalar!(i16, to_i16);
+impl_rem_assign_scalar!(i8, to_i8);
+
+impl Rem<u64> for BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn rem(self, other: u64) -> BigUint {
+ let (_, r) = div_rem(self, From::from(other));
+ r
+ }
+}
+impl RemAssign<u64> for BigUint {
+ #[inline]
+ fn rem_assign(&mut self, other: u64) {
+ *self = &*self % other;
+ }
+}
+
+impl Rem<BigUint> for u64 {
+ type Output = BigUint;
+
+ #[inline]
+ fn rem(mut self, other: BigUint) -> BigUint {
+ self %= other;
+ From::from(self)
+ }
+}
+
+#[cfg(has_i128)]
+impl Rem<u128> for BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn rem(self, other: u128) -> BigUint {
+ let (_, r) = div_rem(self, From::from(other));
+ r
+ }
+}
+#[cfg(has_i128)]
+impl RemAssign<u128> for BigUint {
+ #[inline]
+ fn rem_assign(&mut self, other: u128) {
+ *self = &*self % other;
+ }
+}
+
+#[cfg(has_i128)]
+impl Rem<BigUint> for u128 {
+ type Output = BigUint;
+
+ #[inline]
+ fn rem(mut self, other: BigUint) -> BigUint {
+ self %= other;
+ From::from(self)
+ }
+}
+
+impl Neg for BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn neg(self) -> BigUint {
+ panic!()
+ }
+}
+
+impl<'a> Neg for &'a BigUint {
+ type Output = BigUint;
+
+ #[inline]
+ fn neg(self) -> BigUint {
+ panic!()
+ }
+}
+
+impl CheckedAdd for BigUint {
+ #[inline]
+ fn checked_add(&self, v: &BigUint) -> Option<BigUint> {
+ Some(self.add(v))
+ }
+}
+
+impl CheckedSub for BigUint {
+ #[inline]
+ fn checked_sub(&self, v: &BigUint) -> Option<BigUint> {
+ match self.cmp(v) {
+ Less => None,
+ Equal => Some(Zero::zero()),
+ Greater => Some(self.sub(v)),
+ }
+ }
+}
+
+impl CheckedMul for BigUint {
+ #[inline]
+ fn checked_mul(&self, v: &BigUint) -> Option<BigUint> {
+ Some(self.mul(v))
+ }
+}
+
+impl CheckedDiv for BigUint {
+ #[inline]
+ fn checked_div(&self, v: &BigUint) -> Option<BigUint> {
+ if v.is_zero() {
+ return None;
+ }
+ Some(self.div(v))
+ }
+}
+
+impl Integer for BigUint {
+ #[inline]
+ fn div_rem(&self, other: &BigUint) -> (BigUint, BigUint) {
+ div_rem_ref(self, other)
+ }
+
+ #[inline]
+ fn div_floor(&self, other: &BigUint) -> BigUint {
+ let (d, _) = div_rem_ref(self, other);
+ d
+ }
+
+ #[inline]
+ fn mod_floor(&self, other: &BigUint) -> BigUint {
+ let (_, m) = div_rem_ref(self, other);
+ m
+ }
+
+ #[inline]
+ fn div_mod_floor(&self, other: &BigUint) -> (BigUint, BigUint) {
+ div_rem_ref(self, other)
+ }
+
+ /// Calculates the Greatest Common Divisor (GCD) of the number and `other`.
+ ///
+ /// The result is always positive.
+ #[inline]
+ fn gcd(&self, other: &Self) -> Self {
+ #[inline]
+ fn twos(x: &BigUint) -> usize {
+ trailing_zeros(x).unwrap_or(0)
+ }
+
+ // Stein's algorithm
+ if self.is_zero() {
+ return other.clone();
+ }
+ if other.is_zero() {
+ return self.clone();
+ }
+ let mut m = self.clone();
+ let mut n = other.clone();
+
+ // find common factors of 2
+ let shift = cmp::min(twos(&n), twos(&m));
+
+ // divide m and n by 2 until odd
+ // m inside loop
+ n >>= twos(&n);
+
+ while !m.is_zero() {
+ m >>= twos(&m);
+ if n > m {
+ mem::swap(&mut n, &mut m)
+ }
+ m -= &n;
+ }
+
+ n << shift
+ }
+
+ /// Calculates the Lowest Common Multiple (LCM) of the number and `other`.
+ #[inline]
+ fn lcm(&self, other: &BigUint) -> BigUint {
+ if self.is_zero() && other.is_zero() {
+ Self::zero()
+ } else {
+ self / self.gcd(other) * other
+ }
+ }
+
+ /// Deprecated, use `is_multiple_of` instead.
+ #[inline]
+ fn divides(&self, other: &BigUint) -> bool {
+ self.is_multiple_of(other)
+ }
+
+ /// Returns `true` if the number is a multiple of `other`.
+ #[inline]
+ fn is_multiple_of(&self, other: &BigUint) -> bool {
+ (self % other).is_zero()
+ }
+
+ /// Returns `true` if the number is divisible by `2`.
+ #[inline]
+ fn is_even(&self) -> bool {
+ // Considering only the last digit.
+ match self.data.first() {
+ Some(x) => x.is_even(),
+ None => true,
+ }
+ }
+
+ /// Returns `true` if the number is not divisible by `2`.
+ #[inline]
+ fn is_odd(&self) -> bool {
+ !self.is_even()
+ }
+}
+
+#[inline]
+fn fixpoint<F>(mut x: BigUint, max_bits: usize, f: F) -> BigUint
+where
+ F: Fn(&BigUint) -> BigUint,
+{
+ let mut xn = f(&x);
+
+ // If the value increased, then the initial guess must have been low.
+ // Repeat until we reverse course.
+ while x < xn {
+ // Sometimes an increase will go way too far, especially with large
+ // powers, and then take a long time to walk back. We know an upper
+ // bound based on bit size, so saturate on that.
+ x = if xn.bits() > max_bits {
+ BigUint::one() << max_bits
+ } else {
+ xn
+ };
+ xn = f(&x);
+ }
+
+ // Now keep repeating while the estimate is decreasing.
+ while x > xn {
+ x = xn;
+ xn = f(&x);
+ }
+ x
+}
+
+impl Roots for BigUint {
+ // nth_root, sqrt and cbrt use Newton's method to compute
+ // principal root of a given degree for a given integer.
+
+ // Reference:
+ // Brent & Zimmermann, Modern Computer Arithmetic, v0.5.9, Algorithm 1.14
+ fn nth_root(&self, n: u32) -> Self {
+ assert!(n > 0, "root degree n must be at least 1");
+
+ if self.is_zero() || self.is_one() {
+ return self.clone();
+ }
+
+ match n {
+ // Optimize for small n
+ 1 => return self.clone(),
+ 2 => return self.sqrt(),
+ 3 => return self.cbrt(),
+ _ => (),
+ }
+
+ // The root of non-zero values less than 2ⁿ can only be 1.
+ let bits = self.bits();
+ if bits <= n as usize {
+ return BigUint::one();
+ }
+
+ // If we fit in `u64`, compute the root that way.
+ if let Some(x) = self.to_u64() {
+ return x.nth_root(n).into();
+ }
+
+ let max_bits = bits / n as usize + 1;
+
+ let guess = if let Some(f) = self.to_f64() {
+ // We fit in `f64` (lossy), so get a better initial guess from that.
+ BigUint::from_f64((f.ln() / f64::from(n)).exp()).unwrap()
+ } else {
+ // Try to guess by scaling down such that it does fit in `f64`.
+ // With some (x * 2ⁿᵏ), its nth root ≈ (ⁿ√x * 2ᵏ)
+ let nsz = n as usize;
+ let extra_bits = bits - (f64::MAX_EXP as usize - 1);
+ let root_scale = (extra_bits + (nsz - 1)) / nsz;
+ let scale = root_scale * nsz;
+ if scale < bits && bits - scale > nsz {
+ (self >> scale).nth_root(n) << root_scale
+ } else {
+ BigUint::one() << max_bits
+ }
+ };
+
+ let n_min_1 = n - 1;
+ fixpoint(guess, max_bits, move |s| {
+ let q = self / s.pow(n_min_1);
+ let t = n_min_1 * s + q;
+ t / n
+ })
+ }
+
+ // Reference:
+ // Brent & Zimmermann, Modern Computer Arithmetic, v0.5.9, Algorithm 1.13
+ fn sqrt(&self) -> Self {
+ if self.is_zero() || self.is_one() {
+ return self.clone();
+ }
+
+ // If we fit in `u64`, compute the root that way.
+ if let Some(x) = self.to_u64() {
+ return x.sqrt().into();
+ }
+
+ let bits = self.bits();
+ let max_bits = bits / 2 as usize + 1;
+
+ let guess = if let Some(f) = self.to_f64() {
+ // We fit in `f64` (lossy), so get a better initial guess from that.
+ BigUint::from_f64(f.sqrt()).unwrap()
+ } else {
+ // Try to guess by scaling down such that it does fit in `f64`.
+ // With some (x * 2²ᵏ), its sqrt ≈ (√x * 2ᵏ)
+ let extra_bits = bits - (f64::MAX_EXP as usize - 1);
+ let root_scale = (extra_bits + 1) / 2;
+ let scale = root_scale * 2;
+ (self >> scale).sqrt() << root_scale
+ };
+
+ fixpoint(guess, max_bits, move |s| {
+ let q = self / s;
+ let t = s + q;
+ t >> 1
+ })
+ }
+
+ fn cbrt(&self) -> Self {
+ if self.is_zero() || self.is_one() {
+ return self.clone();
+ }
+
+ // If we fit in `u64`, compute the root that way.
+ if let Some(x) = self.to_u64() {
+ return x.cbrt().into();
+ }
+
+ let bits = self.bits();
+ let max_bits = bits / 3 as usize + 1;
+
+ let guess = if let Some(f) = self.to_f64() {
+ // We fit in `f64` (lossy), so get a better initial guess from that.
+ BigUint::from_f64(f.cbrt()).unwrap()
+ } else {
+ // Try to guess by scaling down such that it does fit in `f64`.
+ // With some (x * 2³ᵏ), its cbrt ≈ (∛x * 2ᵏ)
+ let extra_bits = bits - (f64::MAX_EXP as usize - 1);
+ let root_scale = (extra_bits + 2) / 3;
+ let scale = root_scale * 3;
+ (self >> scale).cbrt() << root_scale
+ };
+
+ fixpoint(guess, max_bits, move |s| {
+ let q = self / (s * s);
+ let t = (s << 1) + q;
+ t / 3u32
+ })
+ }
+}
+
+fn high_bits_to_u64(v: &BigUint) -> u64 {
+ match v.data.len() {
+ 0 => 0,
+ 1 => u64::from(v.data[0]),
+ _ => {
+ let mut bits = v.bits();
+ let mut ret = 0u64;
+ let mut ret_bits = 0;
+
+ for d in v.data.iter().rev() {
+ let digit_bits = (bits - 1) % big_digit::BITS + 1;
+ let bits_want = cmp::min(64 - ret_bits, digit_bits);
+
+ if bits_want != 64 {
+ ret <<= bits_want;
+ }
+ ret |= u64::from(*d) >> (digit_bits - bits_want);
+ ret_bits += bits_want;
+ bits -= bits_want;
+
+ if ret_bits == 64 {
+ break;
+ }
+ }
+
+ ret
+ }
+ }
+}
+
+impl ToPrimitive for BigUint {
+ #[inline]
+ fn to_i64(&self) -> Option<i64> {
+ self.to_u64().as_ref().and_then(u64::to_i64)
+ }
+
+ #[inline]
+ #[cfg(has_i128)]
+ fn to_i128(&self) -> Option<i128> {
+ self.to_u128().as_ref().and_then(u128::to_i128)
+ }
+
+ #[inline]
+ fn to_u64(&self) -> Option<u64> {
+ let mut ret: u64 = 0;
+ let mut bits = 0;
+
+ for i in self.data.iter() {
+ if bits >= 64 {
+ return None;
+ }
+
+ ret += u64::from(*i) << bits;
+ bits += big_digit::BITS;
+ }
+
+ Some(ret)
+ }
+
+ #[inline]
+ #[cfg(has_i128)]
+ fn to_u128(&self) -> Option<u128> {
+ let mut ret: u128 = 0;
+ let mut bits = 0;
+
+ for i in self.data.iter() {
+ if bits >= 128 {
+ return None;
+ }
+
+ ret |= u128::from(*i) << bits;
+ bits += big_digit::BITS;
+ }
+
+ Some(ret)
+ }
+
+ #[inline]
+ fn to_f32(&self) -> Option<f32> {
+ let mantissa = high_bits_to_u64(self);
+ let exponent = self.bits() - fls(mantissa);
+
+ if exponent > f32::MAX_EXP as usize {
+ None
+ } else {
+ let ret = (mantissa as f32) * 2.0f32.powi(exponent as i32);
+ if ret.is_infinite() {
+ None
+ } else {
+ Some(ret)
+ }
+ }
+ }
+
+ #[inline]
+ fn to_f64(&self) -> Option<f64> {
+ let mantissa = high_bits_to_u64(self);
+ let exponent = self.bits() - fls(mantissa);
+
+ if exponent > f64::MAX_EXP as usize {
+ None
+ } else {
+ let ret = (mantissa as f64) * 2.0f64.powi(exponent as i32);
+ if ret.is_infinite() {
+ None
+ } else {
+ Some(ret)
+ }
+ }
+ }
+}
+
+impl FromPrimitive for BigUint {
+ #[inline]
+ fn from_i64(n: i64) -> Option<BigUint> {
+ if n >= 0 {
+ Some(BigUint::from(n as u64))
+ } else {
+ None
+ }
+ }
+
+ #[inline]
+ #[cfg(has_i128)]
+ fn from_i128(n: i128) -> Option<BigUint> {
+ if n >= 0 {
+ Some(BigUint::from(n as u128))
+ } else {
+ None
+ }
+ }
+
+ #[inline]
+ fn from_u64(n: u64) -> Option<BigUint> {
+ Some(BigUint::from(n))
+ }
+
+ #[inline]
+ #[cfg(has_i128)]
+ fn from_u128(n: u128) -> Option<BigUint> {
+ Some(BigUint::from(n))
+ }
+
+ #[inline]
+ fn from_f64(mut n: f64) -> Option<BigUint> {
+ // handle NAN, INFINITY, NEG_INFINITY
+ if !n.is_finite() {
+ return None;
+ }
+
+ // match the rounding of casting from float to int
+ n = n.trunc();
+
+ // handle 0.x, -0.x
+ if n.is_zero() {
+ return Some(BigUint::zero());
+ }
+
+ let (mantissa, exponent, sign) = Float::integer_decode(n);
+
+ if sign == -1 {
+ return None;
+ }
+
+ let mut ret = BigUint::from(mantissa);
+ if exponent > 0 {
+ ret <<= exponent as usize;
+ } else if exponent < 0 {
+ ret >>= (-exponent) as usize;
+ }
+ Some(ret)
+ }
+}
+
+impl From<u64> for BigUint {
+ #[inline]
+ fn from(mut n: u64) -> Self {
+ let mut ret: BigUint = Zero::zero();
+
+ while n != 0 {
+ ret.data.push(n as BigDigit);
+ // don't overflow if BITS is 64:
+ n = (n >> 1) >> (big_digit::BITS - 1);
+ }
+
+ ret
+ }
+}
+
+#[cfg(has_i128)]
+impl From<u128> for BigUint {
+ #[inline]
+ fn from(mut n: u128) -> Self {
+ let mut ret: BigUint = Zero::zero();
+
+ while n != 0 {
+ ret.data.push(n as BigDigit);
+ n >>= big_digit::BITS;
+ }
+
+ ret
+ }
+}
+
+macro_rules! impl_biguint_from_uint {
+ ($T:ty) => {
+ impl From<$T> for BigUint {
+ #[inline]
+ fn from(n: $T) -> Self {
+ BigUint::from(n as u64)
+ }
+ }
+ };
+}
+
+impl_biguint_from_uint!(u8);
+impl_biguint_from_uint!(u16);
+impl_biguint_from_uint!(u32);
+impl_biguint_from_uint!(usize);
+
+/// A generic trait for converting a value to a `BigUint`.
+pub trait ToBigUint {
+ /// Converts the value of `self` to a `BigUint`.
+ fn to_biguint(&self) -> Option<BigUint>;
+}
+
+impl ToBigUint for BigUint {
+ #[inline]
+ fn to_biguint(&self) -> Option<BigUint> {
+ Some(self.clone())
+ }
+}
+
+macro_rules! impl_to_biguint {
+ ($T:ty, $from_ty:path) => {
+ impl ToBigUint for $T {
+ #[inline]
+ fn to_biguint(&self) -> Option<BigUint> {
+ $from_ty(*self)
+ }
+ }
+ };
+}
+
+impl_to_biguint!(isize, FromPrimitive::from_isize);
+impl_to_biguint!(i8, FromPrimitive::from_i8);
+impl_to_biguint!(i16, FromPrimitive::from_i16);
+impl_to_biguint!(i32, FromPrimitive::from_i32);
+impl_to_biguint!(i64, FromPrimitive::from_i64);
+#[cfg(has_i128)]
+impl_to_biguint!(i128, FromPrimitive::from_i128);
+
+impl_to_biguint!(usize, FromPrimitive::from_usize);
+impl_to_biguint!(u8, FromPrimitive::from_u8);
+impl_to_biguint!(u16, FromPrimitive::from_u16);
+impl_to_biguint!(u32, FromPrimitive::from_u32);
+impl_to_biguint!(u64, FromPrimitive::from_u64);
+#[cfg(has_i128)]
+impl_to_biguint!(u128, FromPrimitive::from_u128);
+
+impl_to_biguint!(f32, FromPrimitive::from_f32);
+impl_to_biguint!(f64, FromPrimitive::from_f64);
+
+// Extract bitwise digits that evenly divide BigDigit
+fn to_bitwise_digits_le(u: &BigUint, bits: usize) -> Vec<u8> {
+ debug_assert!(!u.is_zero() && bits <= 8 && big_digit::BITS % bits == 0);
+
+ let last_i = u.data.len() - 1;
+ let mask: BigDigit = (1 << bits) - 1;
+ let digits_per_big_digit = big_digit::BITS / bits;
+ let digits = (u.bits() + bits - 1) / bits;
+ let mut res = Vec::with_capacity(digits);
+
+ for mut r in u.data[..last_i].iter().cloned() {
+ for _ in 0..digits_per_big_digit {
+ res.push((r & mask) as u8);
+ r >>= bits;
+ }
+ }
+
+ let mut r = u.data[last_i];
+ while r != 0 {
+ res.push((r & mask) as u8);
+ r >>= bits;
+ }
+
+ res
+}
+
+// Extract bitwise digits that don't evenly divide BigDigit
+fn to_inexact_bitwise_digits_le(u: &BigUint, bits: usize) -> Vec<u8> {
+ debug_assert!(!u.is_zero() && bits <= 8 && big_digit::BITS % bits != 0);
+
+ let mask: BigDigit = (1 << bits) - 1;
+ let digits = (u.bits() + bits - 1) / bits;
+ let mut res = Vec::with_capacity(digits);
+
+ let mut r = 0;
+ let mut rbits = 0;
+
+ for c in &u.data {
+ r |= *c << rbits;
+ rbits += big_digit::BITS;
+
+ while rbits >= bits {
+ res.push((r & mask) as u8);
+ r >>= bits;
+
+ // r had more bits than it could fit - grab the bits we lost
+ if rbits > big_digit::BITS {
+ r = *c >> (big_digit::BITS - (rbits - bits));
+ }
+
+ rbits -= bits;
+ }
+ }
+
+ if rbits != 0 {
+ res.push(r as u8);
+ }
+
+ while let Some(&0) = res.last() {
+ res.pop();
+ }
+
+ res
+}
+
+// Extract little-endian radix digits
+#[inline(always)] // forced inline to get const-prop for radix=10
+fn to_radix_digits_le(u: &BigUint, radix: u32) -> Vec<u8> {
+ debug_assert!(!u.is_zero() && !radix.is_power_of_two());
+
+ // Estimate how big the result will be, so we can pre-allocate it.
+ let radix_digits = ((u.bits() as f64) / f64::from(radix).log2()).ceil();
+ let mut res = Vec::with_capacity(radix_digits as usize);
+ let mut digits = u.clone();
+
+ let (base, power) = get_radix_base(radix);
+ let radix = radix as BigDigit;
+
+ while digits.data.len() > 1 {
+ let (q, mut r) = div_rem_digit(digits, base);
+ for _ in 0..power {
+ res.push((r % radix) as u8);
+ r /= radix;
+ }
+ digits = q;
+ }
+
+ let mut r = digits.data[0];
+ while r != 0 {
+ res.push((r % radix) as u8);
+ r /= radix;
+ }
+
+ res
+}
+
+pub fn to_radix_le(u: &BigUint, radix: u32) -> Vec<u8> {
+ if u.is_zero() {
+ vec![0]
+ } else if radix.is_power_of_two() {
+ // Powers of two can use bitwise masks and shifting instead of division
+ let bits = ilog2(radix);
+ if big_digit::BITS % bits == 0 {
+ to_bitwise_digits_le(u, bits)
+ } else {
+ to_inexact_bitwise_digits_le(u, bits)
+ }
+ } else if radix == 10 {
+ // 10 is so common that it's worth separating out for const-propagation.
+ // Optimizers can often turn constant division into a faster multiplication.
+ to_radix_digits_le(u, 10)
+ } else {
+ to_radix_digits_le(u, radix)
+ }
+}
+
+pub fn to_str_radix_reversed(u: &BigUint, radix: u32) -> Vec<u8> {
+ assert!(2 <= radix && radix <= 36, "The radix must be within 2...36");
+
+ if u.is_zero() {
+ return vec![b'0'];
+ }
+
+ let mut res = to_radix_le(u, radix);
+
+ // Now convert everything to ASCII digits.
+ for r in &mut res {
+ debug_assert!(u32::from(*r) < radix);
+ if *r < 10 {
+ *r += b'0';
+ } else {
+ *r += b'a' - 10;
+ }
+ }
+ res
+}
+
+impl BigUint {
+ /// Creates and initializes a `BigUint`.
+ ///
+ /// The base 2<sup>32</sup> digits are ordered least significant digit first.
+ #[inline]
+ pub fn new(digits: Vec<u32>) -> BigUint {
+ BigUint { data: digits }.normalized()
+ }
+
+ /// Creates and initializes a `BigUint`.
+ ///
+ /// The base 2<sup>32</sup> digits are ordered least significant digit first.
+ #[inline]
+ pub fn from_slice(slice: &[u32]) -> BigUint {
+ BigUint::new(slice.to_vec())
+ }
+
+ /// Assign a value to a `BigUint`.
+ ///
+ /// The base 2<sup>32</sup> digits are ordered least significant digit first.
+ #[inline]
+ pub fn assign_from_slice(&mut self, slice: &[u32]) {
+ self.data.resize(slice.len(), 0);
+ self.data.clone_from_slice(slice);
+ self.normalize();
+ }
+
+ /// Creates and initializes a `BigUint`.
+ ///
+ /// The bytes are in big-endian byte order.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use num_bigint::BigUint;
+ ///
+ /// assert_eq!(BigUint::from_bytes_be(b"A"),
+ /// BigUint::parse_bytes(b"65", 10).unwrap());
+ /// assert_eq!(BigUint::from_bytes_be(b"AA"),
+ /// BigUint::parse_bytes(b"16705", 10).unwrap());
+ /// assert_eq!(BigUint::from_bytes_be(b"AB"),
+ /// BigUint::parse_bytes(b"16706", 10).unwrap());
+ /// assert_eq!(BigUint::from_bytes_be(b"Hello world!"),
+ /// BigUint::parse_bytes(b"22405534230753963835153736737", 10).unwrap());
+ /// ```
+ #[inline]
+ pub fn from_bytes_be(bytes: &[u8]) -> BigUint {
+ if bytes.is_empty() {
+ Zero::zero()
+ } else {
+ let mut v = bytes.to_vec();
+ v.reverse();
+ BigUint::from_bytes_le(&*v)
+ }
+ }
+
+ /// Creates and initializes a `BigUint`.
+ ///
+ /// The bytes are in little-endian byte order.
+ #[inline]
+ pub fn from_bytes_le(bytes: &[u8]) -> BigUint {
+ if bytes.is_empty() {
+ Zero::zero()
+ } else {
+ from_bitwise_digits_le(bytes, 8)
+ }
+ }
+
+ /// Creates and initializes a `BigUint`. The input slice must contain
+ /// ascii/utf8 characters in [0-9a-zA-Z].
+ /// `radix` must be in the range `2...36`.
+ ///
+ /// The function `from_str_radix` from the `Num` trait provides the same logic
+ /// for `&str` buffers.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use num_bigint::{BigUint, ToBigUint};
+ ///
+ /// assert_eq!(BigUint::parse_bytes(b"1234", 10), ToBigUint::to_biguint(&1234));
+ /// assert_eq!(BigUint::parse_bytes(b"ABCD", 16), ToBigUint::to_biguint(&0xABCD));
+ /// assert_eq!(BigUint::parse_bytes(b"G", 16), None);
+ /// ```
+ #[inline]
+ pub fn parse_bytes(buf: &[u8], radix: u32) -> Option<BigUint> {
+ str::from_utf8(buf)
+ .ok()
+ .and_then(|s| BigUint::from_str_radix(s, radix).ok())
+ }
+
+ /// Creates and initializes a `BigUint`. Each u8 of the input slice is
+ /// interpreted as one digit of the number
+ /// and must therefore be less than `radix`.
+ ///
+ /// The bytes are in big-endian byte order.
+ /// `radix` must be in the range `2...256`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use num_bigint::{BigUint};
+ ///
+ /// let inbase190 = &[15, 33, 125, 12, 14];
+ /// let a = BigUint::from_radix_be(inbase190, 190).unwrap();
+ /// assert_eq!(a.to_radix_be(190), inbase190);
+ /// ```
+ pub fn from_radix_be(buf: &[u8], radix: u32) -> Option<BigUint> {
+ assert!(
+ 2 <= radix && radix <= 256,
+ "The radix must be within 2...256"
+ );
+
+ if radix != 256 && buf.iter().any(|&b| b >= radix as u8) {
+ return None;
+ }
+
+ let res = if radix.is_power_of_two() {
+ // Powers of two can use bitwise masks and shifting instead of multiplication
+ let bits = ilog2(radix);
+ let mut v = Vec::from(buf);
+ v.reverse();
+ if big_digit::BITS % bits == 0 {
+ from_bitwise_digits_le(&v, bits)
+ } else {
+ from_inexact_bitwise_digits_le(&v, bits)
+ }
+ } else {
+ from_radix_digits_be(buf, radix)
+ };
+
+ Some(res)
+ }
+
+ /// Creates and initializes a `BigUint`. Each u8 of the input slice is
+ /// interpreted as one digit of the number
+ /// and must therefore be less than `radix`.
+ ///
+ /// The bytes are in little-endian byte order.
+ /// `radix` must be in the range `2...256`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use num_bigint::{BigUint};
+ ///
+ /// let inbase190 = &[14, 12, 125, 33, 15];
+ /// let a = BigUint::from_radix_be(inbase190, 190).unwrap();
+ /// assert_eq!(a.to_radix_be(190), inbase190);
+ /// ```
+ pub fn from_radix_le(buf: &[u8], radix: u32) -> Option<BigUint> {
+ assert!(
+ 2 <= radix && radix <= 256,
+ "The radix must be within 2...256"
+ );
+
+ if radix != 256 && buf.iter().any(|&b| b >= radix as u8) {
+ return None;
+ }
+
+ let res = if radix.is_power_of_two() {
+ // Powers of two can use bitwise masks and shifting instead of multiplication
+ let bits = ilog2(radix);
+ if big_digit::BITS % bits == 0 {
+ from_bitwise_digits_le(buf, bits)
+ } else {
+ from_inexact_bitwise_digits_le(buf, bits)
+ }
+ } else {
+ let mut v = Vec::from(buf);
+ v.reverse();
+ from_radix_digits_be(&v, radix)
+ };
+
+ Some(res)
+ }
+
+ /// Returns the byte representation of the `BigUint` in big-endian byte order.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use num_bigint::BigUint;
+ ///
+ /// let i = BigUint::parse_bytes(b"1125", 10).unwrap();
+ /// assert_eq!(i.to_bytes_be(), vec![4, 101]);
+ /// ```
+ #[inline]
+ pub fn to_bytes_be(&self) -> Vec<u8> {
+ let mut v = self.to_bytes_le();
+ v.reverse();
+ v
+ }
+
+ /// Returns the byte representation of the `BigUint` in little-endian byte order.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use num_bigint::BigUint;
+ ///
+ /// let i = BigUint::parse_bytes(b"1125", 10).unwrap();
+ /// assert_eq!(i.to_bytes_le(), vec![101, 4]);
+ /// ```
+ #[inline]
+ pub fn to_bytes_le(&self) -> Vec<u8> {
+ if self.is_zero() {
+ vec![0]
+ } else {
+ to_bitwise_digits_le(self, 8)
+ }
+ }
+
+ /// Returns the `u32` digits representation of the `BigUint` ordered least significant digit
+ /// first.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use num_bigint::BigUint;
+ ///
+ /// assert_eq!(BigUint::from(1125u32).to_u32_digits(), vec![1125]);
+ /// assert_eq!(BigUint::from(4294967295u32).to_u32_digits(), vec![4294967295]);
+ /// assert_eq!(BigUint::from(4294967296u64).to_u32_digits(), vec![0, 1]);
+ /// assert_eq!(BigUint::from(112500000000u64).to_u32_digits(), vec![830850304, 26]);
+ /// ```
+ #[inline]
+ pub fn to_u32_digits(&self) -> Vec<u32> {
+ self.data.clone()
+ }
+
+ /// Returns the integer formatted as a string in the given radix.
+ /// `radix` must be in the range `2...36`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use num_bigint::BigUint;
+ ///
+ /// let i = BigUint::parse_bytes(b"ff", 16).unwrap();
+ /// assert_eq!(i.to_str_radix(16), "ff");
+ /// ```
+ #[inline]
+ pub fn to_str_radix(&self, radix: u32) -> String {
+ let mut v = to_str_radix_reversed(self, radix);
+ v.reverse();
+ unsafe { String::from_utf8_unchecked(v) }
+ }
+
+ /// Returns the integer in the requested base in big-endian digit order.
+ /// The output is not given in a human readable alphabet but as a zero
+ /// based u8 number.
+ /// `radix` must be in the range `2...256`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use num_bigint::BigUint;
+ ///
+ /// assert_eq!(BigUint::from(0xFFFFu64).to_radix_be(159),
+ /// vec![2, 94, 27]);
+ /// // 0xFFFF = 65535 = 2*(159^2) + 94*159 + 27
+ /// ```
+ #[inline]
+ pub fn to_radix_be(&self, radix: u32) -> Vec<u8> {
+ let mut v = to_radix_le(self, radix);
+ v.reverse();
+ v
+ }
+
+ /// Returns the integer in the requested base in little-endian digit order.
+ /// The output is not given in a human readable alphabet but as a zero
+ /// based u8 number.
+ /// `radix` must be in the range `2...256`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use num_bigint::BigUint;
+ ///
+ /// assert_eq!(BigUint::from(0xFFFFu64).to_radix_le(159),
+ /// vec![27, 94, 2]);
+ /// // 0xFFFF = 65535 = 27 + 94*159 + 2*(159^2)
+ /// ```
+ #[inline]
+ pub fn to_radix_le(&self, radix: u32) -> Vec<u8> {
+ to_radix_le(self, radix)
+ }
+
+ /// Determines the fewest bits necessary to express the `BigUint`.
+ #[inline]
+ pub fn bits(&self) -> usize {
+ if self.is_zero() {
+ return 0;
+ }
+ let zeros = self.data.last().unwrap().leading_zeros();
+ self.data.len() * big_digit::BITS - zeros as usize
+ }
+
+ /// Strips off trailing zero bigdigits - comparisons require the last element in the vector to
+ /// be nonzero.
+ #[inline]
+ fn normalize(&mut self) {
+ while let Some(&0) = self.data.last() {
+ self.data.pop();
+ }
+ }
+
+ /// Returns a normalized `BigUint`.
+ #[inline]
+ fn normalized(mut self) -> BigUint {
+ self.normalize();
+ self
+ }
+
+ /// Returns `(self ^ exponent) % modulus`.
+ ///
+ /// Panics if the modulus is zero.
+ pub fn modpow(&self, exponent: &Self, modulus: &Self) -> Self {
+ assert!(!modulus.is_zero(), "divide by zero!");
+
+ if modulus.is_odd() {
+ // For an odd modulus, we can use Montgomery multiplication in base 2^32.
+ monty_modpow(self, exponent, modulus)
+ } else {
+ // Otherwise do basically the same as `num::pow`, but with a modulus.
+ plain_modpow(self, &exponent.data, modulus)
+ }
+ }
+
+ /// Returns the truncated principal square root of `self` --
+ /// see [Roots::sqrt](https://docs.rs/num-integer/0.1/num_integer/trait.Roots.html#method.sqrt)
+ pub fn sqrt(&self) -> Self {
+ Roots::sqrt(self)
+ }
+
+ /// Returns the truncated principal cube root of `self` --
+ /// see [Roots::cbrt](https://docs.rs/num-integer/0.1/num_integer/trait.Roots.html#method.cbrt).
+ pub fn cbrt(&self) -> Self {
+ Roots::cbrt(self)
+ }
+
+ /// Returns the truncated principal `n`th root of `self` --
+ /// see [Roots::nth_root](https://docs.rs/num-integer/0.1/num_integer/trait.Roots.html#tymethod.nth_root).
+ pub fn nth_root(&self, n: u32) -> Self {
+ Roots::nth_root(self, n)
+ }
+}
+
+fn plain_modpow(base: &BigUint, exp_data: &[BigDigit], modulus: &BigUint) -> BigUint {
+ assert!(!modulus.is_zero(), "divide by zero!");
+
+ let i = match exp_data.iter().position(|&r| r != 0) {
+ None => return BigUint::one(),
+ Some(i) => i,
+ };
+
+ let mut base = base % modulus;
+ for _ in 0..i {
+ for _ in 0..big_digit::BITS {
+ base = &base * &base % modulus;
+ }
+ }
+
+ let mut r = exp_data[i];
+ let mut b = 0usize;
+ while r.is_even() {
+ base = &base * &base % modulus;
+ r >>= 1;
+ b += 1;
+ }
+
+ let mut exp_iter = exp_data[i + 1..].iter();
+ if exp_iter.len() == 0 && r.is_one() {
+ return base;
+ }
+
+ let mut acc = base.clone();
+ r >>= 1;
+ b += 1;
+
+ {
+ let mut unit = |exp_is_odd| {
+ base = &base * &base % modulus;
+ if exp_is_odd {
+ acc = &acc * &base % modulus;
+ }
+ };
+
+ if let Some(&last) = exp_iter.next_back() {
+ // consume exp_data[i]
+ for _ in b..big_digit::BITS {
+ unit(r.is_odd());
+ r >>= 1;
+ }
+
+ // consume all other digits before the last
+ for &r in exp_iter {
+ let mut r = r;
+ for _ in 0..big_digit::BITS {
+ unit(r.is_odd());
+ r >>= 1;
+ }
+ }
+ r = last;
+ }
+
+ debug_assert_ne!(r, 0);
+ while !r.is_zero() {
+ unit(r.is_odd());
+ r >>= 1;
+ }
+ }
+ acc
+}
+
+#[test]
+fn test_plain_modpow() {
+ let two = BigUint::from(2u32);
+ let modulus = BigUint::from(0x1100u32);
+
+ let exp = vec![0, 0b1];
+ assert_eq!(
+ two.pow(0b1_00000000_u32) % &modulus,
+ plain_modpow(&two, &exp, &modulus)
+ );
+ let exp = vec![0, 0b10];
+ assert_eq!(
+ two.pow(0b10_00000000_u32) % &modulus,
+ plain_modpow(&two, &exp, &modulus)
+ );
+ let exp = vec![0, 0b110010];
+ assert_eq!(
+ two.pow(0b110010_00000000_u32) % &modulus,
+ plain_modpow(&two, &exp, &modulus)
+ );
+ let exp = vec![0b1, 0b1];
+ assert_eq!(
+ two.pow(0b1_00000001_u32) % &modulus,
+ plain_modpow(&two, &exp, &modulus)
+ );
+ let exp = vec![0b1100, 0, 0b1];
+ assert_eq!(
+ two.pow(0b1_00000000_00001100_u32) % &modulus,
+ plain_modpow(&two, &exp, &modulus)
+ );
+}
+
+/// Returns the number of least-significant bits that are zero,
+/// or `None` if the entire number is zero.
+pub fn trailing_zeros(u: &BigUint) -> Option<usize> {
+ u.data
+ .iter()
+ .enumerate()
+ .find(|&(_, &digit)| digit != 0)
+ .map(|(i, digit)| i * big_digit::BITS + digit.trailing_zeros() as usize)
+}
+
+impl_sum_iter_type!(BigUint);
+impl_product_iter_type!(BigUint);
+
+pub trait IntDigits {
+ fn digits(&self) -> &[BigDigit];
+ fn digits_mut(&mut self) -> &mut Vec<BigDigit>;
+ fn normalize(&mut self);
+ fn capacity(&self) -> usize;
+ fn len(&self) -> usize;
+}
+
+impl IntDigits for BigUint {
+ #[inline]
+ fn digits(&self) -> &[BigDigit] {
+ &self.data
+ }
+ #[inline]
+ fn digits_mut(&mut self) -> &mut Vec<BigDigit> {
+ &mut self.data
+ }
+ #[inline]
+ fn normalize(&mut self) {
+ self.normalize();
+ }
+ #[inline]
+ fn capacity(&self) -> usize {
+ self.data.capacity()
+ }
+ #[inline]
+ fn len(&self) -> usize {
+ self.data.len()
+ }
+}
+
+/// Combine four `u32`s into a single `u128`.
+#[cfg(has_i128)]
+#[inline]
+fn u32_to_u128(a: u32, b: u32, c: u32, d: u32) -> u128 {
+ u128::from(d) | (u128::from(c) << 32) | (u128::from(b) << 64) | (u128::from(a) << 96)
+}
+
+/// Split a single `u128` into four `u32`.
+#[cfg(has_i128)]
+#[inline]
+fn u32_from_u128(n: u128) -> (u32, u32, u32, u32) {
+ (
+ (n >> 96) as u32,
+ (n >> 64) as u32,
+ (n >> 32) as u32,
+ n as u32,
+ )
+}
+
+#[cfg(feature = "serde")]
+impl serde::Serialize for BigUint {
+ fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+ where
+ S: serde::Serializer,
+ {
+ // Note: do not change the serialization format, or it may break forward
+ // and backward compatibility of serialized data! If we ever change the
+ // internal representation, we should still serialize in base-`u32`.
+ let data: &Vec<u32> = &self.data;
+ data.serialize(serializer)
+ }
+}
+
+#[cfg(feature = "serde")]
+impl<'de> serde::Deserialize<'de> for BigUint {
+ fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+ where
+ D: serde::Deserializer<'de>,
+ {
+ let data: Vec<u32> = Vec::deserialize(deserializer)?;
+ Ok(BigUint::new(data))
+ }
+}
+
+/// Returns the greatest power of the radix <= big_digit::BASE
+#[inline]
+fn get_radix_base(radix: u32) -> (BigDigit, usize) {
+ debug_assert!(
+ 2 <= radix && radix <= 256,
+ "The radix must be within 2...256"
+ );
+ debug_assert!(!radix.is_power_of_two());
+
+ // To generate this table:
+ // for radix in 2u64..257 {
+ // let mut power = big_digit::BITS / fls(radix as u64);
+ // let mut base = radix.pow(power as u32);
+ //
+ // while let Some(b) = base.checked_mul(radix) {
+ // if b > big_digit::MAX {
+ // break;
+ // }
+ // base = b;
+ // power += 1;
+ // }
+ //
+ // println!("({:10}, {:2}), // {:2}", base, power, radix);
+ // }
+ // and
+ // for radix in 2u64..257 {
+ // let mut power = 64 / fls(radix as u64);
+ // let mut base = radix.pow(power as u32);
+ //
+ // while let Some(b) = base.checked_mul(radix) {
+ // base = b;
+ // power += 1;
+ // }
+ //
+ // println!("({:20}, {:2}), // {:2}", base, power, radix);
+ // }
+ match big_digit::BITS {
+ 32 => {
+ const BASES: [(u32, usize); 257] = [
+ (0, 0),
+ (0, 0),
+ (0, 0), // 2
+ (3486784401, 20), // 3
+ (0, 0), // 4
+ (1220703125, 13), // 5
+ (2176782336, 12), // 6
+ (1977326743, 11), // 7
+ (0, 0), // 8
+ (3486784401, 10), // 9
+ (1000000000, 9), // 10
+ (2357947691, 9), // 11
+ (429981696, 8), // 12
+ (815730721, 8), // 13
+ (1475789056, 8), // 14
+ (2562890625, 8), // 15
+ (0, 0), // 16
+ (410338673, 7), // 17
+ (612220032, 7), // 18
+ (893871739, 7), // 19
+ (1280000000, 7), // 20
+ (1801088541, 7), // 21
+ (2494357888, 7), // 22
+ (3404825447, 7), // 23
+ (191102976, 6), // 24
+ (244140625, 6), // 25
+ (308915776, 6), // 26
+ (387420489, 6), // 27
+ (481890304, 6), // 28
+ (594823321, 6), // 29
+ (729000000, 6), // 30
+ (887503681, 6), // 31
+ (0, 0), // 32
+ (1291467969, 6), // 33
+ (1544804416, 6), // 34
+ (1838265625, 6), // 35
+ (2176782336, 6), // 36
+ (2565726409, 6), // 37
+ (3010936384, 6), // 38
+ (3518743761, 6), // 39
+ (4096000000, 6), // 40
+ (115856201, 5), // 41
+ (130691232, 5), // 42
+ (147008443, 5), // 43
+ (164916224, 5), // 44
+ (184528125, 5), // 45
+ (205962976, 5), // 46
+ (229345007, 5), // 47
+ (254803968, 5), // 48
+ (282475249, 5), // 49
+ (312500000, 5), // 50
+ (345025251, 5), // 51
+ (380204032, 5), // 52
+ (418195493, 5), // 53
+ (459165024, 5), // 54
+ (503284375, 5), // 55
+ (550731776, 5), // 56
+ (601692057, 5), // 57
+ (656356768, 5), // 58
+ (714924299, 5), // 59
+ (777600000, 5), // 60
+ (844596301, 5), // 61
+ (916132832, 5), // 62
+ (992436543, 5), // 63
+ (0, 0), // 64
+ (1160290625, 5), // 65
+ (1252332576, 5), // 66
+ (1350125107, 5), // 67
+ (1453933568, 5), // 68
+ (1564031349, 5), // 69
+ (1680700000, 5), // 70
+ (1804229351, 5), // 71
+ (1934917632, 5), // 72
+ (2073071593, 5), // 73
+ (2219006624, 5), // 74
+ (2373046875, 5), // 75
+ (2535525376, 5), // 76
+ (2706784157, 5), // 77
+ (2887174368, 5), // 78
+ (3077056399, 5), // 79
+ (3276800000, 5), // 80
+ (3486784401, 5), // 81
+ (3707398432, 5), // 82
+ (3939040643, 5), // 83
+ (4182119424, 5), // 84
+ (52200625, 4), // 85
+ (54700816, 4), // 86
+ (57289761, 4), // 87
+ (59969536, 4), // 88
+ (62742241, 4), // 89
+ (65610000, 4), // 90
+ (68574961, 4), // 91
+ (71639296, 4), // 92
+ (74805201, 4), // 93
+ (78074896, 4), // 94
+ (81450625, 4), // 95
+ (84934656, 4), // 96
+ (88529281, 4), // 97
+ (92236816, 4), // 98
+ (96059601, 4), // 99
+ (100000000, 4), // 100
+ (104060401, 4), // 101
+ (108243216, 4), // 102
+ (112550881, 4), // 103
+ (116985856, 4), // 104
+ (121550625, 4), // 105
+ (126247696, 4), // 106
+ (131079601, 4), // 107
+ (136048896, 4), // 108
+ (141158161, 4), // 109
+ (146410000, 4), // 110
+ (151807041, 4), // 111
+ (157351936, 4), // 112
+ (163047361, 4), // 113
+ (168896016, 4), // 114
+ (174900625, 4), // 115
+ (181063936, 4), // 116
+ (187388721, 4), // 117
+ (193877776, 4), // 118
+ (200533921, 4), // 119
+ (207360000, 4), // 120
+ (214358881, 4), // 121
+ (221533456, 4), // 122
+ (228886641, 4), // 123
+ (236421376, 4), // 124
+ (244140625, 4), // 125
+ (252047376, 4), // 126
+ (260144641, 4), // 127
+ (0, 0), // 128
+ (276922881, 4), // 129
+ (285610000, 4), // 130
+ (294499921, 4), // 131
+ (303595776, 4), // 132
+ (312900721, 4), // 133
+ (322417936, 4), // 134
+ (332150625, 4), // 135
+ (342102016, 4), // 136
+ (352275361, 4), // 137
+ (362673936, 4), // 138
+ (373301041, 4), // 139
+ (384160000, 4), // 140
+ (395254161, 4), // 141
+ (406586896, 4), // 142
+ (418161601, 4), // 143
+ (429981696, 4), // 144
+ (442050625, 4), // 145
+ (454371856, 4), // 146
+ (466948881, 4), // 147
+ (479785216, 4), // 148
+ (492884401, 4), // 149
+ (506250000, 4), // 150
+ (519885601, 4), // 151
+ (533794816, 4), // 152
+ (547981281, 4), // 153
+ (562448656, 4), // 154
+ (577200625, 4), // 155
+ (592240896, 4), // 156
+ (607573201, 4), // 157
+ (623201296, 4), // 158
+ (639128961, 4), // 159
+ (655360000, 4), // 160
+ (671898241, 4), // 161
+ (688747536, 4), // 162
+ (705911761, 4), // 163
+ (723394816, 4), // 164
+ (741200625, 4), // 165
+ (759333136, 4), // 166
+ (777796321, 4), // 167
+ (796594176, 4), // 168
+ (815730721, 4), // 169
+ (835210000, 4), // 170
+ (855036081, 4), // 171
+ (875213056, 4), // 172
+ (895745041, 4), // 173
+ (916636176, 4), // 174
+ (937890625, 4), // 175
+ (959512576, 4), // 176
+ (981506241, 4), // 177
+ (1003875856, 4), // 178
+ (1026625681, 4), // 179
+ (1049760000, 4), // 180
+ (1073283121, 4), // 181
+ (1097199376, 4), // 182
+ (1121513121, 4), // 183
+ (1146228736, 4), // 184
+ (1171350625, 4), // 185
+ (1196883216, 4), // 186
+ (1222830961, 4), // 187
+ (1249198336, 4), // 188
+ (1275989841, 4), // 189
+ (1303210000, 4), // 190
+ (1330863361, 4), // 191
+ (1358954496, 4), // 192
+ (1387488001, 4), // 193
+ (1416468496, 4), // 194
+ (1445900625, 4), // 195
+ (1475789056, 4), // 196
+ (1506138481, 4), // 197
+ (1536953616, 4), // 198
+ (1568239201, 4), // 199
+ (1600000000, 4), // 200
+ (1632240801, 4), // 201
+ (1664966416, 4), // 202
+ (1698181681, 4), // 203
+ (1731891456, 4), // 204
+ (1766100625, 4), // 205
+ (1800814096, 4), // 206
+ (1836036801, 4), // 207
+ (1871773696, 4), // 208
+ (1908029761, 4), // 209
+ (1944810000, 4), // 210
+ (1982119441, 4), // 211
+ (2019963136, 4), // 212
+ (2058346161, 4), // 213
+ (2097273616, 4), // 214
+ (2136750625, 4), // 215
+ (2176782336, 4), // 216
+ (2217373921, 4), // 217
+ (2258530576, 4), // 218
+ (2300257521, 4), // 219
+ (2342560000, 4), // 220
+ (2385443281, 4), // 221
+ (2428912656, 4), // 222
+ (2472973441, 4), // 223
+ (2517630976, 4), // 224
+ (2562890625, 4), // 225
+ (2608757776, 4), // 226
+ (2655237841, 4), // 227
+ (2702336256, 4), // 228
+ (2750058481, 4), // 229
+ (2798410000, 4), // 230
+ (2847396321, 4), // 231
+ (2897022976, 4), // 232
+ (2947295521, 4), // 233
+ (2998219536, 4), // 234
+ (3049800625, 4), // 235
+ (3102044416, 4), // 236
+ (3154956561, 4), // 237
+ (3208542736, 4), // 238
+ (3262808641, 4), // 239
+ (3317760000, 4), // 240
+ (3373402561, 4), // 241
+ (3429742096, 4), // 242
+ (3486784401, 4), // 243
+ (3544535296, 4), // 244
+ (3603000625, 4), // 245
+ (3662186256, 4), // 246
+ (3722098081, 4), // 247
+ (3782742016, 4), // 248
+ (3844124001, 4), // 249
+ (3906250000, 4), // 250
+ (3969126001, 4), // 251
+ (4032758016, 4), // 252
+ (4097152081, 4), // 253
+ (4162314256, 4), // 254
+ (4228250625, 4), // 255
+ (0, 0), // 256
+ ];
+
+ let (base, power) = BASES[radix as usize];
+ (base as BigDigit, power)
+ }
+ 64 => {
+ const BASES: [(u64, usize); 257] = [
+ (0, 0),
+ (0, 0),
+ (9223372036854775808, 63), // 2
+ (12157665459056928801, 40), // 3
+ (4611686018427387904, 31), // 4
+ (7450580596923828125, 27), // 5
+ (4738381338321616896, 24), // 6
+ (3909821048582988049, 22), // 7
+ (9223372036854775808, 21), // 8
+ (12157665459056928801, 20), // 9
+ (10000000000000000000, 19), // 10
+ (5559917313492231481, 18), // 11
+ (2218611106740436992, 17), // 12
+ (8650415919381337933, 17), // 13
+ (2177953337809371136, 16), // 14
+ (6568408355712890625, 16), // 15
+ (1152921504606846976, 15), // 16
+ (2862423051509815793, 15), // 17
+ (6746640616477458432, 15), // 18
+ (15181127029874798299, 15), // 19
+ (1638400000000000000, 14), // 20
+ (3243919932521508681, 14), // 21
+ (6221821273427820544, 14), // 22
+ (11592836324538749809, 14), // 23
+ (876488338465357824, 13), // 24
+ (1490116119384765625, 13), // 25
+ (2481152873203736576, 13), // 26
+ (4052555153018976267, 13), // 27
+ (6502111422497947648, 13), // 28
+ (10260628712958602189, 13), // 29
+ (15943230000000000000, 13), // 30
+ (787662783788549761, 12), // 31
+ (1152921504606846976, 12), // 32
+ (1667889514952984961, 12), // 33
+ (2386420683693101056, 12), // 34
+ (3379220508056640625, 12), // 35
+ (4738381338321616896, 12), // 36
+ (6582952005840035281, 12), // 37
+ (9065737908494995456, 12), // 38
+ (12381557655576425121, 12), // 39
+ (16777216000000000000, 12), // 40
+ (550329031716248441, 11), // 41
+ (717368321110468608, 11), // 42
+ (929293739471222707, 11), // 43
+ (1196683881290399744, 11), // 44
+ (1532278301220703125, 11), // 45
+ (1951354384207722496, 11), // 46
+ (2472159215084012303, 11), // 47
+ (3116402981210161152, 11), // 48
+ (3909821048582988049, 11), // 49
+ (4882812500000000000, 11), // 50
+ (6071163615208263051, 11), // 51
+ (7516865509350965248, 11), // 52
+ (9269035929372191597, 11), // 53
+ (11384956040305711104, 11), // 54
+ (13931233916552734375, 11), // 55
+ (16985107389382393856, 11), // 56
+ (362033331456891249, 10), // 57
+ (430804206899405824, 10), // 58
+ (511116753300641401, 10), // 59
+ (604661760000000000, 10), // 60
+ (713342911662882601, 10), // 61
+ (839299365868340224, 10), // 62
+ (984930291881790849, 10), // 63
+ (1152921504606846976, 10), // 64
+ (1346274334462890625, 10), // 65
+ (1568336880910795776, 10), // 66
+ (1822837804551761449, 10), // 67
+ (2113922820157210624, 10), // 68
+ (2446194060654759801, 10), // 69
+ (2824752490000000000, 10), // 70
+ (3255243551009881201, 10), // 71
+ (3743906242624487424, 10), // 72
+ (4297625829703557649, 10), // 73
+ (4923990397355877376, 10), // 74
+ (5631351470947265625, 10), // 75
+ (6428888932339941376, 10), // 76
+ (7326680472586200649, 10), // 77
+ (8335775831236199424, 10), // 78
+ (9468276082626847201, 10), // 79
+ (10737418240000000000, 10), // 80
+ (12157665459056928801, 10), // 81
+ (13744803133596058624, 10), // 82
+ (15516041187205853449, 10), // 83
+ (17490122876598091776, 10), // 84
+ (231616946283203125, 9), // 85
+ (257327417311663616, 9), // 86
+ (285544154243029527, 9), // 87
+ (316478381828866048, 9), // 88
+ (350356403707485209, 9), // 89
+ (387420489000000000, 9), // 90
+ (427929800129788411, 9), // 91
+ (472161363286556672, 9), // 92
+ (520411082988487293, 9), // 93
+ (572994802228616704, 9), // 94
+ (630249409724609375, 9), // 95
+ (692533995824480256, 9), // 96
+ (760231058654565217, 9), // 97
+ (833747762130149888, 9), // 98
+ (913517247483640899, 9), // 99
+ (1000000000000000000, 9), // 100
+ (1093685272684360901, 9), // 101
+ (1195092568622310912, 9), // 102
+ (1304773183829244583, 9), // 103
+ (1423311812421484544, 9), // 104
+ (1551328215978515625, 9), // 105
+ (1689478959002692096, 9), // 106
+ (1838459212420154507, 9), // 107
+ (1999004627104432128, 9), // 108
+ (2171893279442309389, 9), // 109
+ (2357947691000000000, 9), // 110
+ (2558036924386500591, 9), // 111
+ (2773078757450186752, 9), // 112
+ (3004041937984268273, 9), // 113
+ (3251948521156637184, 9), // 114
+ (3517876291919921875, 9), // 115
+ (3802961274698203136, 9), // 116
+ (4108400332687853397, 9), // 117
+ (4435453859151328768, 9), // 118
+ (4785448563124474679, 9), // 119
+ (5159780352000000000, 9), // 120
+ (5559917313492231481, 9), // 121
+ (5987402799531080192, 9), // 122
+ (6443858614676334363, 9), // 123
+ (6930988311686938624, 9), // 124
+ (7450580596923828125, 9), // 125
+ (8004512848309157376, 9), // 126
+ (8594754748609397887, 9), // 127
+ (9223372036854775808, 9), // 128
+ (9892530380752880769, 9), // 129
+ (10604499373000000000, 9), // 130
+ (11361656654439817571, 9), // 131
+ (12166492167065567232, 9), // 132
+ (13021612539908538853, 9), // 133
+ (13929745610903012864, 9), // 134
+ (14893745087865234375, 9), // 135
+ (15916595351771938816, 9), // 136
+ (17001416405572203977, 9), // 137
+ (18151468971815029248, 9), // 138
+ (139353667211683681, 8), // 139
+ (147578905600000000, 8), // 140
+ (156225851787813921, 8), // 141
+ (165312903998914816, 8), // 142
+ (174859124550883201, 8), // 143
+ (184884258895036416, 8), // 144
+ (195408755062890625, 8), // 145
+ (206453783524884736, 8), // 146
+ (218041257467152161, 8), // 147
+ (230193853492166656, 8), // 148
+ (242935032749128801, 8), // 149
+ (256289062500000000, 8), // 150
+ (270281038127131201, 8), // 151
+ (284936905588473856, 8), // 152
+ (300283484326400961, 8), // 153
+ (316348490636206336, 8), // 154
+ (333160561500390625, 8), // 155
+ (350749278894882816, 8), // 156
+ (369145194573386401, 8), // 157
+ (388379855336079616, 8), // 158
+ (408485828788939521, 8), // 159
+ (429496729600000000, 8), // 160
+ (451447246258894081, 8), // 161
+ (474373168346071296, 8), // 162
+ (498311414318121121, 8), // 163
+ (523300059815673856, 8), // 164
+ (549378366500390625, 8), // 165
+ (576586811427594496, 8), // 166
+ (604967116961135041, 8), // 167
+ (634562281237118976, 8), // 168
+ (665416609183179841, 8), // 169
+ (697575744100000000, 8), // 170
+ (731086699811838561, 8), // 171
+ (765997893392859136, 8), // 172
+ (802359178476091681, 8), // 173
+ (840221879151902976, 8), // 174
+ (879638824462890625, 8), // 175
+ (920664383502155776, 8), // 176
+ (963354501121950081, 8), // 177
+ (1007766734259732736, 8), // 178
+ (1053960288888713761, 8), // 179
+ (1101996057600000000, 8), // 180
+ (1151936657823500641, 8), // 181
+ (1203846470694789376, 8), // 182
+ (1257791680575160641, 8), // 183
+ (1313840315232157696, 8), // 184
+ (1372062286687890625, 8), // 185
+ (1432529432742502656, 8), // 186
+ (1495315559180183521, 8), // 187
+ (1560496482665168896, 8), // 188
+ (1628150074335205281, 8), // 189
+ (1698356304100000000, 8), // 190
+ (1771197285652216321, 8), // 191
+ (1846757322198614016, 8), // 192
+ (1925122952918976001, 8), // 193
+ (2006383000160502016, 8), // 194
+ (2090628617375390625, 8), // 195
+ (2177953337809371136, 8), // 196
+ (2268453123948987361, 8), // 197
+ (2362226417735475456, 8), // 198
+ (2459374191553118401, 8), // 199
+ (2560000000000000000, 8), // 200
+ (2664210032449121601, 8), // 201
+ (2772113166407885056, 8), // 202
+ (2883821021683985761, 8), // 203
+ (2999448015365799936, 8), // 204
+ (3119111417625390625, 8), // 205
+ (3242931408352297216, 8), // 206
+ (3371031134626313601, 8), // 207
+ (3503536769037500416, 8), // 208
+ (3640577568861717121, 8), // 209
+ (3782285936100000000, 8), // 210
+ (3928797478390152481, 8), // 211
+ (4080251070798954496, 8), // 212
+ (4236788918503437921, 8), // 213
+ (4398556620369715456, 8), // 214
+ (4565703233437890625, 8), // 215
+ (4738381338321616896, 8), // 216
+ (4916747105530914241, 8), // 217
+ (5100960362726891776, 8), // 218
+ (5291184662917065441, 8), // 219
+ (5487587353600000000, 8), // 220
+ (5690339646868044961, 8), // 221
+ (5899616690476974336, 8), // 222
+ (6115597639891380481, 8), // 223
+ (6338465731314712576, 8), // 224
+ (6568408355712890625, 8), // 225
+ (6805617133840466176, 8), // 226
+ (7050287992278341281, 8), // 227
+ (7302621240492097536, 8), // 228
+ (7562821648920027361, 8), // 229
+ (7831098528100000000, 8), // 230
+ (8107665808844335041, 8), // 231
+ (8392742123471896576, 8), // 232
+ (8686550888106661441, 8), // 233
+ (8989320386052055296, 8), // 234
+ (9301283852250390625, 8), // 235
+ (9622679558836781056, 8), // 236
+ (9953750901796946721, 8), // 237
+ (10294746488738365696, 8), // 238
+ (10645920227784266881, 8), // 239
+ (11007531417600000000, 8), // 240
+ (11379844838561358721, 8), // 241
+ (11763130845074473216, 8), // 242
+ (12157665459056928801, 8), // 243
+ (12563730464589807616, 8), // 244
+ (12981613503750390625, 8), // 245
+ (13411608173635297536, 8), // 246
+ (13854014124583882561, 8), // 247
+ (14309137159611744256, 8), // 248
+ (14777289335064248001, 8), // 249
+ (15258789062500000000, 8), // 250
+ (15753961211814252001, 8), // 251
+ (16263137215612256256, 8), // 252
+ (16786655174842630561, 8), // 253
+ (17324859965700833536, 8), // 254
+ (17878103347812890625, 8), // 255
+ (72057594037927936, 7), // 256
+ ];
+
+ let (base, power) = BASES[radix as usize];
+ (base as BigDigit, power)
+ }
+ _ => panic!("Invalid bigdigit size"),
+ }
+}
+
+#[test]
+fn test_from_slice() {
+ fn check(slice: &[BigDigit], data: &[BigDigit]) {
+ assert!(BigUint::from_slice(slice).data == data);
+ }
+ check(&[1], &[1]);
+ check(&[0, 0, 0], &[]);
+ check(&[1, 2, 0, 0], &[1, 2]);
+ check(&[0, 0, 1, 2], &[0, 0, 1, 2]);
+ check(&[0, 0, 1, 2, 0, 0], &[0, 0, 1, 2]);
+ check(&[-1i32 as BigDigit], &[-1i32 as BigDigit]);
+}
+
+#[test]
+fn test_assign_from_slice() {
+ fn check(slice: &[BigDigit], data: &[BigDigit]) {
+ let mut p = BigUint::from_slice(&[2627_u32, 0_u32, 9182_u32, 42_u32]);
+ p.assign_from_slice(slice);
+ assert!(p.data == data);
+ }
+ check(&[1], &[1]);
+ check(&[0, 0, 0], &[]);
+ check(&[1, 2, 0, 0], &[1, 2]);
+ check(&[0, 0, 1, 2], &[0, 0, 1, 2]);
+ check(&[0, 0, 1, 2, 0, 0], &[0, 0, 1, 2]);
+ check(&[-1i32 as BigDigit], &[-1i32 as BigDigit]);
+}
+
+#[cfg(has_i128)]
+#[test]
+fn test_u32_u128() {
+ assert_eq!(u32_from_u128(0u128), (0, 0, 0, 0));
+ assert_eq!(
+ u32_from_u128(u128::max_value()),
+ (
+ u32::max_value(),
+ u32::max_value(),
+ u32::max_value(),
+ u32::max_value()
+ )
+ );
+
+ assert_eq!(
+ u32_from_u128(u32::max_value() as u128),
+ (0, 0, 0, u32::max_value())
+ );
+
+ assert_eq!(
+ u32_from_u128(u64::max_value() as u128),
+ (0, 0, u32::max_value(), u32::max_value())
+ );
+
+ assert_eq!(
+ u32_from_u128((u64::max_value() as u128) + u32::max_value() as u128),
+ (0, 1, 0, u32::max_value() - 1)
+ );
+
+ assert_eq!(u32_from_u128(36_893_488_151_714_070_528), (0, 2, 1, 0));
+}
+
+#[cfg(has_i128)]
+#[test]
+fn test_u128_u32_roundtrip() {
+ // roundtrips
+ let values = vec![
+ 0u128,
+ 1u128,
+ u64::max_value() as u128 * 3,
+ u32::max_value() as u128,
+ u64::max_value() as u128,
+ (u64::max_value() as u128) + u32::max_value() as u128,
+ u128::max_value(),
+ ];
+
+ for val in &values {
+ let (a, b, c, d) = u32_from_u128(*val);
+ assert_eq!(u32_to_u128(a, b, c, d), *val);
+ }
+}
+
+#[test]
+fn test_pow_biguint() {
+ let base = BigUint::from(5u8);
+ let exponent = BigUint::from(3u8);
+
+ assert_eq!(BigUint::from(125u8), base.pow(exponent));
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-02-10 03:21:38 +0000