1 // Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! A Big integer (signed version: `BigInt`, unsigned version: `BigUint`).
13 //! A `BigUint` is represented as an array of `BigDigit`s.
14 //! A `BigInt` is a combination of `BigUint` and `Sign`.
16 //! Common numerical operations are overloaded, so we can treat them
17 //! the same way we treat other numbers.
22 //! use num::bigint::BigUint;
23 //! use std::num::{Zero, One};
24 //! use std::mem::replace;
26 //! // Calculate large fibonacci numbers.
27 //! fn fib(n: uint) -> BigUint {
28 //! let mut f0: BigUint = Zero::zero();
29 //! let mut f1: BigUint = One::one();
30 //! for _ in range(0, n) {
32 //! // This is a low cost way of swapping f0 with f1 and f1 with f2.
33 //! f0 = replace(&mut f1, f2);
38 //! // This is a very large number.
39 //! println!("fib(1000) = {}", fib(1000));
42 //! It's easy to generate large random numbers:
45 //! use num::bigint::{ToBigInt, RandBigInt};
48 //! let mut rng = rand::task_rng();
49 //! let a = rng.gen_bigint(1000u);
51 //! let low = -10000i.to_bigint().unwrap();
52 //! let high = 10000i.to_bigint().unwrap();
53 //! let b = rng.gen_bigint_range(&low, &high);
55 //! // Probably an even larger number.
56 //! println!("{}", a * b);
62 use std::{cmp, fmt, hash};
63 use std::default::Default;
64 use std::from_str::FromStr;
65 use std::num::CheckedDiv;
66 use std::num::{ToPrimitive, FromPrimitive};
67 use std::num::{Zero, One, ToStrRadix, FromStrRadix};
68 use std::string::String;
69 use std::{uint, i64, u64};
71 /// A `BigDigit` is a `BigUint`'s composing element.
72 pub type BigDigit = u32;
74 /// A `DoubleBigDigit` is the internal type used to do the computations. Its
75 /// size is the double of the size of `BigDigit`.
76 pub type DoubleBigDigit = u64;
78 pub static ZERO_BIG_DIGIT: BigDigit = 0;
79 static ZERO_VEC: [BigDigit, ..1] = [ZERO_BIG_DIGIT];
81 #[allow(non_snake_case)]
84 use super::DoubleBigDigit;
86 // `DoubleBigDigit` size dependent
87 pub static bits: uint = 32;
89 pub static base: DoubleBigDigit = 1 << bits;
90 static lo_mask: DoubleBigDigit = (-1 as DoubleBigDigit) >> bits;
93 fn get_hi(n: DoubleBigDigit) -> BigDigit { (n >> bits) as BigDigit }
95 fn get_lo(n: DoubleBigDigit) -> BigDigit { (n & lo_mask) as BigDigit }
97 /// Split one `DoubleBigDigit` into two `BigDigit`s.
99 pub fn from_doublebigdigit(n: DoubleBigDigit) -> (BigDigit, BigDigit) {
100 (get_hi(n), get_lo(n))
103 /// Join two `BigDigit`s into one `DoubleBigDigit`
105 pub fn to_doublebigdigit(hi: BigDigit, lo: BigDigit) -> DoubleBigDigit {
106 (lo as DoubleBigDigit) | ((hi as DoubleBigDigit) << bits)
110 /// A big unsigned integer type.
112 /// A `BigUint`-typed value `BigUint { data: vec!(a, b, c) }` represents a number
113 /// `(a + b * BigDigit::base + c * BigDigit::base^2)`.
119 impl PartialEq for BigUint {
121 fn eq(&self, other: &BigUint) -> bool {
122 match self.cmp(other) { Equal => true, _ => false }
125 impl Eq for BigUint {}
127 impl PartialOrd for BigUint {
129 fn partial_cmp(&self, other: &BigUint) -> Option<Ordering> {
130 Some(self.cmp(other))
134 impl Ord for BigUint {
136 fn cmp(&self, other: &BigUint) -> Ordering {
137 let (s_len, o_len) = (self.data.len(), other.data.len());
138 if s_len < o_len { return Less; }
139 if s_len > o_len { return Greater; }
141 for (&self_i, &other_i) in self.data.iter().rev().zip(other.data.iter().rev()) {
142 if self_i < other_i { return Less; }
143 if self_i > other_i { return Greater; }
149 impl Default for BigUint {
151 fn default() -> BigUint { Zero::zero() }
154 impl<S: hash::Writer> hash::Hash<S> for BigUint {
155 fn hash(&self, state: &mut S) {
156 // hash 0 in case it's all 0's
159 let mut found_first_value = false;
160 for elem in self.data.iter().rev() {
161 // don't hash any leading 0's, they shouldn't affect the hash
162 if found_first_value || *elem != 0 {
163 found_first_value = true;
170 impl fmt::Show for BigUint {
171 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
172 write!(f, "{}", self.to_str_radix(10))
176 impl FromStr for BigUint {
178 fn from_str(s: &str) -> Option<BigUint> {
179 FromStrRadix::from_str_radix(s, 10)
183 impl Num for BigUint {}
185 impl BitAnd<BigUint, BigUint> for BigUint {
186 fn bitand(&self, other: &BigUint) -> BigUint {
187 BigUint::new(self.data.iter().zip(other.data.iter()).map(|(ai, bi)| *ai & *bi).collect())
191 impl BitOr<BigUint, BigUint> for BigUint {
192 fn bitor(&self, other: &BigUint) -> BigUint {
193 let zeros = ZERO_VEC.iter().cycle();
194 let (a, b) = if self.data.len() > other.data.len() { (self, other) } else { (other, self) };
195 let ored = a.data.iter().zip(b.data.iter().chain(zeros)).map(
198 return BigUint::new(ored);
202 impl BitXor<BigUint, BigUint> for BigUint {
203 fn bitxor(&self, other: &BigUint) -> BigUint {
204 let zeros = ZERO_VEC.iter().cycle();
205 let (a, b) = if self.data.len() > other.data.len() { (self, other) } else { (other, self) };
206 let xored = a.data.iter().zip(b.data.iter().chain(zeros)).map(
209 return BigUint::new(xored);
213 impl Shl<uint, BigUint> for BigUint {
215 fn shl(&self, rhs: &uint) -> BigUint {
216 let n_unit = *rhs / BigDigit::bits;
217 let n_bits = *rhs % BigDigit::bits;
218 return self.shl_unit(n_unit).shl_bits(n_bits);
222 impl Shr<uint, BigUint> for BigUint {
224 fn shr(&self, rhs: &uint) -> BigUint {
225 let n_unit = *rhs / BigDigit::bits;
226 let n_bits = *rhs % BigDigit::bits;
227 return self.shr_unit(n_unit).shr_bits(n_bits);
231 impl Zero for BigUint {
233 fn zero() -> BigUint { BigUint::new(Vec::new()) }
236 fn is_zero(&self) -> bool { self.data.is_empty() }
239 impl One for BigUint {
241 fn one() -> BigUint { BigUint::new(vec!(1)) }
244 impl Unsigned for BigUint {}
246 impl Add<BigUint, BigUint> for BigUint {
247 fn add(&self, other: &BigUint) -> BigUint {
248 let zeros = ZERO_VEC.iter().cycle();
249 let (a, b) = if self.data.len() > other.data.len() { (self, other) } else { (other, self) };
252 let mut sum: Vec<BigDigit> = a.data.iter().zip(b.data.iter().chain(zeros)).map(|(ai, bi)| {
253 let (hi, lo) = BigDigit::from_doublebigdigit(
254 (*ai as DoubleBigDigit) + (*bi as DoubleBigDigit) + (carry as DoubleBigDigit));
258 if carry != 0 { sum.push(carry); }
259 return BigUint::new(sum);
263 impl Sub<BigUint, BigUint> for BigUint {
264 fn sub(&self, other: &BigUint) -> BigUint {
265 let new_len = cmp::max(self.data.len(), other.data.len());
266 let zeros = ZERO_VEC.iter().cycle();
267 let (a, b) = (self.data.iter().chain(zeros.clone()), other.data.iter().chain(zeros));
270 let diff: Vec<BigDigit> = a.take(new_len).zip(b).map(|(ai, bi)| {
271 let (hi, lo) = BigDigit::from_doublebigdigit(
273 + (*ai as DoubleBigDigit)
274 - (*bi as DoubleBigDigit)
275 - (borrow as DoubleBigDigit)
278 hi * (base) + lo == 1*(base) + ai - bi - borrow
279 => ai - bi - borrow < 0 <=> hi == 0
281 borrow = if hi == 0 { 1 } else { 0 };
286 "Cannot subtract other from self because other is larger than self.");
287 return BigUint::new(diff);
291 impl Mul<BigUint, BigUint> for BigUint {
292 fn mul(&self, other: &BigUint) -> BigUint {
293 if self.is_zero() || other.is_zero() { return Zero::zero(); }
295 let (s_len, o_len) = (self.data.len(), other.data.len());
296 if s_len == 1 { return mul_digit(other, self.data.as_slice()[0]); }
297 if o_len == 1 { return mul_digit(self, other.data.as_slice()[0]); }
299 // Using Karatsuba multiplication
300 // (a1 * base + a0) * (b1 * base + b0)
301 // = a1*b1 * base^2 +
302 // (a1*b1 + a0*b0 - (a1-b0)*(b1-a0)) * base +
304 let half_len = cmp::max(s_len, o_len) / 2;
305 let (s_hi, s_lo) = cut_at(self, half_len);
306 let (o_hi, o_lo) = cut_at(other, half_len);
308 let ll = s_lo * o_lo;
309 let hh = s_hi * o_hi;
311 let (s1, n1) = sub_sign(s_hi, s_lo);
312 let (s2, n2) = sub_sign(o_hi, o_lo);
314 (Equal, _) | (_, Equal) => hh + ll,
315 (Less, Greater) | (Greater, Less) => hh + ll + (n1 * n2),
316 (Less, Less) | (Greater, Greater) => hh + ll - (n1 * n2)
320 return ll + mm.shl_unit(half_len) + hh.shl_unit(half_len * 2);
323 fn mul_digit(a: &BigUint, n: BigDigit) -> BigUint {
324 if n == 0 { return Zero::zero(); }
325 if n == 1 { return (*a).clone(); }
328 let mut prod: Vec<BigDigit> = a.data.iter().map(|ai| {
329 let (hi, lo) = BigDigit::from_doublebigdigit(
330 (*ai as DoubleBigDigit) * (n as DoubleBigDigit) + (carry as DoubleBigDigit)
335 if carry != 0 { prod.push(carry); }
336 return BigUint::new(prod);
340 fn cut_at(a: &BigUint, n: uint) -> (BigUint, BigUint) {
341 let mid = cmp::min(a.data.len(), n);
342 return (BigUint::from_slice(a.data.slice(mid, a.data.len())),
343 BigUint::from_slice(a.data.slice(0, mid)));
347 fn sub_sign(a: BigUint, b: BigUint) -> (Ordering, BigUint) {
349 Less => (Less, b - a),
350 Greater => (Greater, a - b),
351 _ => (Equal, Zero::zero())
357 impl Div<BigUint, BigUint> for BigUint {
359 fn div(&self, other: &BigUint) -> BigUint {
360 let (q, _) = self.div_rem(other);
365 impl Rem<BigUint, BigUint> for BigUint {
367 fn rem(&self, other: &BigUint) -> BigUint {
368 let (_, r) = self.div_rem(other);
373 impl Neg<BigUint> for BigUint {
375 fn neg(&self) -> BigUint { fail!() }
378 impl CheckedAdd for BigUint {
380 fn checked_add(&self, v: &BigUint) -> Option<BigUint> {
381 return Some(self.add(v));
385 impl CheckedSub for BigUint {
387 fn checked_sub(&self, v: &BigUint) -> Option<BigUint> {
391 return Some(self.sub(v));
395 impl CheckedMul for BigUint {
397 fn checked_mul(&self, v: &BigUint) -> Option<BigUint> {
398 return Some(self.mul(v));
402 impl CheckedDiv for BigUint {
404 fn checked_div(&self, v: &BigUint) -> Option<BigUint> {
408 return Some(self.div(v));
412 impl Integer for BigUint {
414 fn div_rem(&self, other: &BigUint) -> (BigUint, BigUint) {
415 self.div_mod_floor(other)
419 fn div_floor(&self, other: &BigUint) -> BigUint {
420 let (d, _) = self.div_mod_floor(other);
425 fn mod_floor(&self, other: &BigUint) -> BigUint {
426 let (_, m) = self.div_mod_floor(other);
430 fn div_mod_floor(&self, other: &BigUint) -> (BigUint, BigUint) {
431 if other.is_zero() { fail!() }
432 if self.is_zero() { return (Zero::zero(), Zero::zero()); }
433 if *other == One::one() { return ((*self).clone(), Zero::zero()); }
435 match self.cmp(other) {
436 Less => return (Zero::zero(), (*self).clone()),
437 Equal => return (One::one(), Zero::zero()),
438 Greater => {} // Do nothing
442 let mut n = *other.data.last().unwrap();
443 while n < (1 << BigDigit::bits - 2) {
447 assert!(shift < BigDigit::bits);
448 let (d, m) = div_mod_floor_inner(self << shift, other << shift);
449 return (d, m >> shift);
452 fn div_mod_floor_inner(a: BigUint, b: BigUint) -> (BigUint, BigUint) {
454 let mut d: BigUint = Zero::zero();
457 let (d0, d_unit, b_unit) = div_estimate(&m, &b, n);
459 let mut prod = b * d0;
461 // FIXME(#5992): assignment operator overloads
464 // FIXME(#5992): assignment operator overloads
473 // FIXME(#5992): assignment operator overloads
476 // FIXME(#5992): assignment operator overloads
484 fn div_estimate(a: &BigUint, b: &BigUint, n: uint)
485 -> (BigUint, BigUint, BigUint) {
486 if a.data.len() < n {
487 return (Zero::zero(), Zero::zero(), (*a).clone());
490 let an = a.data.tailn(a.data.len() - n);
491 let bn = *b.data.last().unwrap();
492 let mut d = Vec::with_capacity(an.len());
494 for elt in an.iter().rev() {
495 let ai = BigDigit::to_doublebigdigit(carry, *elt);
496 let di = ai / (bn as DoubleBigDigit);
497 assert!(di < BigDigit::base);
498 carry = (ai % (bn as DoubleBigDigit)) as BigDigit;
499 d.push(di as BigDigit)
503 let shift = (a.data.len() - an.len()) - (b.data.len() - 1);
505 return (BigUint::new(d), One::one(), (*b).clone());
507 let one: BigUint = One::one();
508 return (BigUint::new(d).shl_unit(shift),
514 /// Calculates the Greatest Common Divisor (GCD) of the number and `other`.
516 /// The result is always positive.
518 fn gcd(&self, other: &BigUint) -> BigUint {
519 // Use Euclid's algorithm
520 let mut m = (*self).clone();
521 let mut n = (*other).clone();
530 /// Calculates the Lowest Common Multiple (LCM) of the number and `other`.
532 fn lcm(&self, other: &BigUint) -> BigUint { ((*self * *other) / self.gcd(other)) }
534 /// Deprecated, use `is_multiple_of` instead.
535 #[deprecated = "function renamed to `is_multiple_of`"]
537 fn divides(&self, other: &BigUint) -> bool { return self.is_multiple_of(other); }
539 /// Returns `true` if the number is a multiple of `other`.
541 fn is_multiple_of(&self, other: &BigUint) -> bool { (*self % *other).is_zero() }
543 /// Returns `true` if the number is divisible by `2`.
545 fn is_even(&self) -> bool {
546 // Considering only the last digit.
547 match self.data.as_slice().head() {
548 Some(x) => x.is_even(),
553 /// Returns `true` if the number is not divisible by `2`.
555 fn is_odd(&self) -> bool { !self.is_even() }
558 impl ToPrimitive for BigUint {
560 fn to_i64(&self) -> Option<i64> {
561 self.to_u64().and_then(|n| {
562 // If top bit of u64 is set, it's too large to convert to i64.
571 // `DoubleBigDigit` size dependent
573 fn to_u64(&self) -> Option<u64> {
574 match self.data.len() {
576 1 => Some(self.data.as_slice()[0] as u64),
577 2 => Some(BigDigit::to_doublebigdigit(self.data.as_slice()[1], self.data.as_slice()[0])
584 impl FromPrimitive for BigUint {
586 fn from_i64(n: i64) -> Option<BigUint> {
588 FromPrimitive::from_u64(n as u64)
596 // `DoubleBigDigit` size dependent
598 fn from_u64(n: u64) -> Option<BigUint> {
599 let n = match BigDigit::from_doublebigdigit(n) {
600 (0, 0) => Zero::zero(),
601 (0, n0) => BigUint::new(vec!(n0)),
602 (n1, n0) => BigUint::new(vec!(n0, n1))
608 /// A generic trait for converting a value to a `BigUint`.
609 pub trait ToBigUint {
610 /// Converts the value of `self` to a `BigUint`.
611 fn to_biguint(&self) -> Option<BigUint>;
614 impl ToBigUint for BigInt {
616 fn to_biguint(&self) -> Option<BigUint> {
617 if self.sign == Plus {
618 Some(self.data.clone())
619 } else if self.sign == Zero {
627 impl ToBigUint for BigUint {
629 fn to_biguint(&self) -> Option<BigUint> {
634 macro_rules! impl_to_biguint(
635 ($T:ty, $from_ty:path) => {
636 impl ToBigUint for $T {
638 fn to_biguint(&self) -> Option<BigUint> {
645 impl_to_biguint!(int, FromPrimitive::from_int)
646 impl_to_biguint!(i8, FromPrimitive::from_i8)
647 impl_to_biguint!(i16, FromPrimitive::from_i16)
648 impl_to_biguint!(i32, FromPrimitive::from_i32)
649 impl_to_biguint!(i64, FromPrimitive::from_i64)
650 impl_to_biguint!(uint, FromPrimitive::from_uint)
651 impl_to_biguint!(u8, FromPrimitive::from_u8)
652 impl_to_biguint!(u16, FromPrimitive::from_u16)
653 impl_to_biguint!(u32, FromPrimitive::from_u32)
654 impl_to_biguint!(u64, FromPrimitive::from_u64)
656 impl ToStrRadix for BigUint {
657 fn to_str_radix(&self, radix: uint) -> String {
658 assert!(1 < radix && radix <= 16, "The radix must be within (1, 16]");
659 let (base, max_len) = get_radix_base(radix);
660 if base == BigDigit::base {
661 return fill_concat(self.data.as_slice(), radix, max_len)
663 return fill_concat(convert_base(self, base).as_slice(), radix, max_len);
665 fn convert_base(n: &BigUint, base: DoubleBigDigit) -> Vec<BigDigit> {
666 let divider = base.to_biguint().unwrap();
667 let mut result = Vec::new();
668 let mut m = n.clone();
670 let (d, m0) = m.div_mod_floor(÷r);
671 result.push(m0.to_uint().unwrap() as BigDigit);
675 result.push(m.to_uint().unwrap() as BigDigit);
680 fn fill_concat(v: &[BigDigit], radix: uint, l: uint) -> String {
682 return "0".to_string()
684 let mut s = String::with_capacity(v.len() * l);
685 for n in v.iter().rev() {
686 let ss = (*n as uint).to_str_radix(radix);
687 s.push_str("0".repeat(l - ss.len()).as_slice());
688 s.push_str(ss.as_slice());
690 s.as_slice().trim_left_chars('0').to_string()
695 impl FromStrRadix for BigUint {
696 /// Creates and initializes a `BigUint`.
698 fn from_str_radix(s: &str, radix: uint) -> Option<BigUint> {
699 BigUint::parse_bytes(s.as_bytes(), radix)
704 /// Creates and initializes a `BigUint`.
706 /// The digits are be in base 2^32.
708 pub fn new(mut digits: Vec<BigDigit>) -> BigUint {
709 // omit trailing zeros
710 let new_len = digits.iter().rposition(|n| *n != 0).map_or(0, |p| p + 1);
711 digits.truncate(new_len);
712 BigUint { data: digits }
715 /// Creates and initializes a `BigUint`.
717 /// The digits are be in base 2^32.
719 pub fn from_slice(slice: &[BigDigit]) -> BigUint {
720 BigUint::new(Vec::from_slice(slice))
723 /// Creates and initializes a `BigUint`.
724 pub fn parse_bytes(buf: &[u8], radix: uint) -> Option<BigUint> {
725 let (base, unit_len) = get_radix_base(radix);
726 let base_num = match base.to_biguint() {
727 Some(base_num) => base_num,
728 None => { return None; }
731 let mut end = buf.len();
732 let mut n: BigUint = Zero::zero();
733 let mut power: BigUint = One::one();
735 let start = cmp::max(end, unit_len) - unit_len;
736 match uint::parse_bytes(buf.slice(start, end), radix) {
738 let d: Option<BigUint> = FromPrimitive::from_uint(d);
741 // FIXME(#5992): assignment operator overloads
745 None => { return None; }
748 None => { return None; }
754 // FIXME(#5992): assignment operator overloads
755 // power *= base_num;
756 power = power * base_num;
761 fn shl_unit(&self, n_unit: uint) -> BigUint {
762 if n_unit == 0 || self.is_zero() { return (*self).clone(); }
764 BigUint::new(Vec::from_elem(n_unit, ZERO_BIG_DIGIT).append(self.data.as_slice()))
768 fn shl_bits(&self, n_bits: uint) -> BigUint {
769 if n_bits == 0 || self.is_zero() { return (*self).clone(); }
772 let mut shifted: Vec<BigDigit> = self.data.iter().map(|elem| {
773 let (hi, lo) = BigDigit::from_doublebigdigit(
774 (*elem as DoubleBigDigit) << n_bits | (carry as DoubleBigDigit)
779 if carry != 0 { shifted.push(carry); }
780 return BigUint::new(shifted);
784 fn shr_unit(&self, n_unit: uint) -> BigUint {
785 if n_unit == 0 { return (*self).clone(); }
786 if self.data.len() < n_unit { return Zero::zero(); }
787 return BigUint::from_slice(
788 self.data.slice(n_unit, self.data.len())
793 fn shr_bits(&self, n_bits: uint) -> BigUint {
794 if n_bits == 0 || self.data.is_empty() { return (*self).clone(); }
797 let mut shifted_rev = Vec::with_capacity(self.data.len());
798 for elem in self.data.iter().rev() {
799 shifted_rev.push((*elem >> n_bits) | borrow);
800 borrow = *elem << (BigDigit::bits - n_bits);
802 let shifted = { shifted_rev.reverse(); shifted_rev };
803 return BigUint::new(shifted);
806 /// Determines the fewest bits necessary to express the `BigUint`.
807 pub fn bits(&self) -> uint {
808 if self.is_zero() { return 0; }
809 let zeros = self.data.last().unwrap().leading_zeros();
810 return self.data.len()*BigDigit::bits - (zeros as uint);
814 // `DoubleBigDigit` size dependent
816 fn get_radix_base(radix: uint) -> (DoubleBigDigit, uint) {
818 2 => (4294967296, 32),
819 3 => (3486784401, 20),
820 4 => (4294967296, 16),
821 5 => (1220703125, 13),
822 6 => (2176782336, 12),
823 7 => (1977326743, 11),
824 8 => (1073741824, 10),
825 9 => (3486784401, 10),
826 10 => (1000000000, 9),
827 11 => (2357947691, 9),
828 12 => (429981696, 8),
829 13 => (815730721, 8),
830 14 => (1475789056, 8),
831 15 => (2562890625, 8),
832 16 => (4294967296, 8),
833 _ => fail!("The radix must be within (1, 16]")
837 /// A Sign is a `BigInt`'s composing element.
838 #[deriving(PartialEq, PartialOrd, Eq, Ord, Clone, Show)]
839 pub enum Sign { Minus, Zero, Plus }
841 impl Neg<Sign> for Sign {
842 /// Negate Sign value.
844 fn neg(&self) -> Sign {
853 /// A big signed integer type.
860 impl PartialEq for BigInt {
862 fn eq(&self, other: &BigInt) -> bool {
863 self.cmp(other) == Equal
867 impl Eq for BigInt {}
869 impl PartialOrd for BigInt {
871 fn partial_cmp(&self, other: &BigInt) -> Option<Ordering> {
872 Some(self.cmp(other))
876 impl Ord for BigInt {
878 fn cmp(&self, other: &BigInt) -> Ordering {
879 let scmp = self.sign.cmp(&other.sign);
880 if scmp != Equal { return scmp; }
884 Plus => self.data.cmp(&other.data),
885 Minus => other.data.cmp(&self.data),
890 impl Default for BigInt {
892 fn default() -> BigInt { Zero::zero() }
895 impl fmt::Show for BigInt {
896 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
897 write!(f, "{}", self.to_str_radix(10))
901 impl<S: hash::Writer> hash::Hash<S> for BigInt {
902 fn hash(&self, state: &mut S) {
903 (self.sign == Plus).hash(state);
904 self.data.hash(state);
908 impl FromStr for BigInt {
910 fn from_str(s: &str) -> Option<BigInt> {
911 FromStrRadix::from_str_radix(s, 10)
915 impl Num for BigInt {}
917 impl Shl<uint, BigInt> for BigInt {
919 fn shl(&self, rhs: &uint) -> BigInt {
920 BigInt::from_biguint(self.sign, self.data << *rhs)
924 impl Shr<uint, BigInt> for BigInt {
926 fn shr(&self, rhs: &uint) -> BigInt {
927 BigInt::from_biguint(self.sign, self.data >> *rhs)
931 impl Zero for BigInt {
933 fn zero() -> BigInt {
934 BigInt::from_biguint(Zero, Zero::zero())
938 fn is_zero(&self) -> bool { self.sign == Zero }
941 impl One for BigInt {
944 BigInt::from_biguint(Plus, One::one())
948 impl Signed for BigInt {
950 fn abs(&self) -> BigInt {
952 Plus | Zero => self.clone(),
953 Minus => BigInt::from_biguint(Plus, self.data.clone())
958 fn abs_sub(&self, other: &BigInt) -> BigInt {
959 if *self <= *other { Zero::zero() } else { *self - *other }
963 fn signum(&self) -> BigInt {
965 Plus => BigInt::from_biguint(Plus, One::one()),
966 Minus => BigInt::from_biguint(Minus, One::one()),
967 Zero => Zero::zero(),
972 fn is_positive(&self) -> bool { self.sign == Plus }
975 fn is_negative(&self) -> bool { self.sign == Minus }
978 impl Add<BigInt, BigInt> for BigInt {
980 fn add(&self, other: &BigInt) -> BigInt {
981 match (self.sign, other.sign) {
982 (Zero, _) => other.clone(),
983 (_, Zero) => self.clone(),
984 (Plus, Plus) => BigInt::from_biguint(Plus, self.data + other.data),
985 (Plus, Minus) => self - (-*other),
986 (Minus, Plus) => other - (-*self),
987 (Minus, Minus) => -((-self) + (-*other))
992 impl Sub<BigInt, BigInt> for BigInt {
994 fn sub(&self, other: &BigInt) -> BigInt {
995 match (self.sign, other.sign) {
997 (_, Zero) => self.clone(),
998 (Plus, Plus) => match self.data.cmp(&other.data) {
999 Less => BigInt::from_biguint(Minus, other.data - self.data),
1000 Greater => BigInt::from_biguint(Plus, self.data - other.data),
1001 Equal => Zero::zero()
1003 (Plus, Minus) => self + (-*other),
1004 (Minus, Plus) => -((-self) + *other),
1005 (Minus, Minus) => (-other) - (-*self)
1010 impl Mul<BigInt, BigInt> for BigInt {
1012 fn mul(&self, other: &BigInt) -> BigInt {
1013 match (self.sign, other.sign) {
1014 (Zero, _) | (_, Zero) => Zero::zero(),
1015 (Plus, Plus) | (Minus, Minus) => {
1016 BigInt::from_biguint(Plus, self.data * other.data)
1018 (Plus, Minus) | (Minus, Plus) => {
1019 BigInt::from_biguint(Minus, self.data * other.data)
1025 impl Div<BigInt, BigInt> for BigInt {
1027 fn div(&self, other: &BigInt) -> BigInt {
1028 let (q, _) = self.div_rem(other);
1033 impl Rem<BigInt, BigInt> for BigInt {
1035 fn rem(&self, other: &BigInt) -> BigInt {
1036 let (_, r) = self.div_rem(other);
1041 impl Neg<BigInt> for BigInt {
1043 fn neg(&self) -> BigInt {
1044 BigInt::from_biguint(self.sign.neg(), self.data.clone())
1048 impl CheckedAdd for BigInt {
1050 fn checked_add(&self, v: &BigInt) -> Option<BigInt> {
1051 return Some(self.add(v));
1055 impl CheckedSub for BigInt {
1057 fn checked_sub(&self, v: &BigInt) -> Option<BigInt> {
1058 return Some(self.sub(v));
1062 impl CheckedMul for BigInt {
1064 fn checked_mul(&self, v: &BigInt) -> Option<BigInt> {
1065 return Some(self.mul(v));
1069 impl CheckedDiv for BigInt {
1071 fn checked_div(&self, v: &BigInt) -> Option<BigInt> {
1075 return Some(self.div(v));
1080 impl Integer for BigInt {
1082 fn div_rem(&self, other: &BigInt) -> (BigInt, BigInt) {
1083 // r.sign == self.sign
1084 let (d_ui, r_ui) = self.data.div_mod_floor(&other.data);
1085 let d = BigInt::from_biguint(Plus, d_ui);
1086 let r = BigInt::from_biguint(Plus, r_ui);
1087 match (self.sign, other.sign) {
1088 (_, Zero) => fail!(),
1089 (Plus, Plus) | (Zero, Plus) => ( d, r),
1090 (Plus, Minus) | (Zero, Minus) => (-d, r),
1091 (Minus, Plus) => (-d, -r),
1092 (Minus, Minus) => ( d, -r)
1097 fn div_floor(&self, other: &BigInt) -> BigInt {
1098 let (d, _) = self.div_mod_floor(other);
1103 fn mod_floor(&self, other: &BigInt) -> BigInt {
1104 let (_, m) = self.div_mod_floor(other);
1108 fn div_mod_floor(&self, other: &BigInt) -> (BigInt, BigInt) {
1109 // m.sign == other.sign
1110 let (d_ui, m_ui) = self.data.div_rem(&other.data);
1111 let d = BigInt::from_biguint(Plus, d_ui);
1112 let m = BigInt::from_biguint(Plus, m_ui);
1113 match (self.sign, other.sign) {
1114 (_, Zero) => fail!(),
1115 (Plus, Plus) | (Zero, Plus) => (d, m),
1116 (Plus, Minus) | (Zero, Minus) => if m.is_zero() {
1119 (-d - One::one(), m + *other)
1121 (Minus, Plus) => if m.is_zero() {
1124 (-d - One::one(), other - m)
1126 (Minus, Minus) => (d, -m)
1130 /// Calculates the Greatest Common Divisor (GCD) of the number and `other`.
1132 /// The result is always positive.
1134 fn gcd(&self, other: &BigInt) -> BigInt {
1135 BigInt::from_biguint(Plus, self.data.gcd(&other.data))
1138 /// Calculates the Lowest Common Multiple (LCM) of the number and `other`.
1140 fn lcm(&self, other: &BigInt) -> BigInt {
1141 BigInt::from_biguint(Plus, self.data.lcm(&other.data))
1144 /// Deprecated, use `is_multiple_of` instead.
1145 #[deprecated = "function renamed to `is_multiple_of`"]
1147 fn divides(&self, other: &BigInt) -> bool { return self.is_multiple_of(other); }
1149 /// Returns `true` if the number is a multiple of `other`.
1151 fn is_multiple_of(&self, other: &BigInt) -> bool { self.data.is_multiple_of(&other.data) }
1153 /// Returns `true` if the number is divisible by `2`.
1155 fn is_even(&self) -> bool { self.data.is_even() }
1157 /// Returns `true` if the number is not divisible by `2`.
1159 fn is_odd(&self) -> bool { self.data.is_odd() }
1162 impl ToPrimitive for BigInt {
1164 fn to_i64(&self) -> Option<i64> {
1166 Plus => self.data.to_i64(),
1169 self.data.to_u64().and_then(|n| {
1170 let m: u64 = 1 << 63;
1184 fn to_u64(&self) -> Option<u64> {
1186 Plus => self.data.to_u64(),
1193 impl FromPrimitive for BigInt {
1195 fn from_i64(n: i64) -> Option<BigInt> {
1197 FromPrimitive::from_u64(n as u64).and_then(|n| {
1198 Some(BigInt::from_biguint(Plus, n))
1201 FromPrimitive::from_u64(u64::MAX - (n as u64) + 1).and_then(
1203 Some(BigInt::from_biguint(Minus, n))
1211 fn from_u64(n: u64) -> Option<BigInt> {
1215 FromPrimitive::from_u64(n).and_then(|n| {
1216 Some(BigInt::from_biguint(Plus, n))
1222 /// A generic trait for converting a value to a `BigInt`.
1223 pub trait ToBigInt {
1224 /// Converts the value of `self` to a `BigInt`.
1225 fn to_bigint(&self) -> Option<BigInt>;
1228 impl ToBigInt for BigInt {
1230 fn to_bigint(&self) -> Option<BigInt> {
1235 impl ToBigInt for BigUint {
1237 fn to_bigint(&self) -> Option<BigInt> {
1241 Some(BigInt { sign: Plus, data: self.clone() })
1246 macro_rules! impl_to_bigint(
1247 ($T:ty, $from_ty:path) => {
1248 impl ToBigInt for $T {
1250 fn to_bigint(&self) -> Option<BigInt> {
1257 impl_to_bigint!(int, FromPrimitive::from_int)
1258 impl_to_bigint!(i8, FromPrimitive::from_i8)
1259 impl_to_bigint!(i16, FromPrimitive::from_i16)
1260 impl_to_bigint!(i32, FromPrimitive::from_i32)
1261 impl_to_bigint!(i64, FromPrimitive::from_i64)
1262 impl_to_bigint!(uint, FromPrimitive::from_uint)
1263 impl_to_bigint!(u8, FromPrimitive::from_u8)
1264 impl_to_bigint!(u16, FromPrimitive::from_u16)
1265 impl_to_bigint!(u32, FromPrimitive::from_u32)
1266 impl_to_bigint!(u64, FromPrimitive::from_u64)
1268 impl ToStrRadix for BigInt {
1270 fn to_str_radix(&self, radix: uint) -> String {
1272 Plus => self.data.to_str_radix(radix),
1273 Zero => "0".to_string(),
1274 Minus => format!("-{}", self.data.to_str_radix(radix)),
1279 impl FromStrRadix for BigInt {
1280 /// Creates and initializes a BigInt.
1282 fn from_str_radix(s: &str, radix: uint) -> Option<BigInt> {
1283 BigInt::parse_bytes(s.as_bytes(), radix)
1287 pub trait RandBigInt {
1288 /// Generate a random `BigUint` of the given bit size.
1289 fn gen_biguint(&mut self, bit_size: uint) -> BigUint;
1291 /// Generate a random BigInt of the given bit size.
1292 fn gen_bigint(&mut self, bit_size: uint) -> BigInt;
1294 /// Generate a random `BigUint` less than the given bound. Fails
1295 /// when the bound is zero.
1296 fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint;
1298 /// Generate a random `BigUint` within the given range. The lower
1299 /// bound is inclusive; the upper bound is exclusive. Fails when
1300 /// the upper bound is not greater than the lower bound.
1301 fn gen_biguint_range(&mut self, lbound: &BigUint, ubound: &BigUint) -> BigUint;
1303 /// Generate a random `BigInt` within the given range. The lower
1304 /// bound is inclusive; the upper bound is exclusive. Fails when
1305 /// the upper bound is not greater than the lower bound.
1306 fn gen_bigint_range(&mut self, lbound: &BigInt, ubound: &BigInt) -> BigInt;
1309 impl<R: Rng> RandBigInt for R {
1310 fn gen_biguint(&mut self, bit_size: uint) -> BigUint {
1311 let (digits, rem) = bit_size.div_rem(&BigDigit::bits);
1312 let mut data = Vec::with_capacity(digits+1);
1313 for _ in range(0, digits) {
1314 data.push(self.gen());
1317 let final_digit: BigDigit = self.gen();
1318 data.push(final_digit >> (BigDigit::bits - rem));
1323 fn gen_bigint(&mut self, bit_size: uint) -> BigInt {
1324 // Generate a random BigUint...
1325 let biguint = self.gen_biguint(bit_size);
1326 // ...and then randomly assign it a Sign...
1327 let sign = if biguint.is_zero() {
1328 // ...except that if the BigUint is zero, we need to try
1329 // again with probability 0.5. This is because otherwise,
1330 // the probability of generating a zero BigInt would be
1331 // double that of any other number.
1333 return self.gen_bigint(bit_size);
1337 } else if self.gen() {
1342 BigInt::from_biguint(sign, biguint)
1345 fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint {
1346 assert!(!bound.is_zero());
1347 let bits = bound.bits();
1349 let n = self.gen_biguint(bits);
1350 if n < *bound { return n; }
1354 fn gen_biguint_range(&mut self,
1358 assert!(*lbound < *ubound);
1359 return *lbound + self.gen_biguint_below(&(*ubound - *lbound));
1362 fn gen_bigint_range(&mut self,
1366 assert!(*lbound < *ubound);
1367 let delta = (*ubound - *lbound).to_biguint().unwrap();
1368 return *lbound + self.gen_biguint_below(&delta).to_bigint().unwrap();
1373 /// Creates and initializes a BigInt.
1375 /// The digits are be in base 2^32.
1377 pub fn new(sign: Sign, digits: Vec<BigDigit>) -> BigInt {
1378 BigInt::from_biguint(sign, BigUint::new(digits))
1381 /// Creates and initializes a `BigInt`.
1383 /// The digits are be in base 2^32.
1385 pub fn from_biguint(sign: Sign, data: BigUint) -> BigInt {
1386 if sign == Zero || data.is_zero() {
1387 return BigInt { sign: Zero, data: Zero::zero() };
1389 BigInt { sign: sign, data: data }
1392 /// Creates and initializes a `BigInt`.
1394 pub fn from_slice(sign: Sign, slice: &[BigDigit]) -> BigInt {
1395 BigInt::from_biguint(sign, BigUint::from_slice(slice))
1398 /// Creates and initializes a `BigInt`.
1399 pub fn parse_bytes(buf: &[u8], radix: uint) -> Option<BigInt> {
1400 if buf.is_empty() { return None; }
1401 let mut sign = Plus;
1407 return BigUint::parse_bytes(buf.slice(start, buf.len()), radix)
1408 .map(|bu| BigInt::from_biguint(sign, bu));
1411 /// Converts this `BigInt` into a `BigUint`, if it's not negative.
1413 pub fn to_biguint(&self) -> Option<BigUint> {
1415 Plus => Some(self.data.clone()),
1416 Zero => Some(Zero::zero()),
1425 use super::{BigDigit, BigUint, ToBigUint};
1426 use super::{Plus, BigInt, RandBigInt, ToBigInt};
1428 use std::cmp::{Less, Equal, Greater};
1429 use std::from_str::FromStr;
1431 use std::num::{Zero, One, FromStrRadix, ToStrRadix};
1432 use std::num::{ToPrimitive, FromPrimitive};
1433 use std::num::CheckedDiv;
1434 use std::rand::task_rng;
1436 use std::hash::hash;
1439 fn test_from_slice() {
1440 fn check(slice: &[BigDigit], data: &[BigDigit]) {
1441 assert!(data == BigUint::from_slice(slice).data.as_slice());
1444 check([0, 0, 0], []);
1445 check([1, 2, 0, 0], [1, 2]);
1446 check([0, 0, 1, 2], [0, 0, 1, 2]);
1447 check([0, 0, 1, 2, 0, 0], [0, 0, 1, 2]);
1453 let data: [&[_], ..7] = [ &[], &[1], &[2], &[-1], &[0, 1], &[2, 1], &[1, 1, 1] ];
1454 let data: Vec<BigUint> = data.iter().map(|v| BigUint::from_slice(*v)).collect();
1455 for (i, ni) in data.iter().enumerate() {
1456 for (j0, nj) in data.slice(i, data.len()).iter().enumerate() {
1459 assert_eq!(ni.cmp(nj), Equal);
1460 assert_eq!(nj.cmp(ni), Equal);
1462 assert!(!(ni != nj));
1465 assert!(!(ni < nj));
1466 assert!(!(ni > nj));
1468 assert_eq!(ni.cmp(nj), Less);
1469 assert_eq!(nj.cmp(ni), Greater);
1471 assert!(!(ni == nj));
1475 assert!(!(ni >= nj));
1477 assert!(!(ni > nj));
1479 assert!(!(nj <= ni));
1481 assert!(!(nj < ni));
1490 let a = BigUint::new(vec!());
1491 let b = BigUint::new(vec!(0));
1492 let c = BigUint::new(vec!(1));
1493 let d = BigUint::new(vec!(1,0,0,0,0,0));
1494 let e = BigUint::new(vec!(0,0,0,0,0,1));
1495 assert!(hash(&a) == hash(&b));
1496 assert!(hash(&b) != hash(&c));
1497 assert!(hash(&c) == hash(&d));
1498 assert!(hash(&d) != hash(&e));
1503 fn check(left: &[BigDigit],
1505 expected: &[BigDigit]) {
1506 assert_eq!(BigUint::from_slice(left) & BigUint::from_slice(right),
1507 BigUint::from_slice(expected));
1510 check([268, 482, 17],
1517 fn check(left: &[BigDigit],
1519 expected: &[BigDigit]) {
1520 assert_eq!(BigUint::from_slice(left) | BigUint::from_slice(right),
1521 BigUint::from_slice(expected));
1524 check([268, 482, 17],
1531 fn check(left: &[BigDigit],
1533 expected: &[BigDigit]) {
1534 assert_eq!(BigUint::from_slice(left) ^ BigUint::from_slice(right),
1535 BigUint::from_slice(expected));
1538 check([268, 482, 17],
1545 fn check(s: &str, shift: uint, ans: &str) {
1546 let opt_biguint: Option<BigUint> = FromStrRadix::from_str_radix(s, 16);
1547 let bu = (opt_biguint.unwrap() << shift).to_str_radix(16);
1548 assert_eq!(bu.as_slice(), ans);
1660 check("88887777666655554444333322221111", 16,
1661 "888877776666555544443333222211110000");
1666 fn check(s: &str, shift: uint, ans: &str) {
1667 let opt_biguint: Option<BigUint> =
1668 FromStrRadix::from_str_radix(s, 16);
1669 let bu = (opt_biguint.unwrap() >> shift).to_str_radix(16);
1670 assert_eq!(bu.as_slice(), ans);
1778 check("888877776666555544443333222211110000", 16,
1779 "88887777666655554444333322221111");
1782 // `DoubleBigDigit` size dependent
1784 fn test_convert_i64() {
1785 fn check(b1: BigUint, i: i64) {
1786 let b2: BigUint = FromPrimitive::from_i64(i).unwrap();
1788 assert!(b1.to_i64().unwrap() == i);
1791 check(Zero::zero(), 0);
1792 check(One::one(), 1);
1793 check(i64::MAX.to_biguint().unwrap(), i64::MAX);
1795 check(BigUint::new(vec!( )), 0);
1796 check(BigUint::new(vec!( 1 )), (1 << (0*BigDigit::bits)));
1797 check(BigUint::new(vec!(-1 )), (1 << (1*BigDigit::bits)) - 1);
1798 check(BigUint::new(vec!( 0, 1 )), (1 << (1*BigDigit::bits)));
1799 check(BigUint::new(vec!(-1, -1 >> 1)), i64::MAX);
1801 assert_eq!(i64::MIN.to_biguint(), None);
1802 assert_eq!(BigUint::new(vec!(-1, -1 )).to_i64(), None);
1803 assert_eq!(BigUint::new(vec!( 0, 0, 1)).to_i64(), None);
1804 assert_eq!(BigUint::new(vec!(-1, -1, -1)).to_i64(), None);
1807 // `DoubleBigDigit` size dependent
1809 fn test_convert_u64() {
1810 fn check(b1: BigUint, u: u64) {
1811 let b2: BigUint = FromPrimitive::from_u64(u).unwrap();
1813 assert!(b1.to_u64().unwrap() == u);
1816 check(Zero::zero(), 0);
1817 check(One::one(), 1);
1818 check(u64::MIN.to_biguint().unwrap(), u64::MIN);
1819 check(u64::MAX.to_biguint().unwrap(), u64::MAX);
1821 check(BigUint::new(vec!( )), 0);
1822 check(BigUint::new(vec!( 1 )), (1 << (0*BigDigit::bits)));
1823 check(BigUint::new(vec!(-1 )), (1 << (1*BigDigit::bits)) - 1);
1824 check(BigUint::new(vec!( 0, 1)), (1 << (1*BigDigit::bits)));
1825 check(BigUint::new(vec!(-1, -1)), u64::MAX);
1827 assert_eq!(BigUint::new(vec!( 0, 0, 1)).to_u64(), None);
1828 assert_eq!(BigUint::new(vec!(-1, -1, -1)).to_u64(), None);
1832 fn test_convert_to_bigint() {
1833 fn check(n: BigUint, ans: BigInt) {
1834 assert_eq!(n.to_bigint().unwrap(), ans);
1835 assert_eq!(n.to_bigint().unwrap().to_biguint().unwrap(), n);
1837 check(Zero::zero(), Zero::zero());
1838 check(BigUint::new(vec!(1,2,3)),
1839 BigInt::from_biguint(Plus, BigUint::new(vec!(1,2,3))));
1842 static sum_triples: &'static [(&'static [BigDigit],
1843 &'static [BigDigit],
1844 &'static [BigDigit])] = &[
1846 (&[], &[ 1], &[ 1]),
1847 (&[ 1], &[ 1], &[ 2]),
1848 (&[ 1], &[ 1, 1], &[ 2, 1]),
1849 (&[ 1], &[-1], &[ 0, 1]),
1850 (&[ 1], &[-1, -1], &[ 0, 0, 1]),
1851 (&[-1, -1], &[-1, -1], &[-2, -1, 1]),
1852 (&[ 1, 1, 1], &[-1, -1], &[ 0, 1, 2]),
1853 (&[ 2, 2, 1], &[-1, -2], &[ 1, 1, 2])
1858 for elm in sum_triples.iter() {
1859 let (a_vec, b_vec, c_vec) = *elm;
1860 let a = BigUint::from_slice(a_vec);
1861 let b = BigUint::from_slice(b_vec);
1862 let c = BigUint::from_slice(c_vec);
1864 assert!(a + b == c);
1865 assert!(b + a == c);
1871 for elm in sum_triples.iter() {
1872 let (a_vec, b_vec, c_vec) = *elm;
1873 let a = BigUint::from_slice(a_vec);
1874 let b = BigUint::from_slice(b_vec);
1875 let c = BigUint::from_slice(c_vec);
1877 assert!(c - a == b);
1878 assert!(c - b == a);
1884 fn test_sub_fail_on_underflow() {
1885 let (a, b) : (BigUint, BigUint) = (Zero::zero(), One::one());
1889 static mul_triples: &'static [(&'static [BigDigit],
1890 &'static [BigDigit],
1891 &'static [BigDigit])] = &[
1895 (&[ 1], &[ 1], &[1]),
1896 (&[ 2], &[ 3], &[ 6]),
1897 (&[ 1], &[ 1, 1, 1], &[1, 1, 1]),
1898 (&[ 1, 2, 3], &[ 3], &[ 3, 6, 9]),
1899 (&[ 1, 1, 1], &[-1], &[-1, -1, -1]),
1900 (&[ 1, 2, 3], &[-1], &[-1, -2, -2, 2]),
1901 (&[ 1, 2, 3, 4], &[-1], &[-1, -2, -2, -2, 3]),
1902 (&[-1], &[-1], &[ 1, -2]),
1903 (&[-1, -1], &[-1], &[ 1, -1, -2]),
1904 (&[-1, -1, -1], &[-1], &[ 1, -1, -1, -2]),
1905 (&[-1, -1, -1, -1], &[-1], &[ 1, -1, -1, -1, -2]),
1906 (&[-1/2 + 1], &[ 2], &[ 0, 1]),
1907 (&[0, -1/2 + 1], &[ 2], &[ 0, 0, 1]),
1908 (&[ 1, 2], &[ 1, 2, 3], &[1, 4, 7, 6]),
1909 (&[-1, -1], &[-1, -1, -1], &[1, 0, -1, -2, -1]),
1910 (&[-1, -1, -1], &[-1, -1, -1, -1], &[1, 0, 0, -1, -2, -1, -1]),
1911 (&[ 0, 0, 1], &[ 1, 2, 3], &[0, 0, 1, 2, 3]),
1912 (&[ 0, 0, 1], &[ 0, 0, 0, 1], &[0, 0, 0, 0, 0, 1])
1915 static div_rem_quadruples: &'static [(&'static [BigDigit],
1916 &'static [BigDigit],
1917 &'static [BigDigit],
1918 &'static [BigDigit])]
1920 (&[ 1], &[ 2], &[], &[1]),
1921 (&[ 1, 1], &[ 2], &[-1/2+1], &[1]),
1922 (&[ 1, 1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
1923 (&[ 0, 1], &[-1], &[1], &[1]),
1924 (&[-1, -1], &[-2], &[2, 1], &[3])
1929 for elm in mul_triples.iter() {
1930 let (a_vec, b_vec, c_vec) = *elm;
1931 let a = BigUint::from_slice(a_vec);
1932 let b = BigUint::from_slice(b_vec);
1933 let c = BigUint::from_slice(c_vec);
1935 assert!(a * b == c);
1936 assert!(b * a == c);
1939 for elm in div_rem_quadruples.iter() {
1940 let (a_vec, b_vec, c_vec, d_vec) = *elm;
1941 let a = BigUint::from_slice(a_vec);
1942 let b = BigUint::from_slice(b_vec);
1943 let c = BigUint::from_slice(c_vec);
1944 let d = BigUint::from_slice(d_vec);
1946 assert!(a == b * c + d);
1947 assert!(a == c * b + d);
1953 for elm in mul_triples.iter() {
1954 let (a_vec, b_vec, c_vec) = *elm;
1955 let a = BigUint::from_slice(a_vec);
1956 let b = BigUint::from_slice(b_vec);
1957 let c = BigUint::from_slice(c_vec);
1960 assert_eq!(c.div_rem(&a), (b.clone(), Zero::zero()));
1963 assert_eq!(c.div_rem(&b), (a.clone(), Zero::zero()));
1967 for elm in div_rem_quadruples.iter() {
1968 let (a_vec, b_vec, c_vec, d_vec) = *elm;
1969 let a = BigUint::from_slice(a_vec);
1970 let b = BigUint::from_slice(b_vec);
1971 let c = BigUint::from_slice(c_vec);
1972 let d = BigUint::from_slice(d_vec);
1974 if !b.is_zero() { assert!(a.div_rem(&b) == (c, d)); }
1979 fn test_checked_add() {
1980 for elm in sum_triples.iter() {
1981 let (aVec, bVec, cVec) = *elm;
1982 let a = BigUint::from_slice(aVec);
1983 let b = BigUint::from_slice(bVec);
1984 let c = BigUint::from_slice(cVec);
1986 assert!(a.checked_add(&b).unwrap() == c);
1987 assert!(b.checked_add(&a).unwrap() == c);
1992 fn test_checked_sub() {
1993 for elm in sum_triples.iter() {
1994 let (aVec, bVec, cVec) = *elm;
1995 let a = BigUint::from_slice(aVec);
1996 let b = BigUint::from_slice(bVec);
1997 let c = BigUint::from_slice(cVec);
1999 assert!(c.checked_sub(&a).unwrap() == b);
2000 assert!(c.checked_sub(&b).unwrap() == a);
2003 assert!(a.checked_sub(&c).is_none());
2006 assert!(b.checked_sub(&c).is_none());
2012 fn test_checked_mul() {
2013 for elm in mul_triples.iter() {
2014 let (aVec, bVec, cVec) = *elm;
2015 let a = BigUint::from_slice(aVec);
2016 let b = BigUint::from_slice(bVec);
2017 let c = BigUint::from_slice(cVec);
2019 assert!(a.checked_mul(&b).unwrap() == c);
2020 assert!(b.checked_mul(&a).unwrap() == c);
2023 for elm in div_rem_quadruples.iter() {
2024 let (aVec, bVec, cVec, dVec) = *elm;
2025 let a = BigUint::from_slice(aVec);
2026 let b = BigUint::from_slice(bVec);
2027 let c = BigUint::from_slice(cVec);
2028 let d = BigUint::from_slice(dVec);
2030 assert!(a == b.checked_mul(&c).unwrap() + d);
2031 assert!(a == c.checked_mul(&b).unwrap() + d);
2036 fn test_checked_div() {
2037 for elm in mul_triples.iter() {
2038 let (aVec, bVec, cVec) = *elm;
2039 let a = BigUint::from_slice(aVec);
2040 let b = BigUint::from_slice(bVec);
2041 let c = BigUint::from_slice(cVec);
2044 assert!(c.checked_div(&a).unwrap() == b);
2047 assert!(c.checked_div(&b).unwrap() == a);
2050 assert!(c.checked_div(&Zero::zero()).is_none());
2056 fn check(a: uint, b: uint, c: uint) {
2057 let big_a: BigUint = FromPrimitive::from_uint(a).unwrap();
2058 let big_b: BigUint = FromPrimitive::from_uint(b).unwrap();
2059 let big_c: BigUint = FromPrimitive::from_uint(c).unwrap();
2061 assert_eq!(big_a.gcd(&big_b), big_c);
2073 fn check(a: uint, b: uint, c: uint) {
2074 let big_a: BigUint = FromPrimitive::from_uint(a).unwrap();
2075 let big_b: BigUint = FromPrimitive::from_uint(b).unwrap();
2076 let big_c: BigUint = FromPrimitive::from_uint(c).unwrap();
2078 assert_eq!(big_a.lcm(&big_b), big_c);
2086 check(99, 17, 1683);
2091 let one: BigUint = FromStr::from_str("1").unwrap();
2092 let two: BigUint = FromStr::from_str("2").unwrap();
2093 let thousand: BigUint = FromStr::from_str("1000").unwrap();
2094 let big: BigUint = FromStr::from_str("1000000000000000000000").unwrap();
2095 let bigger: BigUint = FromStr::from_str("1000000000000000000001").unwrap();
2096 assert!(one.is_odd());
2097 assert!(two.is_even());
2098 assert!(thousand.is_even());
2099 assert!(big.is_even());
2100 assert!(bigger.is_odd());
2101 assert!((one << 64).is_even());
2102 assert!(((one << 64) + one).is_odd());
2105 fn to_str_pairs() -> Vec<(BigUint, Vec<(uint, String)>)> {
2106 let bits = BigDigit::bits;
2107 vec!(( Zero::zero(), vec!(
2108 (2, "0".to_string()), (3, "0".to_string())
2109 )), ( BigUint::from_slice([ 0xff ]), vec!(
2110 (2, "11111111".to_string()),
2111 (3, "100110".to_string()),
2112 (4, "3333".to_string()),
2113 (5, "2010".to_string()),
2114 (6, "1103".to_string()),
2115 (7, "513".to_string()),
2116 (8, "377".to_string()),
2117 (9, "313".to_string()),
2118 (10, "255".to_string()),
2119 (11, "212".to_string()),
2120 (12, "193".to_string()),
2121 (13, "168".to_string()),
2122 (14, "143".to_string()),
2123 (15, "120".to_string()),
2124 (16, "ff".to_string())
2125 )), ( BigUint::from_slice([ 0xfff ]), vec!(
2126 (2, "111111111111".to_string()),
2127 (4, "333333".to_string()),
2128 (16, "fff".to_string())
2129 )), ( BigUint::from_slice([ 1, 2 ]), vec!(
2131 format!("10{}1", "0".repeat(bits - 1))),
2133 format!("2{}1", "0".repeat(bits / 2 - 1))),
2135 32 => "8589934593".to_string(),
2136 16 => "131073".to_string(),
2140 format!("2{}1", "0".repeat(bits / 4 - 1)))
2141 )), ( BigUint::from_slice([ 1, 2, 3 ]), vec!(
2143 format!("11{}10{}1",
2144 "0".repeat(bits - 2),
2145 "0".repeat(bits - 1))),
2148 "0".repeat(bits / 2 - 1),
2149 "0".repeat(bits / 2 - 1))),
2151 32 => "55340232229718589441".to_string(),
2152 16 => "12885032961".to_string(),
2157 "0".repeat(bits / 4 - 1),
2158 "0".repeat(bits / 4 - 1)))
2163 fn test_to_str_radix() {
2164 let r = to_str_pairs();
2165 for num_pair in r.iter() {
2166 let &(ref n, ref rs) = num_pair;
2167 for str_pair in rs.iter() {
2168 let &(ref radix, ref str) = str_pair;
2169 assert_eq!(n.to_str_radix(*radix).as_slice(),
2176 fn test_from_str_radix() {
2177 let r = to_str_pairs();
2178 for num_pair in r.iter() {
2179 let &(ref n, ref rs) = num_pair;
2180 for str_pair in rs.iter() {
2181 let &(ref radix, ref str) = str_pair;
2183 &FromStrRadix::from_str_radix(str.as_slice(),
2188 let zed: Option<BigUint> = FromStrRadix::from_str_radix("Z", 10);
2189 assert_eq!(zed, None);
2190 let blank: Option<BigUint> = FromStrRadix::from_str_radix("_", 2);
2191 assert_eq!(blank, None);
2192 let minus_one: Option<BigUint> = FromStrRadix::from_str_radix("-1",
2194 assert_eq!(minus_one, None);
2199 fn factor(n: uint) -> BigUint {
2200 let mut f: BigUint = One::one();
2201 for i in range(2, n + 1) {
2202 // FIXME(#5992): assignment operator overloads
2203 // f *= FromPrimitive::from_uint(i);
2204 f = f * FromPrimitive::from_uint(i).unwrap();
2209 fn check(n: uint, s: &str) {
2211 let ans = match FromStrRadix::from_str_radix(s, 10) {
2212 Some(x) => x, None => fail!()
2218 check(10, "3628800");
2219 check(20, "2432902008176640000");
2220 check(30, "265252859812191058636308480000000");
2225 assert_eq!(BigUint::new(vec!(0,0,0,0)).bits(), 0);
2226 let n: BigUint = FromPrimitive::from_uint(0).unwrap();
2227 assert_eq!(n.bits(), 0);
2228 let n: BigUint = FromPrimitive::from_uint(1).unwrap();
2229 assert_eq!(n.bits(), 1);
2230 let n: BigUint = FromPrimitive::from_uint(3).unwrap();
2231 assert_eq!(n.bits(), 2);
2232 let n: BigUint = FromStrRadix::from_str_radix("4000000000", 16).unwrap();
2233 assert_eq!(n.bits(), 39);
2234 let one: BigUint = One::one();
2235 assert_eq!((one << 426).bits(), 427);
2240 let mut rng = task_rng();
2241 let _n: BigUint = rng.gen_biguint(137);
2242 assert!(rng.gen_biguint(0).is_zero());
2246 fn test_rand_range() {
2247 let mut rng = task_rng();
2249 for _ in range(0u, 10) {
2250 assert_eq!(rng.gen_bigint_range(&FromPrimitive::from_uint(236).unwrap(),
2251 &FromPrimitive::from_uint(237).unwrap()),
2252 FromPrimitive::from_uint(236).unwrap());
2255 let l = FromPrimitive::from_uint(403469000 + 2352).unwrap();
2256 let u = FromPrimitive::from_uint(403469000 + 3513).unwrap();
2257 for _ in range(0u, 1000) {
2258 let n: BigUint = rng.gen_biguint_below(&u);
2261 let n: BigUint = rng.gen_biguint_range(&l, &u);
2269 fn test_zero_rand_range() {
2270 task_rng().gen_biguint_range(&FromPrimitive::from_uint(54).unwrap(),
2271 &FromPrimitive::from_uint(54).unwrap());
2276 fn test_negative_rand_range() {
2277 let mut rng = task_rng();
2278 let l = FromPrimitive::from_uint(2352).unwrap();
2279 let u = FromPrimitive::from_uint(3513).unwrap();
2280 // Switching u and l should fail:
2281 let _n: BigUint = rng.gen_biguint_range(&u, &l);
2288 use super::{BigDigit, BigUint, ToBigUint};
2289 use super::{Sign, Minus, Zero, Plus, BigInt, RandBigInt, ToBigInt};
2291 use std::cmp::{Less, Equal, Greater};
2293 use std::num::CheckedDiv;
2294 use std::num::{Zero, One, FromStrRadix, ToStrRadix};
2295 use std::num::{ToPrimitive, FromPrimitive};
2296 use std::rand::task_rng;
2298 use std::hash::hash;
2301 fn test_from_biguint() {
2302 fn check(inp_s: Sign, inp_n: uint, ans_s: Sign, ans_n: uint) {
2303 let inp = BigInt::from_biguint(inp_s, FromPrimitive::from_uint(inp_n).unwrap());
2304 let ans = BigInt { sign: ans_s, data: FromPrimitive::from_uint(ans_n).unwrap()};
2305 assert_eq!(inp, ans);
2307 check(Plus, 1, Plus, 1);
2308 check(Plus, 0, Zero, 0);
2309 check(Minus, 1, Minus, 1);
2310 check(Zero, 1, Zero, 0);
2315 let vs: [&[BigDigit], ..4] = [ &[2 as BigDigit], &[1, 1], &[2, 1], &[1, 1, 1] ];
2316 let mut nums = Vec::new();
2317 for s in vs.iter().rev() {
2318 nums.push(BigInt::from_slice(Minus, *s));
2320 nums.push(Zero::zero());
2321 nums.extend(vs.iter().map(|s| BigInt::from_slice(Plus, *s)));
2323 for (i, ni) in nums.iter().enumerate() {
2324 for (j0, nj) in nums.slice(i, nums.len()).iter().enumerate() {
2327 assert_eq!(ni.cmp(nj), Equal);
2328 assert_eq!(nj.cmp(ni), Equal);
2330 assert!(!(ni != nj));
2333 assert!(!(ni < nj));
2334 assert!(!(ni > nj));
2336 assert_eq!(ni.cmp(nj), Less);
2337 assert_eq!(nj.cmp(ni), Greater);
2339 assert!(!(ni == nj));
2343 assert!(!(ni >= nj));
2345 assert!(!(ni > nj));
2347 assert!(!(nj <= ni));
2349 assert!(!(nj < ni));
2358 let a = BigInt::new(Zero, vec!());
2359 let b = BigInt::new(Zero, vec!(0));
2360 let c = BigInt::new(Plus, vec!(1));
2361 let d = BigInt::new(Plus, vec!(1,0,0,0,0,0));
2362 let e = BigInt::new(Plus, vec!(0,0,0,0,0,1));
2363 let f = BigInt::new(Minus, vec!(1));
2364 assert!(hash(&a) == hash(&b));
2365 assert!(hash(&b) != hash(&c));
2366 assert!(hash(&c) == hash(&d));
2367 assert!(hash(&d) != hash(&e));
2368 assert!(hash(&c) != hash(&f));
2372 fn test_convert_i64() {
2373 fn check(b1: BigInt, i: i64) {
2374 let b2: BigInt = FromPrimitive::from_i64(i).unwrap();
2376 assert!(b1.to_i64().unwrap() == i);
2379 check(Zero::zero(), 0);
2380 check(One::one(), 1);
2381 check(i64::MIN.to_bigint().unwrap(), i64::MIN);
2382 check(i64::MAX.to_bigint().unwrap(), i64::MAX);
2385 (i64::MAX as u64 + 1).to_bigint().unwrap().to_i64(),
2389 BigInt::from_biguint(Plus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_i64(),
2393 BigInt::from_biguint(Minus, BigUint::new(vec!(1,0,0,1<<(BigDigit::bits-1)))).to_i64(),
2397 BigInt::from_biguint(Minus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_i64(),
2402 fn test_convert_u64() {
2403 fn check(b1: BigInt, u: u64) {
2404 let b2: BigInt = FromPrimitive::from_u64(u).unwrap();
2406 assert!(b1.to_u64().unwrap() == u);
2409 check(Zero::zero(), 0);
2410 check(One::one(), 1);
2411 check(u64::MIN.to_bigint().unwrap(), u64::MIN);
2412 check(u64::MAX.to_bigint().unwrap(), u64::MAX);
2415 BigInt::from_biguint(Plus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_u64(),
2418 let max_value: BigUint = FromPrimitive::from_u64(u64::MAX).unwrap();
2419 assert_eq!(BigInt::from_biguint(Minus, max_value).to_u64(), None);
2420 assert_eq!(BigInt::from_biguint(Minus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_u64(), None);
2424 fn test_convert_to_biguint() {
2425 fn check(n: BigInt, ans_1: BigUint) {
2426 assert_eq!(n.to_biguint().unwrap(), ans_1);
2427 assert_eq!(n.to_biguint().unwrap().to_bigint().unwrap(), n);
2429 let zero: BigInt = Zero::zero();
2430 let unsigned_zero: BigUint = Zero::zero();
2431 let positive = BigInt::from_biguint(
2432 Plus, BigUint::new(vec!(1,2,3)));
2433 let negative = -positive;
2435 check(zero, unsigned_zero);
2436 check(positive, BigUint::new(vec!(1,2,3)));
2438 assert_eq!(negative.to_biguint(), None);
2441 static sum_triples: &'static [(&'static [BigDigit],
2442 &'static [BigDigit],
2443 &'static [BigDigit])] = &[
2445 (&[], &[ 1], &[ 1]),
2446 (&[ 1], &[ 1], &[ 2]),
2447 (&[ 1], &[ 1, 1], &[ 2, 1]),
2448 (&[ 1], &[-1], &[ 0, 1]),
2449 (&[ 1], &[-1, -1], &[ 0, 0, 1]),
2450 (&[-1, -1], &[-1, -1], &[-2, -1, 1]),
2451 (&[ 1, 1, 1], &[-1, -1], &[ 0, 1, 2]),
2452 (&[ 2, 2, 1], &[-1, -2], &[ 1, 1, 2])
2457 for elm in sum_triples.iter() {
2458 let (a_vec, b_vec, c_vec) = *elm;
2459 let a = BigInt::from_slice(Plus, a_vec);
2460 let b = BigInt::from_slice(Plus, b_vec);
2461 let c = BigInt::from_slice(Plus, c_vec);
2463 assert!(a + b == c);
2464 assert!(b + a == c);
2465 assert!(c + (-a) == b);
2466 assert!(c + (-b) == a);
2467 assert!(a + (-c) == (-b));
2468 assert!(b + (-c) == (-a));
2469 assert!((-a) + (-b) == (-c))
2470 assert!(a + (-a) == Zero::zero());
2476 for elm in sum_triples.iter() {
2477 let (a_vec, b_vec, c_vec) = *elm;
2478 let a = BigInt::from_slice(Plus, a_vec);
2479 let b = BigInt::from_slice(Plus, b_vec);
2480 let c = BigInt::from_slice(Plus, c_vec);
2482 assert!(c - a == b);
2483 assert!(c - b == a);
2484 assert!((-b) - a == (-c))
2485 assert!((-a) - b == (-c))
2486 assert!(b - (-a) == c);
2487 assert!(a - (-b) == c);
2488 assert!((-c) - (-a) == (-b));
2489 assert!(a - a == Zero::zero());
2493 static mul_triples: &'static [(&'static [BigDigit],
2494 &'static [BigDigit],
2495 &'static [BigDigit])] = &[
2499 (&[ 1], &[ 1], &[1]),
2500 (&[ 2], &[ 3], &[ 6]),
2501 (&[ 1], &[ 1, 1, 1], &[1, 1, 1]),
2502 (&[ 1, 2, 3], &[ 3], &[ 3, 6, 9]),
2503 (&[ 1, 1, 1], &[-1], &[-1, -1, -1]),
2504 (&[ 1, 2, 3], &[-1], &[-1, -2, -2, 2]),
2505 (&[ 1, 2, 3, 4], &[-1], &[-1, -2, -2, -2, 3]),
2506 (&[-1], &[-1], &[ 1, -2]),
2507 (&[-1, -1], &[-1], &[ 1, -1, -2]),
2508 (&[-1, -1, -1], &[-1], &[ 1, -1, -1, -2]),
2509 (&[-1, -1, -1, -1], &[-1], &[ 1, -1, -1, -1, -2]),
2510 (&[-1/2 + 1], &[ 2], &[ 0, 1]),
2511 (&[0, -1/2 + 1], &[ 2], &[ 0, 0, 1]),
2512 (&[ 1, 2], &[ 1, 2, 3], &[1, 4, 7, 6]),
2513 (&[-1, -1], &[-1, -1, -1], &[1, 0, -1, -2, -1]),
2514 (&[-1, -1, -1], &[-1, -1, -1, -1], &[1, 0, 0, -1, -2, -1, -1]),
2515 (&[ 0, 0, 1], &[ 1, 2, 3], &[0, 0, 1, 2, 3]),
2516 (&[ 0, 0, 1], &[ 0, 0, 0, 1], &[0, 0, 0, 0, 0, 1])
2519 static div_rem_quadruples: &'static [(&'static [BigDigit],
2520 &'static [BigDigit],
2521 &'static [BigDigit],
2522 &'static [BigDigit])]
2524 (&[ 1], &[ 2], &[], &[1]),
2525 (&[ 1, 1], &[ 2], &[-1/2+1], &[1]),
2526 (&[ 1, 1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
2527 (&[ 0, 1], &[-1], &[1], &[1]),
2528 (&[-1, -1], &[-2], &[2, 1], &[3])
2533 for elm in mul_triples.iter() {
2534 let (a_vec, b_vec, c_vec) = *elm;
2535 let a = BigInt::from_slice(Plus, a_vec);
2536 let b = BigInt::from_slice(Plus, b_vec);
2537 let c = BigInt::from_slice(Plus, c_vec);
2539 assert!(a * b == c);
2540 assert!(b * a == c);
2542 assert!((-a) * b == -c);
2543 assert!((-b) * a == -c);
2546 for elm in div_rem_quadruples.iter() {
2547 let (a_vec, b_vec, c_vec, d_vec) = *elm;
2548 let a = BigInt::from_slice(Plus, a_vec);
2549 let b = BigInt::from_slice(Plus, b_vec);
2550 let c = BigInt::from_slice(Plus, c_vec);
2551 let d = BigInt::from_slice(Plus, d_vec);
2553 assert!(a == b * c + d);
2554 assert!(a == c * b + d);
2559 fn test_div_mod_floor() {
2560 fn check_sub(a: &BigInt, b: &BigInt, ans_d: &BigInt, ans_m: &BigInt) {
2561 let (d, m) = a.div_mod_floor(b);
2563 assert_eq!(m.sign, b.sign);
2565 assert!(m.abs() <= b.abs());
2566 assert!(*a == b * d + m);
2567 assert!(d == *ans_d);
2568 assert!(m == *ans_m);
2571 fn check(a: &BigInt, b: &BigInt, d: &BigInt, m: &BigInt) {
2573 check_sub(a, b, d, m);
2574 check_sub(a, &b.neg(), &d.neg(), m);
2575 check_sub(&a.neg(), b, &d.neg(), m);
2576 check_sub(&a.neg(), &b.neg(), d, m);
2578 check_sub(a, b, d, m);
2579 check_sub(a, &b.neg(), &(d.neg() - One::one()), &(m - *b));
2580 check_sub(&a.neg(), b, &(d.neg() - One::one()), &(b - *m));
2581 check_sub(&a.neg(), &b.neg(), d, &m.neg());
2585 for elm in mul_triples.iter() {
2586 let (a_vec, b_vec, c_vec) = *elm;
2587 let a = BigInt::from_slice(Plus, a_vec);
2588 let b = BigInt::from_slice(Plus, b_vec);
2589 let c = BigInt::from_slice(Plus, c_vec);
2591 if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
2592 if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
2595 for elm in div_rem_quadruples.iter() {
2596 let (a_vec, b_vec, c_vec, d_vec) = *elm;
2597 let a = BigInt::from_slice(Plus, a_vec);
2598 let b = BigInt::from_slice(Plus, b_vec);
2599 let c = BigInt::from_slice(Plus, c_vec);
2600 let d = BigInt::from_slice(Plus, d_vec);
2603 check(&a, &b, &c, &d);
2611 fn check_sub(a: &BigInt, b: &BigInt, ans_q: &BigInt, ans_r: &BigInt) {
2612 let (q, r) = a.div_rem(b);
2614 assert_eq!(r.sign, a.sign);
2616 assert!(r.abs() <= b.abs());
2617 assert!(*a == b * q + r);
2618 assert!(q == *ans_q);
2619 assert!(r == *ans_r);
2622 fn check(a: &BigInt, b: &BigInt, q: &BigInt, r: &BigInt) {
2623 check_sub(a, b, q, r);
2624 check_sub(a, &b.neg(), &q.neg(), r);
2625 check_sub(&a.neg(), b, &q.neg(), &r.neg());
2626 check_sub(&a.neg(), &b.neg(), q, &r.neg());
2628 for elm in mul_triples.iter() {
2629 let (a_vec, b_vec, c_vec) = *elm;
2630 let a = BigInt::from_slice(Plus, a_vec);
2631 let b = BigInt::from_slice(Plus, b_vec);
2632 let c = BigInt::from_slice(Plus, c_vec);
2634 if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
2635 if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
2638 for elm in div_rem_quadruples.iter() {
2639 let (a_vec, b_vec, c_vec, d_vec) = *elm;
2640 let a = BigInt::from_slice(Plus, a_vec);
2641 let b = BigInt::from_slice(Plus, b_vec);
2642 let c = BigInt::from_slice(Plus, c_vec);
2643 let d = BigInt::from_slice(Plus, d_vec);
2646 check(&a, &b, &c, &d);
2652 fn test_checked_add() {
2653 for elm in sum_triples.iter() {
2654 let (aVec, bVec, cVec) = *elm;
2655 let a = BigInt::from_slice(Plus, aVec);
2656 let b = BigInt::from_slice(Plus, bVec);
2657 let c = BigInt::from_slice(Plus, cVec);
2659 assert!(a.checked_add(&b).unwrap() == c);
2660 assert!(b.checked_add(&a).unwrap() == c);
2661 assert!(c.checked_add(&(-a)).unwrap() == b);
2662 assert!(c.checked_add(&(-b)).unwrap() == a);
2663 assert!(a.checked_add(&(-c)).unwrap() == (-b));
2664 assert!(b.checked_add(&(-c)).unwrap() == (-a));
2665 assert!((-a).checked_add(&(-b)).unwrap() == (-c))
2666 assert!(a.checked_add(&(-a)).unwrap() == Zero::zero());
2671 fn test_checked_sub() {
2672 for elm in sum_triples.iter() {
2673 let (aVec, bVec, cVec) = *elm;
2674 let a = BigInt::from_slice(Plus, aVec);
2675 let b = BigInt::from_slice(Plus, bVec);
2676 let c = BigInt::from_slice(Plus, cVec);
2678 assert!(c.checked_sub(&a).unwrap() == b);
2679 assert!(c.checked_sub(&b).unwrap() == a);
2680 assert!((-b).checked_sub(&a).unwrap() == (-c))
2681 assert!((-a).checked_sub(&b).unwrap() == (-c))
2682 assert!(b.checked_sub(&(-a)).unwrap() == c);
2683 assert!(a.checked_sub(&(-b)).unwrap() == c);
2684 assert!((-c).checked_sub(&(-a)).unwrap() == (-b));
2685 assert!(a.checked_sub(&a).unwrap() == Zero::zero());
2690 fn test_checked_mul() {
2691 for elm in mul_triples.iter() {
2692 let (aVec, bVec, cVec) = *elm;
2693 let a = BigInt::from_slice(Plus, aVec);
2694 let b = BigInt::from_slice(Plus, bVec);
2695 let c = BigInt::from_slice(Plus, cVec);
2697 assert!(a.checked_mul(&b).unwrap() == c);
2698 assert!(b.checked_mul(&a).unwrap() == c);
2700 assert!((-a).checked_mul(&b).unwrap() == -c);
2701 assert!((-b).checked_mul(&a).unwrap() == -c);
2704 for elm in div_rem_quadruples.iter() {
2705 let (aVec, bVec, cVec, dVec) = *elm;
2706 let a = BigInt::from_slice(Plus, aVec);
2707 let b = BigInt::from_slice(Plus, bVec);
2708 let c = BigInt::from_slice(Plus, cVec);
2709 let d = BigInt::from_slice(Plus, dVec);
2711 assert!(a == b.checked_mul(&c).unwrap() + d);
2712 assert!(a == c.checked_mul(&b).unwrap() + d);
2716 fn test_checked_div() {
2717 for elm in mul_triples.iter() {
2718 let (aVec, bVec, cVec) = *elm;
2719 let a = BigInt::from_slice(Plus, aVec);
2720 let b = BigInt::from_slice(Plus, bVec);
2721 let c = BigInt::from_slice(Plus, cVec);
2724 assert!(c.checked_div(&a).unwrap() == b);
2725 assert!((-c).checked_div(&(-a)).unwrap() == b);
2726 assert!((-c).checked_div(&a).unwrap() == -b);
2729 assert!(c.checked_div(&b).unwrap() == a);
2730 assert!((-c).checked_div(&(-b)).unwrap() == a);
2731 assert!((-c).checked_div(&b).unwrap() == -a);
2734 assert!(c.checked_div(&Zero::zero()).is_none());
2735 assert!((-c).checked_div(&Zero::zero()).is_none());
2741 fn check(a: int, b: int, c: int) {
2742 let big_a: BigInt = FromPrimitive::from_int(a).unwrap();
2743 let big_b: BigInt = FromPrimitive::from_int(b).unwrap();
2744 let big_c: BigInt = FromPrimitive::from_int(c).unwrap();
2746 assert_eq!(big_a.gcd(&big_b), big_c);
2761 fn check(a: int, b: int, c: int) {
2762 let big_a: BigInt = FromPrimitive::from_int(a).unwrap();
2763 let big_b: BigInt = FromPrimitive::from_int(b).unwrap();
2764 let big_c: BigInt = FromPrimitive::from_int(c).unwrap();
2766 assert_eq!(big_a.lcm(&big_b), big_c);
2781 let zero: BigInt = Zero::zero();
2782 let one: BigInt = One::one();
2783 assert_eq!((-one).abs_sub(&one), zero);
2784 let one: BigInt = One::one();
2785 let zero: BigInt = Zero::zero();
2786 assert_eq!(one.abs_sub(&one), zero);
2787 let one: BigInt = One::one();
2788 let zero: BigInt = Zero::zero();
2789 assert_eq!(one.abs_sub(&zero), one);
2790 let one: BigInt = One::one();
2791 let two: BigInt = FromPrimitive::from_int(2).unwrap();
2792 assert_eq!(one.abs_sub(&-one), two);
2796 fn test_to_str_radix() {
2797 fn check(n: int, ans: &str) {
2798 let n: BigInt = FromPrimitive::from_int(n).unwrap();
2799 assert!(ans == n.to_str_radix(10).as_slice());
2810 fn test_from_str_radix() {
2811 fn check(s: &str, ans: Option<int>) {
2812 let ans = ans.map(|n| {
2813 let x: BigInt = FromPrimitive::from_int(n).unwrap();
2816 assert_eq!(FromStrRadix::from_str_radix(s, 10), ans);
2818 check("10", Some(10));
2819 check("1", Some(1));
2820 check("0", Some(0));
2821 check("-1", Some(-1));
2822 check("-10", Some(-10));
2826 // issue 10522, this hit an edge case that caused it to
2827 // attempt to allocate a vector of size (-1u) == huge.
2829 from_str(format!("1{}", "0".repeat(36)).as_slice()).unwrap();
2830 let _y = x.to_string();
2835 assert!(-BigInt::new(Plus, vec!(1, 1, 1)) ==
2836 BigInt::new(Minus, vec!(1, 1, 1)));
2837 assert!(-BigInt::new(Minus, vec!(1, 1, 1)) ==
2838 BigInt::new(Plus, vec!(1, 1, 1)));
2839 let zero: BigInt = Zero::zero();
2840 assert_eq!(-zero, zero);
2845 let mut rng = task_rng();
2846 let _n: BigInt = rng.gen_bigint(137);
2847 assert!(rng.gen_bigint(0).is_zero());
2851 fn test_rand_range() {
2852 let mut rng = task_rng();
2854 for _ in range(0u, 10) {
2855 assert_eq!(rng.gen_bigint_range(&FromPrimitive::from_uint(236).unwrap(),
2856 &FromPrimitive::from_uint(237).unwrap()),
2857 FromPrimitive::from_uint(236).unwrap());
2860 fn check(l: BigInt, u: BigInt) {
2861 let mut rng = task_rng();
2862 for _ in range(0u, 1000) {
2863 let n: BigInt = rng.gen_bigint_range(&l, &u);
2868 let l: BigInt = FromPrimitive::from_uint(403469000 + 2352).unwrap();
2869 let u: BigInt = FromPrimitive::from_uint(403469000 + 3513).unwrap();
2870 check( l.clone(), u.clone());
2871 check(-l.clone(), u.clone());
2872 check(-u.clone(), -l.clone());
2877 fn test_zero_rand_range() {
2878 task_rng().gen_bigint_range(&FromPrimitive::from_int(54).unwrap(),
2879 &FromPrimitive::from_int(54).unwrap());
2884 fn test_negative_rand_range() {
2885 let mut rng = task_rng();
2886 let l = FromPrimitive::from_uint(2352).unwrap();
2887 let u = FromPrimitive::from_uint(3513).unwrap();
2888 // Switching u and l should fail:
2889 let _n: BigInt = rng.gen_bigint_range(&u, &l);
2896 use self::test::Bencher;
2899 use std::mem::replace;
2900 use std::num::{FromPrimitive, Zero, One};
2902 fn factorial(n: uint) -> BigUint {
2903 let mut f: BigUint = One::one();
2904 for i in iter::range_inclusive(1, n) {
2905 f = f * FromPrimitive::from_uint(i).unwrap();
2910 fn fib(n: uint) -> BigUint {
2911 let mut f0: BigUint = Zero::zero();
2912 let mut f1: BigUint = One::one();
2913 for _ in range(0, n) {
2915 f0 = replace(&mut f1, f2);
2921 fn factorial_100(b: &mut Bencher) {
2928 fn fib_100(b: &mut Bencher) {
2935 fn to_string(b: &mut Bencher) {
2936 let fac = factorial(100);
2947 fn shr(b: &mut Bencher) {
2948 let n = { let one : BigUint = One::one(); one << 1000 };
2950 let mut m = n.clone();
2951 for _ in range(0u, 10) {