| use crate::big_digit::{self, BigDigit}; |
| use crate::std_alloc::{String, Vec}; |
| |
| use core::cmp; |
| use core::cmp::Ordering; |
| use core::default::Default; |
| use core::fmt; |
| use core::hash; |
| use core::mem; |
| use core::str; |
| use core::{u32, u64, u8}; |
| |
| use num_integer::{Integer, Roots}; |
| use num_traits::{Num, One, Pow, ToPrimitive, Unsigned, Zero}; |
| |
| mod addition; |
| mod division; |
| mod multiplication; |
| mod subtraction; |
| |
| mod bits; |
| mod convert; |
| mod iter; |
| mod monty; |
| mod power; |
| mod shift; |
| |
| #[cfg(any(feature = "quickcheck", feature = "arbitrary"))] |
| mod arbitrary; |
| |
| #[cfg(feature = "serde")] |
| mod serde; |
| |
| pub(crate) use self::convert::to_str_radix_reversed; |
| pub use self::iter::{U32Digits, U64Digits}; |
| |
| /// A big unsigned integer type. |
| pub struct BigUint { |
| data: Vec<BigDigit>, |
| } |
| |
| // Note: derived `Clone` doesn't specialize `clone_from`, |
| // but we want to keep the allocation in `data`. |
| impl Clone for BigUint { |
| #[inline] |
| fn clone(&self) -> Self { |
| BigUint { |
| data: self.data.clone(), |
| } |
| } |
| |
| #[inline] |
| fn clone_from(&mut self, other: &Self) { |
| self.data.clone_from(&other.data); |
| } |
| } |
| |
| impl hash::Hash for BigUint { |
| #[inline] |
| fn hash<H: hash::Hasher>(&self, state: &mut H) { |
| debug_assert!(self.data.last() != Some(&0)); |
| self.data.hash(state); |
| } |
| } |
| |
| impl PartialEq for BigUint { |
| #[inline] |
| fn eq(&self, other: &BigUint) -> bool { |
| debug_assert!(self.data.last() != Some(&0)); |
| debug_assert!(other.data.last() != Some(&0)); |
| self.data == other.data |
| } |
| } |
| 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[..]) |
| } |
| } |
| |
| #[inline] |
| fn cmp_slice(a: &[BigDigit], b: &[BigDigit]) -> Ordering { |
| debug_assert!(a.last() != Some(&0)); |
| debug_assert!(b.last() != Some(&0)); |
| |
| match Ord::cmp(&a.len(), &b.len()) { |
| Ordering::Equal => Iterator::cmp(a.iter().rev(), b.iter().rev()), |
| other => other, |
| } |
| } |
| |
| impl Default for BigUint { |
| #[inline] |
| fn default() -> BigUint { |
| Zero::zero() |
| } |
| } |
| |
| impl fmt::Debug for BigUint { |
| fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| fmt::Display::fmt(self, f) |
| } |
| } |
| |
| 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 Zero for BigUint { |
| #[inline] |
| fn zero() -> BigUint { |
| BigUint { data: 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 { data: 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 Integer for BigUint { |
| #[inline] |
| fn div_rem(&self, other: &BigUint) -> (BigUint, BigUint) { |
| division::div_rem_ref(self, other) |
| } |
| |
| #[inline] |
| fn div_floor(&self, other: &BigUint) -> BigUint { |
| let (d, _) = division::div_rem_ref(self, other); |
| d |
| } |
| |
| #[inline] |
| fn mod_floor(&self, other: &BigUint) -> BigUint { |
| let (_, m) = division::div_rem_ref(self, other); |
| m |
| } |
| |
| #[inline] |
| fn div_mod_floor(&self, other: &BigUint) -> (BigUint, BigUint) { |
| division::div_rem_ref(self, other) |
| } |
| |
| #[inline] |
| fn div_ceil(&self, other: &BigUint) -> BigUint { |
| let (d, m) = division::div_rem_ref(self, other); |
| if m.is_zero() { |
| d |
| } else { |
| d + 1u32 |
| } |
| } |
| |
| /// 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) -> u64 { |
| x.trailing_zeros().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 |
| } |
| } |
| |
| /// Calculates the Greatest Common Divisor (GCD) and |
| /// Lowest Common Multiple (LCM) together. |
| #[inline] |
| fn gcd_lcm(&self, other: &Self) -> (Self, Self) { |
| let gcd = self.gcd(other); |
| let lcm = if gcd.is_zero() { |
| Self::zero() |
| } else { |
| self / &gcd * other |
| }; |
| (gcd, lcm) |
| } |
| |
| /// 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() |
| } |
| |
| /// Rounds up to nearest multiple of argument. |
| #[inline] |
| fn next_multiple_of(&self, other: &Self) -> Self { |
| let m = self.mod_floor(other); |
| if m.is_zero() { |
| self.clone() |
| } else { |
| self + (other - m) |
| } |
| } |
| /// Rounds down to nearest multiple of argument. |
| #[inline] |
| fn prev_multiple_of(&self, other: &Self) -> Self { |
| self - self.mod_floor(other) |
| } |
| } |
| |
| #[inline] |
| fn fixpoint<F>(mut x: BigUint, max_bits: u64, 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(); |
| let n64 = u64::from(n); |
| if bits <= n64 { |
| 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 / n64 + 1; |
| |
| #[cfg(feature = "std")] |
| let guess = match self.to_f64() { |
| Some(f) if f.is_finite() => { |
| use num_traits::FromPrimitive; |
| |
| // We fit in `f64` (lossy), so get a better initial guess from that. |
| BigUint::from_f64((f.ln() / f64::from(n)).exp()).unwrap() |
| } |
| _ => { |
| // Try to guess by scaling down such that it does fit in `f64`. |
| // With some (x * 2ⁿᵏ), its nth root ≈ (ⁿ√x * 2ᵏ) |
| let extra_bits = bits - (core::f64::MAX_EXP as u64 - 1); |
| let root_scale = Integer::div_ceil(&extra_bits, &n64); |
| let scale = root_scale * n64; |
| if scale < bits && bits - scale > n64 { |
| (self >> scale).nth_root(n) << root_scale |
| } else { |
| BigUint::one() << max_bits |
| } |
| } |
| }; |
| |
| #[cfg(not(feature = "std"))] |
| let guess = 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 + 1; |
| |
| #[cfg(feature = "std")] |
| let guess = match self.to_f64() { |
| Some(f) if f.is_finite() => { |
| use num_traits::FromPrimitive; |
| |
| // We fit in `f64` (lossy), so get a better initial guess from that. |
| BigUint::from_f64(f.sqrt()).unwrap() |
| } |
| _ => { |
| // 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 - (core::f64::MAX_EXP as u64 - 1); |
| let root_scale = (extra_bits + 1) / 2; |
| let scale = root_scale * 2; |
| (self >> scale).sqrt() << root_scale |
| } |
| }; |
| |
| #[cfg(not(feature = "std"))] |
| let guess = BigUint::one() << max_bits; |
| |
| 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 + 1; |
| |
| #[cfg(feature = "std")] |
| let guess = match self.to_f64() { |
| Some(f) if f.is_finite() => { |
| use num_traits::FromPrimitive; |
| |
| // We fit in `f64` (lossy), so get a better initial guess from that. |
| BigUint::from_f64(f.cbrt()).unwrap() |
| } |
| _ => { |
| // 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 - (core::f64::MAX_EXP as u64 - 1); |
| let root_scale = (extra_bits + 2) / 3; |
| let scale = root_scale * 3; |
| (self >> scale).cbrt() << root_scale |
| } |
| }; |
| |
| #[cfg(not(feature = "std"))] |
| let guess = BigUint::one() << max_bits; |
| |
| fixpoint(guess, max_bits, move |s| { |
| let q = self / (s * s); |
| let t = (s << 1) + q; |
| t / 3u32 |
| }) |
| } |
| } |
| |
| /// 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>; |
| } |
| |
| /// Creates and initializes a `BigUint`. |
| /// |
| /// The digits are in little-endian base matching `BigDigit`. |
| #[inline] |
| pub(crate) fn biguint_from_vec(digits: Vec<BigDigit>) -> BigUint { |
| BigUint { data: digits }.normalized() |
| } |
| |
| 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 { |
| let mut big = BigUint::zero(); |
| |
| #[cfg(not(u64_digit))] |
| { |
| big.data = digits; |
| big.normalize(); |
| } |
| |
| #[cfg(u64_digit)] |
| big.assign_from_slice(&digits); |
| |
| big |
| } |
| |
| /// 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 { |
| let mut big = BigUint::zero(); |
| big.assign_from_slice(slice); |
| big |
| } |
| |
| /// 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.clear(); |
| |
| #[cfg(not(u64_digit))] |
| self.data.extend_from_slice(slice); |
| |
| #[cfg(u64_digit)] |
| self.data.extend(slice.chunks(2).map(u32_chunk_to_u64)); |
| |
| 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 { |
| convert::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> { |
| let s = str::from_utf8(buf).ok()?; |
| 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> { |
| convert::from_radix_be(buf, radix) |
| } |
| |
| /// 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> { |
| convert::from_radix_le(buf, radix) |
| } |
| |
| /// 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 { |
| convert::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.iter_u32_digits().collect() |
| } |
| |
| /// Returns the `u64` digits representation of the `BigUint` ordered least significant digit |
| /// first. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use num_bigint::BigUint; |
| /// |
| /// assert_eq!(BigUint::from(1125u32).to_u64_digits(), vec![1125]); |
| /// assert_eq!(BigUint::from(4294967295u32).to_u64_digits(), vec![4294967295]); |
| /// assert_eq!(BigUint::from(4294967296u64).to_u64_digits(), vec![4294967296]); |
| /// assert_eq!(BigUint::from(112500000000u64).to_u64_digits(), vec![112500000000]); |
| /// assert_eq!(BigUint::from(1u128 << 64).to_u64_digits(), vec![0, 1]); |
| /// ``` |
| #[inline] |
| pub fn to_u64_digits(&self) -> Vec<u64> { |
| self.iter_u64_digits().collect() |
| } |
| |
| /// Returns an iterator of `u32` digits representation of the `BigUint` ordered least |
| /// significant digit first. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use num_bigint::BigUint; |
| /// |
| /// assert_eq!(BigUint::from(1125u32).iter_u32_digits().collect::<Vec<u32>>(), vec![1125]); |
| /// assert_eq!(BigUint::from(4294967295u32).iter_u32_digits().collect::<Vec<u32>>(), vec![4294967295]); |
| /// assert_eq!(BigUint::from(4294967296u64).iter_u32_digits().collect::<Vec<u32>>(), vec![0, 1]); |
| /// assert_eq!(BigUint::from(112500000000u64).iter_u32_digits().collect::<Vec<u32>>(), vec![830850304, 26]); |
| /// ``` |
| #[inline] |
| pub fn iter_u32_digits(&self) -> U32Digits<'_> { |
| U32Digits::new(self.data.as_slice()) |
| } |
| |
| /// Returns an iterator of `u64` digits representation of the `BigUint` ordered least |
| /// significant digit first. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use num_bigint::BigUint; |
| /// |
| /// assert_eq!(BigUint::from(1125u32).iter_u64_digits().collect::<Vec<u64>>(), vec![1125]); |
| /// assert_eq!(BigUint::from(4294967295u32).iter_u64_digits().collect::<Vec<u64>>(), vec![4294967295]); |
| /// assert_eq!(BigUint::from(4294967296u64).iter_u64_digits().collect::<Vec<u64>>(), vec![4294967296]); |
| /// assert_eq!(BigUint::from(112500000000u64).iter_u64_digits().collect::<Vec<u64>>(), vec![112500000000]); |
| /// assert_eq!(BigUint::from(1u128 << 64).iter_u64_digits().collect::<Vec<u64>>(), vec![0, 1]); |
| /// ``` |
| #[inline] |
| pub fn iter_u64_digits(&self) -> U64Digits<'_> { |
| U64Digits::new(self.data.as_slice()) |
| } |
| |
| /// 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 = convert::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> { |
| convert::to_radix_le(self, radix) |
| } |
| |
| /// Determines the fewest bits necessary to express the `BigUint`. |
| #[inline] |
| pub fn bits(&self) -> u64 { |
| if self.is_zero() { |
| return 0; |
| } |
| let zeros: u64 = self.data.last().unwrap().leading_zeros().into(); |
| self.data.len() as u64 * u64::from(big_digit::BITS) - zeros |
| } |
| |
| /// Strips off trailing zero bigdigits - comparisons require the last element in the vector to |
| /// be nonzero. |
| #[inline] |
| fn normalize(&mut self) { |
| if let Some(&0) = self.data.last() { |
| let len = self.data.iter().rposition(|&d| d != 0).map_or(0, |i| i + 1); |
| self.data.truncate(len); |
| } |
| if self.data.len() < self.data.capacity() / 4 { |
| self.data.shrink_to_fit(); |
| } |
| } |
| |
| /// Returns a normalized `BigUint`. |
| #[inline] |
| fn normalized(mut self) -> BigUint { |
| self.normalize(); |
| self |
| } |
| |
| /// Returns `self ^ exponent`. |
| pub fn pow(&self, exponent: u32) -> Self { |
| Pow::pow(self, exponent) |
| } |
| |
| /// Returns `(self ^ exponent) % modulus`. |
| /// |
| /// Panics if the modulus is zero. |
| pub fn modpow(&self, exponent: &Self, modulus: &Self) -> Self { |
| power::modpow(self, exponent, 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) |
| } |
| |
| /// Returns the number of least-significant bits that are zero, |
| /// or `None` if the entire number is zero. |
| pub fn trailing_zeros(&self) -> Option<u64> { |
| let i = self.data.iter().position(|&digit| digit != 0)?; |
| let zeros: u64 = self.data[i].trailing_zeros().into(); |
| Some(i as u64 * u64::from(big_digit::BITS) + zeros) |
| } |
| |
| /// Returns the number of least-significant bits that are ones. |
| pub fn trailing_ones(&self) -> u64 { |
| if let Some(i) = self.data.iter().position(|&digit| !digit != 0) { |
| // XXX u64::trailing_ones() introduced in Rust 1.46, |
| // but we need to be compatible further back. |
| // Thanks to cuviper for this workaround. |
| let ones: u64 = (!self.data[i]).trailing_zeros().into(); |
| i as u64 * u64::from(big_digit::BITS) + ones |
| } else { |
| self.data.len() as u64 * u64::from(big_digit::BITS) |
| } |
| } |
| |
| /// Returns the number of one bits. |
| pub fn count_ones(&self) -> u64 { |
| self.data.iter().map(|&d| u64::from(d.count_ones())).sum() |
| } |
| |
| /// Returns whether the bit in the given position is set |
| pub fn bit(&self, bit: u64) -> bool { |
| let bits_per_digit = u64::from(big_digit::BITS); |
| if let Some(digit_index) = (bit / bits_per_digit).to_usize() { |
| if let Some(digit) = self.data.get(digit_index) { |
| let bit_mask = (1 as BigDigit) << (bit % bits_per_digit); |
| return (digit & bit_mask) != 0; |
| } |
| } |
| false |
| } |
| |
| /// Sets or clears the bit in the given position |
| /// |
| /// Note that setting a bit greater than the current bit length, a reallocation may be needed |
| /// to store the new digits |
| pub fn set_bit(&mut self, bit: u64, value: bool) { |
| // Note: we're saturating `digit_index` and `new_len` -- any such case is guaranteed to |
| // fail allocation, and that's more consistent than adding our own overflow panics. |
| let bits_per_digit = u64::from(big_digit::BITS); |
| let digit_index = (bit / bits_per_digit) |
| .to_usize() |
| .unwrap_or(core::usize::MAX); |
| let bit_mask = (1 as BigDigit) << (bit % bits_per_digit); |
| if value { |
| if digit_index >= self.data.len() { |
| let new_len = digit_index.saturating_add(1); |
| self.data.resize(new_len, 0); |
| } |
| self.data[digit_index] |= bit_mask; |
| } else if digit_index < self.data.len() { |
| self.data[digit_index] &= !bit_mask; |
| // the top bit may have been cleared, so normalize |
| self.normalize(); |
| } |
| } |
| } |
| |
| pub(crate) 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() |
| } |
| } |
| |
| /// Convert a u32 chunk (len is either 1 or 2) to a single u64 digit |
| #[inline] |
| fn u32_chunk_to_u64(chunk: &[u32]) -> u64 { |
| // raw could have odd length |
| let mut digit = chunk[0] as u64; |
| if let Some(&hi) = chunk.get(1) { |
| digit |= (hi as u64) << 32; |
| } |
| digit |
| } |
| |
| /// Combine four `u32`s into a single `u128`. |
| #[cfg(any(test, not(u64_digit)))] |
| #[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(any(test, not(u64_digit)))] |
| #[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(not(u64_digit))] |
| #[test] |
| fn test_from_slice() { |
| fn check(slice: &[u32], data: &[BigDigit]) { |
| assert_eq!(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 u32], &[-1i32 as BigDigit]); |
| } |
| |
| #[cfg(u64_digit)] |
| #[test] |
| fn test_from_slice() { |
| fn check(slice: &[u32], data: &[BigDigit]) { |
| assert_eq!( |
| BigUint::from_slice(slice).data, |
| data, |
| "from {:?}, to {:?}", |
| slice, |
| data |
| ); |
| } |
| check(&[1], &[1]); |
| check(&[0, 0, 0], &[]); |
| check(&[1, 2], &[8_589_934_593]); |
| check(&[1, 2, 0, 0], &[8_589_934_593]); |
| check(&[0, 0, 1, 2], &[0, 8_589_934_593]); |
| check(&[0, 0, 1, 2, 0, 0], &[0, 8_589_934_593]); |
| check(&[-1i32 as u32], &[(-1i32 as u32) as BigDigit]); |
| } |
| |
| #[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)); |
| } |
| |
| #[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); |
| } |
| } |