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};
pub struct BigUint {
data: Vec<BigDigit>,
}
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
}
}
#[inline]
fn gcd(&self, other: &Self) -> Self {
#[inline]
fn twos(x: &BigUint) -> u64 {
x.trailing_zeros().unwrap_or(0)
}
if self.is_zero() {
return other.clone();
}
if other.is_zero() {
return self.clone();
}
let mut m = self.clone();
let mut n = other.clone();
let shift = cmp::min(twos(&n), twos(&m));
n >>= twos(&n);
while !m.is_zero() {
m >>= twos(&m);
if n > m {
mem::swap(&mut n, &mut m)
}
m -= &n;
}
n << shift
}
#[inline]
fn lcm(&self, other: &BigUint) -> BigUint {
if self.is_zero() && other.is_zero() {
Self::zero()
} else {
self / self.gcd(other) * other
}
}
#[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)
}
#[inline]
fn divides(&self, other: &BigUint) -> bool {
self.is_multiple_of(other)
}
#[inline]
fn is_multiple_of(&self, other: &BigUint) -> bool {
(self % other).is_zero()
}
#[inline]
fn is_even(&self) -> bool {
match self.data.first() {
Some(x) => x.is_even(),
None => true,
}
}
#[inline]
fn is_odd(&self) -> bool {
!self.is_even()
}
#[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)
}
}
#[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);
while x < xn {
x = if xn.bits() > max_bits {
BigUint::one() << max_bits
} else {
xn
};
xn = f(&x);
}
while x > xn {
x = xn;
xn = f(&x);
}
x
}
impl Roots for BigUint {
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 {
1 => return self.clone(),
2 => return self.sqrt(),
3 => return self.cbrt(),
_ => (),
}
let bits = self.bits();
let n64 = u64::from(n);
if bits <= n64 {
return BigUint::one();
}
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;
BigUint::from_f64((f.ln() / f64::from(n)).exp()).unwrap()
}
_ => {
let extra_bits = bits - (core::f64::MAX_EXP as u64 - 1);
let root_scale = extra_bits.div_ceil(&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
})
}
fn sqrt(&self) -> Self {
if self.is_zero() || self.is_one() {
return self.clone();
}
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;
BigUint::from_f64(f.sqrt()).unwrap()
}
_ => {
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 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;
BigUint::from_f64(f.cbrt()).unwrap()
}
_ => {
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
})
}
}
pub trait ToBigUint {
fn to_biguint(&self) -> Option<BigUint>;
}
#[inline]
pub(crate) fn biguint_from_vec(digits: Vec<BigDigit>) -> BigUint {
BigUint { data: digits }.normalized()
}
impl BigUint {
#[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
}
#[inline]
pub fn from_slice(slice: &[u32]) -> BigUint {
let mut big = BigUint::zero();
big.assign_from_slice(slice);
big
}
#[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();
}
#[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)
}
}
#[inline]
pub fn from_bytes_le(bytes: &[u8]) -> BigUint {
if bytes.is_empty() {
Zero::zero()
} else {
convert::from_bitwise_digits_le(bytes, 8)
}
}
#[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()
}
pub fn from_radix_be(buf: &[u8], radix: u32) -> Option<BigUint> {
convert::from_radix_be(buf, radix)
}
pub fn from_radix_le(buf: &[u8], radix: u32) -> Option<BigUint> {
convert::from_radix_le(buf, radix)
}
#[inline]
pub fn to_bytes_be(&self) -> Vec<u8> {
let mut v = self.to_bytes_le();
v.reverse();
v
}
#[inline]
pub fn to_bytes_le(&self) -> Vec<u8> {
if self.is_zero() {
vec![0]
} else {
convert::to_bitwise_digits_le(self, 8)
}
}
#[inline]
pub fn to_u32_digits(&self) -> Vec<u32> {
self.iter_u32_digits().collect()
}
#[inline]
pub fn to_u64_digits(&self) -> Vec<u64> {
self.iter_u64_digits().collect()
}
#[inline]
pub fn iter_u32_digits(&self) -> U32Digits<'_> {
U32Digits::new(self.data.as_slice())
}
#[inline]
pub fn iter_u64_digits(&self) -> U64Digits<'_> {
U64Digits::new(self.data.as_slice())
}
#[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) }
}
#[inline]
pub fn to_radix_be(&self, radix: u32) -> Vec<u8> {
let mut v = convert::to_radix_le(self, radix);
v.reverse();
v
}
#[inline]
pub fn to_radix_le(&self, radix: u32) -> Vec<u8> {
convert::to_radix_le(self, radix)
}
#[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
}
#[inline]
fn normalize(&mut self) {
while let Some(&0) = self.data.last() {
self.data.pop();
}
if self.data.len() < self.data.capacity() / 4 {
self.data.shrink_to_fit();
}
}
#[inline]
fn normalized(mut self) -> BigUint {
self.normalize();
self
}
pub fn pow(&self, exponent: u32) -> Self {
Pow::pow(self, exponent)
}
pub fn modpow(&self, exponent: &Self, modulus: &Self) -> Self {
power::modpow(self, exponent, modulus)
}
pub fn sqrt(&self) -> Self {
Roots::sqrt(self)
}
pub fn cbrt(&self) -> Self {
Roots::cbrt(self)
}
pub fn nth_root(&self, n: u32) -> Self {
Roots::nth_root(self, n)
}
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)
}
pub fn trailing_ones(&self) -> u64 {
if let Some(i) = self.data.iter().position(|&digit| !digit != 0) {
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)
}
}
pub fn count_ones(&self) -> u64 {
self.data.iter().map(|&d| u64::from(d.count_ones())).sum()
}
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
}
pub fn set_bit(&mut self, bit: u64, value: bool) {
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;
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()
}
}
#[inline]
fn u32_chunk_to_u64(chunk: &[u32]) -> u64 {
let mut digit = chunk[0] as u64;
if let Some(&hi) = chunk.get(1) {
digit |= (hi as u64) << 32;
}
digit
}
#[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)
}
#[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() {
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);
}
}