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);
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];
83 use super::DoubleBigDigit;
85 // `DoubleBigDigit` size dependent
86 pub static bits: uint = 32;
88 pub static base: DoubleBigDigit = 1 << bits;
89 static lo_mask: DoubleBigDigit = (-1 as DoubleBigDigit) >> bits;
92 fn get_hi(n: DoubleBigDigit) -> BigDigit { (n >> bits) as BigDigit }
94 fn get_lo(n: DoubleBigDigit) -> BigDigit { (n & lo_mask) as BigDigit }
96 /// Split one `DoubleBigDigit` into two `BigDigit`s.
98 pub fn from_doublebigdigit(n: DoubleBigDigit) -> (BigDigit, BigDigit) {
99 (get_hi(n), get_lo(n))
102 /// Join two `BigDigit`s into one `DoubleBigDigit`
104 pub fn to_doublebigdigit(hi: BigDigit, lo: BigDigit) -> DoubleBigDigit {
105 (lo as DoubleBigDigit) | ((hi as DoubleBigDigit) << bits)
109 /// A big unsigned integer type.
111 /// A `BigUint`-typed value `BigUint { data: vec!(a, b, c) }` represents a number
112 /// `(a + b * BigDigit::base + c * BigDigit::base^2)`.
118 impl PartialEq for BigUint {
120 fn eq(&self, other: &BigUint) -> bool {
121 match self.cmp(other) { Equal => true, _ => false }
124 impl Eq for BigUint {}
126 impl PartialOrd for BigUint {
128 fn partial_cmp(&self, other: &BigUint) -> Option<Ordering> {
129 Some(self.cmp(other))
133 impl Ord for BigUint {
135 fn cmp(&self, other: &BigUint) -> Ordering {
136 let (s_len, o_len) = (self.data.len(), other.data.len());
137 if s_len < o_len { return Less; }
138 if s_len > o_len { return Greater; }
140 for (&self_i, &other_i) in self.data.iter().rev().zip(other.data.iter().rev()) {
141 if self_i < other_i { return Less; }
142 if self_i > other_i { return Greater; }
148 impl Default for BigUint {
150 fn default() -> BigUint { Zero::zero() }
153 impl fmt::Show for BigUint {
154 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
155 write!(f, "{}", self.to_str_radix(10))
159 impl FromStr for BigUint {
161 fn from_str(s: &str) -> Option<BigUint> {
162 FromStrRadix::from_str_radix(s, 10)
166 impl Num for BigUint {}
168 impl BitAnd<BigUint, BigUint> for BigUint {
169 fn bitand(&self, other: &BigUint) -> BigUint {
170 BigUint::new(self.data.iter().zip(other.data.iter()).map(|(ai, bi)| *ai & *bi).collect())
174 impl BitOr<BigUint, BigUint> for BigUint {
175 fn bitor(&self, other: &BigUint) -> BigUint {
176 let zeros = ZERO_VEC.iter().cycle();
177 let (a, b) = if self.data.len() > other.data.len() { (self, other) } else { (other, self) };
178 let ored = a.data.iter().zip(b.data.iter().chain(zeros)).map(
181 return BigUint::new(ored);
185 impl BitXor<BigUint, BigUint> for BigUint {
186 fn bitxor(&self, other: &BigUint) -> BigUint {
187 let zeros = ZERO_VEC.iter().cycle();
188 let (a, b) = if self.data.len() > other.data.len() { (self, other) } else { (other, self) };
189 let xored = a.data.iter().zip(b.data.iter().chain(zeros)).map(
192 return BigUint::new(xored);
196 impl Shl<uint, BigUint> for BigUint {
198 fn shl(&self, rhs: &uint) -> BigUint {
199 let n_unit = *rhs / BigDigit::bits;
200 let n_bits = *rhs % BigDigit::bits;
201 return self.shl_unit(n_unit).shl_bits(n_bits);
205 impl Shr<uint, BigUint> for BigUint {
207 fn shr(&self, rhs: &uint) -> BigUint {
208 let n_unit = *rhs / BigDigit::bits;
209 let n_bits = *rhs % BigDigit::bits;
210 return self.shr_unit(n_unit).shr_bits(n_bits);
214 impl Zero for BigUint {
216 fn zero() -> BigUint { BigUint::new(Vec::new()) }
219 fn is_zero(&self) -> bool { self.data.is_empty() }
222 impl One for BigUint {
224 fn one() -> BigUint { BigUint::new(vec!(1)) }
227 impl Unsigned for BigUint {}
229 impl Add<BigUint, BigUint> for BigUint {
230 fn add(&self, other: &BigUint) -> BigUint {
231 let zeros = ZERO_VEC.iter().cycle();
232 let (a, b) = if self.data.len() > other.data.len() { (self, other) } else { (other, self) };
235 let mut sum: Vec<BigDigit> = a.data.iter().zip(b.data.iter().chain(zeros)).map(|(ai, bi)| {
236 let (hi, lo) = BigDigit::from_doublebigdigit(
237 (*ai as DoubleBigDigit) + (*bi as DoubleBigDigit) + (carry as DoubleBigDigit));
241 if carry != 0 { sum.push(carry); }
242 return BigUint::new(sum);
246 impl Sub<BigUint, BigUint> for BigUint {
247 fn sub(&self, other: &BigUint) -> BigUint {
248 let new_len = cmp::max(self.data.len(), other.data.len());
249 let zeros = ZERO_VEC.iter().cycle();
250 let (a, b) = (self.data.iter().chain(zeros.clone()), other.data.iter().chain(zeros));
253 let diff: Vec<BigDigit> = a.take(new_len).zip(b).map(|(ai, bi)| {
254 let (hi, lo) = BigDigit::from_doublebigdigit(
256 + (*ai as DoubleBigDigit)
257 - (*bi as DoubleBigDigit)
258 - (borrow as DoubleBigDigit)
261 hi * (base) + lo == 1*(base) + ai - bi - borrow
262 => ai - bi - borrow < 0 <=> hi == 0
264 borrow = if hi == 0 { 1 } else { 0 };
269 "Cannot subtract other from self because other is larger than self.");
270 return BigUint::new(diff);
274 impl Mul<BigUint, BigUint> for BigUint {
275 fn mul(&self, other: &BigUint) -> BigUint {
276 if self.is_zero() || other.is_zero() { return Zero::zero(); }
278 let (s_len, o_len) = (self.data.len(), other.data.len());
279 if s_len == 1 { return mul_digit(other, self.data.as_slice()[0]); }
280 if o_len == 1 { return mul_digit(self, other.data.as_slice()[0]); }
282 // Using Karatsuba multiplication
283 // (a1 * base + a0) * (b1 * base + b0)
284 // = a1*b1 * base^2 +
285 // (a1*b1 + a0*b0 - (a1-b0)*(b1-a0)) * base +
287 let half_len = cmp::max(s_len, o_len) / 2;
288 let (s_hi, s_lo) = cut_at(self, half_len);
289 let (o_hi, o_lo) = cut_at(other, half_len);
291 let ll = s_lo * o_lo;
292 let hh = s_hi * o_hi;
294 let (s1, n1) = sub_sign(s_hi, s_lo);
295 let (s2, n2) = sub_sign(o_hi, o_lo);
297 (Equal, _) | (_, Equal) => hh + ll,
298 (Less, Greater) | (Greater, Less) => hh + ll + (n1 * n2),
299 (Less, Less) | (Greater, Greater) => hh + ll - (n1 * n2)
303 return ll + mm.shl_unit(half_len) + hh.shl_unit(half_len * 2);
306 fn mul_digit(a: &BigUint, n: BigDigit) -> BigUint {
307 if n == 0 { return Zero::zero(); }
308 if n == 1 { return (*a).clone(); }
311 let mut prod: Vec<BigDigit> = a.data.iter().map(|ai| {
312 let (hi, lo) = BigDigit::from_doublebigdigit(
313 (*ai as DoubleBigDigit) * (n as DoubleBigDigit) + (carry as DoubleBigDigit)
318 if carry != 0 { prod.push(carry); }
319 return BigUint::new(prod);
323 fn cut_at(a: &BigUint, n: uint) -> (BigUint, BigUint) {
324 let mid = cmp::min(a.data.len(), n);
325 return (BigUint::from_slice(a.data.slice(mid, a.data.len())),
326 BigUint::from_slice(a.data.slice(0, mid)));
330 fn sub_sign(a: BigUint, b: BigUint) -> (Ordering, BigUint) {
332 Less => (Less, b - a),
333 Greater => (Greater, a - b),
334 _ => (Equal, Zero::zero())
340 impl Div<BigUint, BigUint> for BigUint {
342 fn div(&self, other: &BigUint) -> BigUint {
343 let (q, _) = self.div_rem(other);
348 impl Rem<BigUint, BigUint> for BigUint {
350 fn rem(&self, other: &BigUint) -> BigUint {
351 let (_, r) = self.div_rem(other);
356 impl Neg<BigUint> for BigUint {
358 fn neg(&self) -> BigUint { fail!() }
361 impl CheckedAdd for BigUint {
363 fn checked_add(&self, v: &BigUint) -> Option<BigUint> {
364 return Some(self.add(v));
368 impl CheckedSub for BigUint {
370 fn checked_sub(&self, v: &BigUint) -> Option<BigUint> {
374 return Some(self.sub(v));
378 impl CheckedMul for BigUint {
380 fn checked_mul(&self, v: &BigUint) -> Option<BigUint> {
381 return Some(self.mul(v));
385 impl CheckedDiv for BigUint {
387 fn checked_div(&self, v: &BigUint) -> Option<BigUint> {
391 return Some(self.div(v));
395 impl Integer for BigUint {
397 fn div_rem(&self, other: &BigUint) -> (BigUint, BigUint) {
398 self.div_mod_floor(other)
402 fn div_floor(&self, other: &BigUint) -> BigUint {
403 let (d, _) = self.div_mod_floor(other);
408 fn mod_floor(&self, other: &BigUint) -> BigUint {
409 let (_, m) = self.div_mod_floor(other);
413 fn div_mod_floor(&self, other: &BigUint) -> (BigUint, BigUint) {
414 if other.is_zero() { fail!() }
415 if self.is_zero() { return (Zero::zero(), Zero::zero()); }
416 if *other == One::one() { return ((*self).clone(), Zero::zero()); }
418 match self.cmp(other) {
419 Less => return (Zero::zero(), (*self).clone()),
420 Equal => return (One::one(), Zero::zero()),
421 Greater => {} // Do nothing
425 let mut n = *other.data.last().unwrap();
426 while n < (1 << BigDigit::bits - 2) {
430 assert!(shift < BigDigit::bits);
431 let (d, m) = div_mod_floor_inner(self << shift, other << shift);
432 return (d, m >> shift);
435 fn div_mod_floor_inner(a: BigUint, b: BigUint) -> (BigUint, BigUint) {
437 let mut d: BigUint = Zero::zero();
440 let (d0, d_unit, b_unit) = div_estimate(&m, &b, n);
442 let mut prod = b * d0;
444 // FIXME(#5992): assignment operator overloads
447 // FIXME(#5992): assignment operator overloads
456 // FIXME(#5992): assignment operator overloads
459 // FIXME(#5992): assignment operator overloads
467 fn div_estimate(a: &BigUint, b: &BigUint, n: uint)
468 -> (BigUint, BigUint, BigUint) {
469 if a.data.len() < n {
470 return (Zero::zero(), Zero::zero(), (*a).clone());
473 let an = a.data.tailn(a.data.len() - n);
474 let bn = *b.data.last().unwrap();
475 let mut d = Vec::with_capacity(an.len());
477 for elt in an.iter().rev() {
478 let ai = BigDigit::to_doublebigdigit(carry, *elt);
479 let di = ai / (bn as DoubleBigDigit);
480 assert!(di < BigDigit::base);
481 carry = (ai % (bn as DoubleBigDigit)) as BigDigit;
482 d.push(di as BigDigit)
486 let shift = (a.data.len() - an.len()) - (b.data.len() - 1);
488 return (BigUint::new(d), One::one(), (*b).clone());
490 let one: BigUint = One::one();
491 return (BigUint::new(d).shl_unit(shift),
497 /// Calculates the Greatest Common Divisor (GCD) of the number and `other`.
499 /// The result is always positive.
501 fn gcd(&self, other: &BigUint) -> BigUint {
502 // Use Euclid's algorithm
503 let mut m = (*self).clone();
504 let mut n = (*other).clone();
513 /// Calculates the Lowest Common Multiple (LCM) of the number and `other`.
515 fn lcm(&self, other: &BigUint) -> BigUint { ((*self * *other) / self.gcd(other)) }
517 /// Returns `true` if the number can be divided by `other` without leaving a remainder.
519 fn divides(&self, other: &BigUint) -> bool { (*self % *other).is_zero() }
521 /// Returns `true` if the number is divisible by `2`.
523 fn is_even(&self) -> bool {
524 // Considering only the last digit.
525 match self.data.as_slice().head() {
526 Some(x) => x.is_even(),
531 /// Returns `true` if the number is not divisible by `2`.
533 fn is_odd(&self) -> bool { !self.is_even() }
536 impl ToPrimitive for BigUint {
538 fn to_i64(&self) -> Option<i64> {
539 self.to_u64().and_then(|n| {
540 // If top bit of u64 is set, it's too large to convert to i64.
549 // `DoubleBigDigit` size dependent
551 fn to_u64(&self) -> Option<u64> {
552 match self.data.len() {
554 1 => Some(self.data.as_slice()[0] as u64),
555 2 => Some(BigDigit::to_doublebigdigit(self.data.as_slice()[1], self.data.as_slice()[0])
562 impl FromPrimitive for BigUint {
564 fn from_i64(n: i64) -> Option<BigUint> {
566 FromPrimitive::from_u64(n as u64)
574 // `DoubleBigDigit` size dependent
576 fn from_u64(n: u64) -> Option<BigUint> {
577 let n = match BigDigit::from_doublebigdigit(n) {
578 (0, 0) => Zero::zero(),
579 (0, n0) => BigUint::new(vec!(n0)),
580 (n1, n0) => BigUint::new(vec!(n0, n1))
586 /// A generic trait for converting a value to a `BigUint`.
587 pub trait ToBigUint {
588 /// Converts the value of `self` to a `BigUint`.
589 fn to_biguint(&self) -> Option<BigUint>;
592 impl ToBigUint for BigInt {
594 fn to_biguint(&self) -> Option<BigUint> {
595 if self.sign == Plus {
596 Some(self.data.clone())
597 } else if self.sign == Zero {
605 impl ToBigUint for BigUint {
607 fn to_biguint(&self) -> Option<BigUint> {
612 macro_rules! impl_to_biguint(
613 ($T:ty, $from_ty:path) => {
614 impl ToBigUint for $T {
616 fn to_biguint(&self) -> Option<BigUint> {
623 impl_to_biguint!(int, FromPrimitive::from_int)
624 impl_to_biguint!(i8, FromPrimitive::from_i8)
625 impl_to_biguint!(i16, FromPrimitive::from_i16)
626 impl_to_biguint!(i32, FromPrimitive::from_i32)
627 impl_to_biguint!(i64, FromPrimitive::from_i64)
628 impl_to_biguint!(uint, FromPrimitive::from_uint)
629 impl_to_biguint!(u8, FromPrimitive::from_u8)
630 impl_to_biguint!(u16, FromPrimitive::from_u16)
631 impl_to_biguint!(u32, FromPrimitive::from_u32)
632 impl_to_biguint!(u64, FromPrimitive::from_u64)
634 impl ToStrRadix for BigUint {
635 fn to_str_radix(&self, radix: uint) -> String {
636 assert!(1 < radix && radix <= 16, "The radix must be within (1, 16]");
637 let (base, max_len) = get_radix_base(radix);
638 if base == BigDigit::base {
639 return fill_concat(self.data.as_slice(), radix, max_len)
641 return fill_concat(convert_base(self, base).as_slice(), radix, max_len);
643 fn convert_base(n: &BigUint, base: DoubleBigDigit) -> Vec<BigDigit> {
644 let divider = base.to_biguint().unwrap();
645 let mut result = Vec::new();
646 let mut m = n.clone();
648 let (d, m0) = m.div_mod_floor(÷r);
649 result.push(m0.to_uint().unwrap() as BigDigit);
653 result.push(m.to_uint().unwrap() as BigDigit);
658 fn fill_concat(v: &[BigDigit], radix: uint, l: uint) -> String {
660 return "0".to_string()
662 let mut s = String::with_capacity(v.len() * l);
663 for n in v.iter().rev() {
664 let ss = (*n as uint).to_str_radix(radix);
665 s.push_str("0".repeat(l - ss.len()).as_slice());
666 s.push_str(ss.as_slice());
668 s.as_slice().trim_left_chars('0').to_string()
673 impl FromStrRadix for BigUint {
674 /// Creates and initializes a `BigUint`.
676 fn from_str_radix(s: &str, radix: uint) -> Option<BigUint> {
677 BigUint::parse_bytes(s.as_bytes(), radix)
682 /// Creates and initializes a `BigUint`.
684 /// The digits are be in base 2^32.
686 pub fn new(mut digits: Vec<BigDigit>) -> BigUint {
687 // omit trailing zeros
688 let new_len = digits.iter().rposition(|n| *n != 0).map_or(0, |p| p + 1);
689 digits.truncate(new_len);
690 BigUint { data: digits }
693 /// Creates and initializes a `BigUint`.
695 /// The digits are be in base 2^32.
697 pub fn from_slice(slice: &[BigDigit]) -> BigUint {
698 BigUint::new(Vec::from_slice(slice))
701 /// Creates and initializes a `BigUint`.
702 pub fn parse_bytes(buf: &[u8], radix: uint) -> Option<BigUint> {
703 let (base, unit_len) = get_radix_base(radix);
704 let base_num = match base.to_biguint() {
705 Some(base_num) => base_num,
706 None => { return None; }
709 let mut end = buf.len();
710 let mut n: BigUint = Zero::zero();
711 let mut power: BigUint = One::one();
713 let start = cmp::max(end, unit_len) - unit_len;
714 match uint::parse_bytes(buf.slice(start, end), radix) {
716 let d: Option<BigUint> = FromPrimitive::from_uint(d);
719 // FIXME(#5992): assignment operator overloads
723 None => { return None; }
726 None => { return None; }
732 // FIXME(#5992): assignment operator overloads
733 // power *= base_num;
734 power = power * base_num;
739 fn shl_unit(&self, n_unit: uint) -> BigUint {
740 if n_unit == 0 || self.is_zero() { return (*self).clone(); }
742 BigUint::new(Vec::from_elem(n_unit, ZERO_BIG_DIGIT).append(self.data.as_slice()))
746 fn shl_bits(&self, n_bits: uint) -> BigUint {
747 if n_bits == 0 || self.is_zero() { return (*self).clone(); }
750 let mut shifted: Vec<BigDigit> = self.data.iter().map(|elem| {
751 let (hi, lo) = BigDigit::from_doublebigdigit(
752 (*elem as DoubleBigDigit) << n_bits | (carry as DoubleBigDigit)
757 if carry != 0 { shifted.push(carry); }
758 return BigUint::new(shifted);
762 fn shr_unit(&self, n_unit: uint) -> BigUint {
763 if n_unit == 0 { return (*self).clone(); }
764 if self.data.len() < n_unit { return Zero::zero(); }
765 return BigUint::from_slice(
766 self.data.slice(n_unit, self.data.len())
771 fn shr_bits(&self, n_bits: uint) -> BigUint {
772 if n_bits == 0 || self.data.is_empty() { return (*self).clone(); }
775 let mut shifted_rev = Vec::with_capacity(self.data.len());
776 for elem in self.data.iter().rev() {
777 shifted_rev.push((*elem >> n_bits) | borrow);
778 borrow = *elem << (BigDigit::bits - n_bits);
780 let shifted = { shifted_rev.reverse(); shifted_rev };
781 return BigUint::new(shifted);
784 /// Determines the fewest bits necessary to express the `BigUint`.
785 pub fn bits(&self) -> uint {
786 if self.is_zero() { return 0; }
787 let zeros = self.data.last().unwrap().leading_zeros();
788 return self.data.len()*BigDigit::bits - (zeros as uint);
792 // `DoubleBigDigit` size dependent
794 fn get_radix_base(radix: uint) -> (DoubleBigDigit, uint) {
796 2 => (4294967296, 32),
797 3 => (3486784401, 20),
798 4 => (4294967296, 16),
799 5 => (1220703125, 13),
800 6 => (2176782336, 12),
801 7 => (1977326743, 11),
802 8 => (1073741824, 10),
803 9 => (3486784401, 10),
804 10 => (1000000000, 9),
805 11 => (2357947691, 9),
806 12 => (429981696, 8),
807 13 => (815730721, 8),
808 14 => (1475789056, 8),
809 15 => (2562890625, 8),
810 16 => (4294967296, 8),
811 _ => fail!("The radix must be within (1, 16]")
815 /// A Sign is a `BigInt`'s composing element.
816 #[deriving(PartialEq, PartialOrd, Eq, Ord, Clone, Show)]
817 pub enum Sign { Minus, Zero, Plus }
819 impl Neg<Sign> for Sign {
820 /// Negate Sign value.
822 fn neg(&self) -> Sign {
831 /// A big signed integer type.
838 impl PartialEq for BigInt {
840 fn eq(&self, other: &BigInt) -> bool {
841 self.cmp(other) == Equal
845 impl Eq for BigInt {}
847 impl PartialOrd for BigInt {
849 fn partial_cmp(&self, other: &BigInt) -> Option<Ordering> {
850 Some(self.cmp(other))
854 impl Ord for BigInt {
856 fn cmp(&self, other: &BigInt) -> Ordering {
857 let scmp = self.sign.cmp(&other.sign);
858 if scmp != Equal { return scmp; }
862 Plus => self.data.cmp(&other.data),
863 Minus => other.data.cmp(&self.data),
868 impl Default for BigInt {
870 fn default() -> BigInt { Zero::zero() }
873 impl fmt::Show for BigInt {
874 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
875 write!(f, "{}", self.to_str_radix(10))
879 impl FromStr for BigInt {
881 fn from_str(s: &str) -> Option<BigInt> {
882 FromStrRadix::from_str_radix(s, 10)
886 impl Num for BigInt {}
888 impl Shl<uint, BigInt> for BigInt {
890 fn shl(&self, rhs: &uint) -> BigInt {
891 BigInt::from_biguint(self.sign, self.data << *rhs)
895 impl Shr<uint, BigInt> for BigInt {
897 fn shr(&self, rhs: &uint) -> BigInt {
898 BigInt::from_biguint(self.sign, self.data >> *rhs)
902 impl Zero for BigInt {
904 fn zero() -> BigInt {
905 BigInt::from_biguint(Zero, Zero::zero())
909 fn is_zero(&self) -> bool { self.sign == Zero }
912 impl One for BigInt {
915 BigInt::from_biguint(Plus, One::one())
919 impl Signed for BigInt {
921 fn abs(&self) -> BigInt {
923 Plus | Zero => self.clone(),
924 Minus => BigInt::from_biguint(Plus, self.data.clone())
929 fn abs_sub(&self, other: &BigInt) -> BigInt {
930 if *self <= *other { Zero::zero() } else { *self - *other }
934 fn signum(&self) -> BigInt {
936 Plus => BigInt::from_biguint(Plus, One::one()),
937 Minus => BigInt::from_biguint(Minus, One::one()),
938 Zero => Zero::zero(),
943 fn is_positive(&self) -> bool { self.sign == Plus }
946 fn is_negative(&self) -> bool { self.sign == Minus }
949 impl Add<BigInt, BigInt> for BigInt {
951 fn add(&self, other: &BigInt) -> BigInt {
952 match (self.sign, other.sign) {
953 (Zero, _) => other.clone(),
954 (_, Zero) => self.clone(),
955 (Plus, Plus) => BigInt::from_biguint(Plus, self.data + other.data),
956 (Plus, Minus) => self - (-*other),
957 (Minus, Plus) => other - (-*self),
958 (Minus, Minus) => -((-self) + (-*other))
963 impl Sub<BigInt, BigInt> for BigInt {
965 fn sub(&self, other: &BigInt) -> BigInt {
966 match (self.sign, other.sign) {
968 (_, Zero) => self.clone(),
969 (Plus, Plus) => match self.data.cmp(&other.data) {
970 Less => BigInt::from_biguint(Minus, other.data - self.data),
971 Greater => BigInt::from_biguint(Plus, self.data - other.data),
972 Equal => Zero::zero()
974 (Plus, Minus) => self + (-*other),
975 (Minus, Plus) => -((-self) + *other),
976 (Minus, Minus) => (-other) - (-*self)
981 impl Mul<BigInt, BigInt> for BigInt {
983 fn mul(&self, other: &BigInt) -> BigInt {
984 match (self.sign, other.sign) {
985 (Zero, _) | (_, Zero) => Zero::zero(),
986 (Plus, Plus) | (Minus, Minus) => {
987 BigInt::from_biguint(Plus, self.data * other.data)
989 (Plus, Minus) | (Minus, Plus) => {
990 BigInt::from_biguint(Minus, self.data * other.data)
996 impl Div<BigInt, BigInt> for BigInt {
998 fn div(&self, other: &BigInt) -> BigInt {
999 let (q, _) = self.div_rem(other);
1004 impl Rem<BigInt, BigInt> for BigInt {
1006 fn rem(&self, other: &BigInt) -> BigInt {
1007 let (_, r) = self.div_rem(other);
1012 impl Neg<BigInt> for BigInt {
1014 fn neg(&self) -> BigInt {
1015 BigInt::from_biguint(self.sign.neg(), self.data.clone())
1019 impl CheckedAdd for BigInt {
1021 fn checked_add(&self, v: &BigInt) -> Option<BigInt> {
1022 return Some(self.add(v));
1026 impl CheckedSub for BigInt {
1028 fn checked_sub(&self, v: &BigInt) -> Option<BigInt> {
1029 return Some(self.sub(v));
1033 impl CheckedMul for BigInt {
1035 fn checked_mul(&self, v: &BigInt) -> Option<BigInt> {
1036 return Some(self.mul(v));
1040 impl CheckedDiv for BigInt {
1042 fn checked_div(&self, v: &BigInt) -> Option<BigInt> {
1046 return Some(self.div(v));
1051 impl Integer for BigInt {
1053 fn div_rem(&self, other: &BigInt) -> (BigInt, BigInt) {
1054 // r.sign == self.sign
1055 let (d_ui, r_ui) = self.data.div_mod_floor(&other.data);
1056 let d = BigInt::from_biguint(Plus, d_ui);
1057 let r = BigInt::from_biguint(Plus, r_ui);
1058 match (self.sign, other.sign) {
1059 (_, Zero) => fail!(),
1060 (Plus, Plus) | (Zero, Plus) => ( d, r),
1061 (Plus, Minus) | (Zero, Minus) => (-d, r),
1062 (Minus, Plus) => (-d, -r),
1063 (Minus, Minus) => ( d, -r)
1068 fn div_floor(&self, other: &BigInt) -> BigInt {
1069 let (d, _) = self.div_mod_floor(other);
1074 fn mod_floor(&self, other: &BigInt) -> BigInt {
1075 let (_, m) = self.div_mod_floor(other);
1079 fn div_mod_floor(&self, other: &BigInt) -> (BigInt, BigInt) {
1080 // m.sign == other.sign
1081 let (d_ui, m_ui) = self.data.div_rem(&other.data);
1082 let d = BigInt::from_biguint(Plus, d_ui);
1083 let m = BigInt::from_biguint(Plus, m_ui);
1084 match (self.sign, other.sign) {
1085 (_, Zero) => fail!(),
1086 (Plus, Plus) | (Zero, Plus) => (d, m),
1087 (Plus, Minus) | (Zero, Minus) => if m.is_zero() {
1090 (-d - One::one(), m + *other)
1092 (Minus, Plus) => if m.is_zero() {
1095 (-d - One::one(), other - m)
1097 (Minus, Minus) => (d, -m)
1101 /// Calculates the Greatest Common Divisor (GCD) of the number and `other`.
1103 /// The result is always positive.
1105 fn gcd(&self, other: &BigInt) -> BigInt {
1106 BigInt::from_biguint(Plus, self.data.gcd(&other.data))
1109 /// Calculates the Lowest Common Multiple (LCM) of the number and `other`.
1111 fn lcm(&self, other: &BigInt) -> BigInt {
1112 BigInt::from_biguint(Plus, self.data.lcm(&other.data))
1115 /// Returns `true` if the number can be divided by `other` without leaving a remainder.
1117 fn divides(&self, other: &BigInt) -> bool { self.data.divides(&other.data) }
1119 /// Returns `true` if the number is divisible by `2`.
1121 fn is_even(&self) -> bool { self.data.is_even() }
1123 /// Returns `true` if the number is not divisible by `2`.
1125 fn is_odd(&self) -> bool { self.data.is_odd() }
1128 impl ToPrimitive for BigInt {
1130 fn to_i64(&self) -> Option<i64> {
1132 Plus => self.data.to_i64(),
1135 self.data.to_u64().and_then(|n| {
1136 let m: u64 = 1 << 63;
1150 fn to_u64(&self) -> Option<u64> {
1152 Plus => self.data.to_u64(),
1159 impl FromPrimitive for BigInt {
1161 fn from_i64(n: i64) -> Option<BigInt> {
1163 FromPrimitive::from_u64(n as u64).and_then(|n| {
1164 Some(BigInt::from_biguint(Plus, n))
1167 FromPrimitive::from_u64(u64::MAX - (n as u64) + 1).and_then(
1169 Some(BigInt::from_biguint(Minus, n))
1177 fn from_u64(n: u64) -> Option<BigInt> {
1181 FromPrimitive::from_u64(n).and_then(|n| {
1182 Some(BigInt::from_biguint(Plus, n))
1188 /// A generic trait for converting a value to a `BigInt`.
1189 pub trait ToBigInt {
1190 /// Converts the value of `self` to a `BigInt`.
1191 fn to_bigint(&self) -> Option<BigInt>;
1194 impl ToBigInt for BigInt {
1196 fn to_bigint(&self) -> Option<BigInt> {
1201 impl ToBigInt for BigUint {
1203 fn to_bigint(&self) -> Option<BigInt> {
1207 Some(BigInt { sign: Plus, data: self.clone() })
1212 macro_rules! impl_to_bigint(
1213 ($T:ty, $from_ty:path) => {
1214 impl ToBigInt for $T {
1216 fn to_bigint(&self) -> Option<BigInt> {
1223 impl_to_bigint!(int, FromPrimitive::from_int)
1224 impl_to_bigint!(i8, FromPrimitive::from_i8)
1225 impl_to_bigint!(i16, FromPrimitive::from_i16)
1226 impl_to_bigint!(i32, FromPrimitive::from_i32)
1227 impl_to_bigint!(i64, FromPrimitive::from_i64)
1228 impl_to_bigint!(uint, FromPrimitive::from_uint)
1229 impl_to_bigint!(u8, FromPrimitive::from_u8)
1230 impl_to_bigint!(u16, FromPrimitive::from_u16)
1231 impl_to_bigint!(u32, FromPrimitive::from_u32)
1232 impl_to_bigint!(u64, FromPrimitive::from_u64)
1234 impl ToStrRadix for BigInt {
1236 fn to_str_radix(&self, radix: uint) -> String {
1238 Plus => self.data.to_str_radix(radix),
1239 Zero => "0".to_string(),
1240 Minus => format!("-{}", self.data.to_str_radix(radix)),
1245 impl FromStrRadix for BigInt {
1246 /// Creates and initializes a BigInt.
1248 fn from_str_radix(s: &str, radix: uint) -> Option<BigInt> {
1249 BigInt::parse_bytes(s.as_bytes(), radix)
1253 pub trait RandBigInt {
1254 /// Generate a random `BigUint` of the given bit size.
1255 fn gen_biguint(&mut self, bit_size: uint) -> BigUint;
1257 /// Generate a random BigInt of the given bit size.
1258 fn gen_bigint(&mut self, bit_size: uint) -> BigInt;
1260 /// Generate a random `BigUint` less than the given bound. Fails
1261 /// when the bound is zero.
1262 fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint;
1264 /// Generate a random `BigUint` within the given range. The lower
1265 /// bound is inclusive; the upper bound is exclusive. Fails when
1266 /// the upper bound is not greater than the lower bound.
1267 fn gen_biguint_range(&mut self, lbound: &BigUint, ubound: &BigUint) -> BigUint;
1269 /// Generate a random `BigInt` within the given range. The lower
1270 /// bound is inclusive; the upper bound is exclusive. Fails when
1271 /// the upper bound is not greater than the lower bound.
1272 fn gen_bigint_range(&mut self, lbound: &BigInt, ubound: &BigInt) -> BigInt;
1275 impl<R: Rng> RandBigInt for R {
1276 fn gen_biguint(&mut self, bit_size: uint) -> BigUint {
1277 let (digits, rem) = bit_size.div_rem(&BigDigit::bits);
1278 let mut data = Vec::with_capacity(digits+1);
1279 for _ in range(0, digits) {
1280 data.push(self.gen());
1283 let final_digit: BigDigit = self.gen();
1284 data.push(final_digit >> (BigDigit::bits - rem));
1289 fn gen_bigint(&mut self, bit_size: uint) -> BigInt {
1290 // Generate a random BigUint...
1291 let biguint = self.gen_biguint(bit_size);
1292 // ...and then randomly assign it a Sign...
1293 let sign = if biguint.is_zero() {
1294 // ...except that if the BigUint is zero, we need to try
1295 // again with probability 0.5. This is because otherwise,
1296 // the probability of generating a zero BigInt would be
1297 // double that of any other number.
1299 return self.gen_bigint(bit_size);
1303 } else if self.gen() {
1308 BigInt::from_biguint(sign, biguint)
1311 fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint {
1312 assert!(!bound.is_zero());
1313 let bits = bound.bits();
1315 let n = self.gen_biguint(bits);
1316 if n < *bound { return n; }
1320 fn gen_biguint_range(&mut self,
1324 assert!(*lbound < *ubound);
1325 return *lbound + self.gen_biguint_below(&(*ubound - *lbound));
1328 fn gen_bigint_range(&mut self,
1332 assert!(*lbound < *ubound);
1333 let delta = (*ubound - *lbound).to_biguint().unwrap();
1334 return *lbound + self.gen_biguint_below(&delta).to_bigint().unwrap();
1339 /// Creates and initializes a BigInt.
1341 /// The digits are be in base 2^32.
1343 pub fn new(sign: Sign, digits: Vec<BigDigit>) -> BigInt {
1344 BigInt::from_biguint(sign, BigUint::new(digits))
1347 /// Creates and initializes a `BigInt`.
1349 /// The digits are be in base 2^32.
1351 pub fn from_biguint(sign: Sign, data: BigUint) -> BigInt {
1352 if sign == Zero || data.is_zero() {
1353 return BigInt { sign: Zero, data: Zero::zero() };
1355 BigInt { sign: sign, data: data }
1358 /// Creates and initializes a `BigInt`.
1360 pub fn from_slice(sign: Sign, slice: &[BigDigit]) -> BigInt {
1361 BigInt::from_biguint(sign, BigUint::from_slice(slice))
1364 /// Creates and initializes a `BigInt`.
1365 pub fn parse_bytes(buf: &[u8], radix: uint) -> Option<BigInt> {
1366 if buf.is_empty() { return None; }
1367 let mut sign = Plus;
1369 if buf[0] == ('-' as u8) {
1373 return BigUint::parse_bytes(buf.slice(start, buf.len()), radix)
1374 .map(|bu| BigInt::from_biguint(sign, bu));
1377 /// Converts this `BigInt` into a `BigUint`, if it's not negative.
1379 pub fn to_biguint(&self) -> Option<BigUint> {
1381 Plus => Some(self.data.clone()),
1382 Zero => Some(Zero::zero()),
1391 use super::{BigDigit, BigUint, ToBigUint};
1392 use super::{Plus, BigInt, RandBigInt, ToBigInt};
1394 use std::cmp::{Less, Equal, Greater};
1395 use std::from_str::FromStr;
1397 use std::num::{Zero, One, FromStrRadix, ToStrRadix};
1398 use std::num::{ToPrimitive, FromPrimitive};
1399 use std::num::CheckedDiv;
1400 use std::rand::task_rng;
1404 fn test_from_slice() {
1405 fn check(slice: &[BigDigit], data: &[BigDigit]) {
1406 assert!(data == BigUint::from_slice(slice).data.as_slice());
1409 check([0, 0, 0], []);
1410 check([1, 2, 0, 0], [1, 2]);
1411 check([0, 0, 1, 2], [0, 0, 1, 2]);
1412 check([0, 0, 1, 2, 0, 0], [0, 0, 1, 2]);
1418 let data: Vec<BigUint> = [ &[], &[1], &[2], &[-1], &[0, 1], &[2, 1], &[1, 1, 1] ]
1419 .iter().map(|v| BigUint::from_slice(*v)).collect();
1420 for (i, ni) in data.iter().enumerate() {
1421 for (j0, nj) in data.slice(i, data.len()).iter().enumerate() {
1424 assert_eq!(ni.cmp(nj), Equal);
1425 assert_eq!(nj.cmp(ni), Equal);
1427 assert!(!(ni != nj));
1430 assert!(!(ni < nj));
1431 assert!(!(ni > nj));
1433 assert_eq!(ni.cmp(nj), Less);
1434 assert_eq!(nj.cmp(ni), Greater);
1436 assert!(!(ni == nj));
1440 assert!(!(ni >= nj));
1442 assert!(!(ni > nj));
1444 assert!(!(nj <= ni));
1446 assert!(!(nj < ni));
1455 fn check(left: &[BigDigit],
1457 expected: &[BigDigit]) {
1458 assert_eq!(BigUint::from_slice(left) & BigUint::from_slice(right),
1459 BigUint::from_slice(expected));
1462 check([268, 482, 17],
1469 fn check(left: &[BigDigit],
1471 expected: &[BigDigit]) {
1472 assert_eq!(BigUint::from_slice(left) | BigUint::from_slice(right),
1473 BigUint::from_slice(expected));
1476 check([268, 482, 17],
1483 fn check(left: &[BigDigit],
1485 expected: &[BigDigit]) {
1486 assert_eq!(BigUint::from_slice(left) ^ BigUint::from_slice(right),
1487 BigUint::from_slice(expected));
1490 check([268, 482, 17],
1497 fn check(s: &str, shift: uint, ans: &str) {
1498 let opt_biguint: Option<BigUint> = FromStrRadix::from_str_radix(s, 16);
1499 let bu = (opt_biguint.unwrap() << shift).to_str_radix(16);
1500 assert_eq!(bu.as_slice(), ans);
1612 check("88887777666655554444333322221111", 16,
1613 "888877776666555544443333222211110000");
1618 fn check(s: &str, shift: uint, ans: &str) {
1619 let opt_biguint: Option<BigUint> =
1620 FromStrRadix::from_str_radix(s, 16);
1621 let bu = (opt_biguint.unwrap() >> shift).to_str_radix(16);
1622 assert_eq!(bu.as_slice(), ans);
1730 check("888877776666555544443333222211110000", 16,
1731 "88887777666655554444333322221111");
1734 // `DoubleBigDigit` size dependent
1736 fn test_convert_i64() {
1737 fn check(b1: BigUint, i: i64) {
1738 let b2: BigUint = FromPrimitive::from_i64(i).unwrap();
1740 assert!(b1.to_i64().unwrap() == i);
1743 check(Zero::zero(), 0);
1744 check(One::one(), 1);
1745 check(i64::MAX.to_biguint().unwrap(), i64::MAX);
1747 check(BigUint::new(vec!( )), 0);
1748 check(BigUint::new(vec!( 1 )), (1 << (0*BigDigit::bits)));
1749 check(BigUint::new(vec!(-1 )), (1 << (1*BigDigit::bits)) - 1);
1750 check(BigUint::new(vec!( 0, 1 )), (1 << (1*BigDigit::bits)));
1751 check(BigUint::new(vec!(-1, -1 >> 1)), i64::MAX);
1753 assert_eq!(i64::MIN.to_biguint(), None);
1754 assert_eq!(BigUint::new(vec!(-1, -1 )).to_i64(), None);
1755 assert_eq!(BigUint::new(vec!( 0, 0, 1)).to_i64(), None);
1756 assert_eq!(BigUint::new(vec!(-1, -1, -1)).to_i64(), None);
1759 // `DoubleBigDigit` size dependent
1761 fn test_convert_u64() {
1762 fn check(b1: BigUint, u: u64) {
1763 let b2: BigUint = FromPrimitive::from_u64(u).unwrap();
1765 assert!(b1.to_u64().unwrap() == u);
1768 check(Zero::zero(), 0);
1769 check(One::one(), 1);
1770 check(u64::MIN.to_biguint().unwrap(), u64::MIN);
1771 check(u64::MAX.to_biguint().unwrap(), u64::MAX);
1773 check(BigUint::new(vec!( )), 0);
1774 check(BigUint::new(vec!( 1 )), (1 << (0*BigDigit::bits)));
1775 check(BigUint::new(vec!(-1 )), (1 << (1*BigDigit::bits)) - 1);
1776 check(BigUint::new(vec!( 0, 1)), (1 << (1*BigDigit::bits)));
1777 check(BigUint::new(vec!(-1, -1)), u64::MAX);
1779 assert_eq!(BigUint::new(vec!( 0, 0, 1)).to_u64(), None);
1780 assert_eq!(BigUint::new(vec!(-1, -1, -1)).to_u64(), None);
1784 fn test_convert_to_bigint() {
1785 fn check(n: BigUint, ans: BigInt) {
1786 assert_eq!(n.to_bigint().unwrap(), ans);
1787 assert_eq!(n.to_bigint().unwrap().to_biguint().unwrap(), n);
1789 check(Zero::zero(), Zero::zero());
1790 check(BigUint::new(vec!(1,2,3)),
1791 BigInt::from_biguint(Plus, BigUint::new(vec!(1,2,3))));
1794 static sum_triples: &'static [(&'static [BigDigit],
1795 &'static [BigDigit],
1796 &'static [BigDigit])] = &[
1798 (&[], &[ 1], &[ 1]),
1799 (&[ 1], &[ 1], &[ 2]),
1800 (&[ 1], &[ 1, 1], &[ 2, 1]),
1801 (&[ 1], &[-1], &[ 0, 1]),
1802 (&[ 1], &[-1, -1], &[ 0, 0, 1]),
1803 (&[-1, -1], &[-1, -1], &[-2, -1, 1]),
1804 (&[ 1, 1, 1], &[-1, -1], &[ 0, 1, 2]),
1805 (&[ 2, 2, 1], &[-1, -2], &[ 1, 1, 2])
1810 for elm in sum_triples.iter() {
1811 let (a_vec, b_vec, c_vec) = *elm;
1812 let a = BigUint::from_slice(a_vec);
1813 let b = BigUint::from_slice(b_vec);
1814 let c = BigUint::from_slice(c_vec);
1816 assert!(a + b == c);
1817 assert!(b + a == c);
1823 for elm in sum_triples.iter() {
1824 let (a_vec, b_vec, c_vec) = *elm;
1825 let a = BigUint::from_slice(a_vec);
1826 let b = BigUint::from_slice(b_vec);
1827 let c = BigUint::from_slice(c_vec);
1829 assert!(c - a == b);
1830 assert!(c - b == a);
1836 fn test_sub_fail_on_underflow() {
1837 let (a, b) : (BigUint, BigUint) = (Zero::zero(), One::one());
1841 static mul_triples: &'static [(&'static [BigDigit],
1842 &'static [BigDigit],
1843 &'static [BigDigit])] = &[
1847 (&[ 1], &[ 1], &[1]),
1848 (&[ 2], &[ 3], &[ 6]),
1849 (&[ 1], &[ 1, 1, 1], &[1, 1, 1]),
1850 (&[ 1, 2, 3], &[ 3], &[ 3, 6, 9]),
1851 (&[ 1, 1, 1], &[-1], &[-1, -1, -1]),
1852 (&[ 1, 2, 3], &[-1], &[-1, -2, -2, 2]),
1853 (&[ 1, 2, 3, 4], &[-1], &[-1, -2, -2, -2, 3]),
1854 (&[-1], &[-1], &[ 1, -2]),
1855 (&[-1, -1], &[-1], &[ 1, -1, -2]),
1856 (&[-1, -1, -1], &[-1], &[ 1, -1, -1, -2]),
1857 (&[-1, -1, -1, -1], &[-1], &[ 1, -1, -1, -1, -2]),
1858 (&[-1/2 + 1], &[ 2], &[ 0, 1]),
1859 (&[0, -1/2 + 1], &[ 2], &[ 0, 0, 1]),
1860 (&[ 1, 2], &[ 1, 2, 3], &[1, 4, 7, 6]),
1861 (&[-1, -1], &[-1, -1, -1], &[1, 0, -1, -2, -1]),
1862 (&[-1, -1, -1], &[-1, -1, -1, -1], &[1, 0, 0, -1, -2, -1, -1]),
1863 (&[ 0, 0, 1], &[ 1, 2, 3], &[0, 0, 1, 2, 3]),
1864 (&[ 0, 0, 1], &[ 0, 0, 0, 1], &[0, 0, 0, 0, 0, 1])
1867 static div_rem_quadruples: &'static [(&'static [BigDigit],
1868 &'static [BigDigit],
1869 &'static [BigDigit],
1870 &'static [BigDigit])]
1872 (&[ 1], &[ 2], &[], &[1]),
1873 (&[ 1, 1], &[ 2], &[-1/2+1], &[1]),
1874 (&[ 1, 1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
1875 (&[ 0, 1], &[-1], &[1], &[1]),
1876 (&[-1, -1], &[-2], &[2, 1], &[3])
1881 for elm in mul_triples.iter() {
1882 let (a_vec, b_vec, c_vec) = *elm;
1883 let a = BigUint::from_slice(a_vec);
1884 let b = BigUint::from_slice(b_vec);
1885 let c = BigUint::from_slice(c_vec);
1887 assert!(a * b == c);
1888 assert!(b * a == c);
1891 for elm in div_rem_quadruples.iter() {
1892 let (a_vec, b_vec, c_vec, d_vec) = *elm;
1893 let a = BigUint::from_slice(a_vec);
1894 let b = BigUint::from_slice(b_vec);
1895 let c = BigUint::from_slice(c_vec);
1896 let d = BigUint::from_slice(d_vec);
1898 assert!(a == b * c + d);
1899 assert!(a == c * b + d);
1905 for elm in mul_triples.iter() {
1906 let (a_vec, b_vec, c_vec) = *elm;
1907 let a = BigUint::from_slice(a_vec);
1908 let b = BigUint::from_slice(b_vec);
1909 let c = BigUint::from_slice(c_vec);
1912 assert_eq!(c.div_rem(&a), (b.clone(), Zero::zero()));
1915 assert_eq!(c.div_rem(&b), (a.clone(), Zero::zero()));
1919 for elm in div_rem_quadruples.iter() {
1920 let (a_vec, b_vec, c_vec, d_vec) = *elm;
1921 let a = BigUint::from_slice(a_vec);
1922 let b = BigUint::from_slice(b_vec);
1923 let c = BigUint::from_slice(c_vec);
1924 let d = BigUint::from_slice(d_vec);
1926 if !b.is_zero() { assert!(a.div_rem(&b) == (c, d)); }
1931 fn test_checked_add() {
1932 for elm in sum_triples.iter() {
1933 let (aVec, bVec, cVec) = *elm;
1934 let a = BigUint::from_slice(aVec);
1935 let b = BigUint::from_slice(bVec);
1936 let c = BigUint::from_slice(cVec);
1938 assert!(a.checked_add(&b).unwrap() == c);
1939 assert!(b.checked_add(&a).unwrap() == c);
1944 fn test_checked_sub() {
1945 for elm in sum_triples.iter() {
1946 let (aVec, bVec, cVec) = *elm;
1947 let a = BigUint::from_slice(aVec);
1948 let b = BigUint::from_slice(bVec);
1949 let c = BigUint::from_slice(cVec);
1951 assert!(c.checked_sub(&a).unwrap() == b);
1952 assert!(c.checked_sub(&b).unwrap() == a);
1955 assert!(a.checked_sub(&c).is_none());
1958 assert!(b.checked_sub(&c).is_none());
1964 fn test_checked_mul() {
1965 for elm in mul_triples.iter() {
1966 let (aVec, bVec, cVec) = *elm;
1967 let a = BigUint::from_slice(aVec);
1968 let b = BigUint::from_slice(bVec);
1969 let c = BigUint::from_slice(cVec);
1971 assert!(a.checked_mul(&b).unwrap() == c);
1972 assert!(b.checked_mul(&a).unwrap() == c);
1975 for elm in div_rem_quadruples.iter() {
1976 let (aVec, bVec, cVec, dVec) = *elm;
1977 let a = BigUint::from_slice(aVec);
1978 let b = BigUint::from_slice(bVec);
1979 let c = BigUint::from_slice(cVec);
1980 let d = BigUint::from_slice(dVec);
1982 assert!(a == b.checked_mul(&c).unwrap() + d);
1983 assert!(a == c.checked_mul(&b).unwrap() + d);
1988 fn test_checked_div() {
1989 for elm in mul_triples.iter() {
1990 let (aVec, bVec, cVec) = *elm;
1991 let a = BigUint::from_slice(aVec);
1992 let b = BigUint::from_slice(bVec);
1993 let c = BigUint::from_slice(cVec);
1996 assert!(c.checked_div(&a).unwrap() == b);
1999 assert!(c.checked_div(&b).unwrap() == a);
2002 assert!(c.checked_div(&Zero::zero()).is_none());
2008 fn check(a: uint, b: uint, c: uint) {
2009 let big_a: BigUint = FromPrimitive::from_uint(a).unwrap();
2010 let big_b: BigUint = FromPrimitive::from_uint(b).unwrap();
2011 let big_c: BigUint = FromPrimitive::from_uint(c).unwrap();
2013 assert_eq!(big_a.gcd(&big_b), big_c);
2025 fn check(a: uint, b: uint, c: uint) {
2026 let big_a: BigUint = FromPrimitive::from_uint(a).unwrap();
2027 let big_b: BigUint = FromPrimitive::from_uint(b).unwrap();
2028 let big_c: BigUint = FromPrimitive::from_uint(c).unwrap();
2030 assert_eq!(big_a.lcm(&big_b), big_c);
2038 check(99, 17, 1683);
2043 let one: BigUint = FromStr::from_str("1").unwrap();
2044 let two: BigUint = FromStr::from_str("2").unwrap();
2045 let thousand: BigUint = FromStr::from_str("1000").unwrap();
2046 let big: BigUint = FromStr::from_str("1000000000000000000000").unwrap();
2047 let bigger: BigUint = FromStr::from_str("1000000000000000000001").unwrap();
2048 assert!(one.is_odd());
2049 assert!(two.is_even());
2050 assert!(thousand.is_even());
2051 assert!(big.is_even());
2052 assert!(bigger.is_odd());
2053 assert!((one << 64).is_even());
2054 assert!(((one << 64) + one).is_odd());
2057 fn to_str_pairs() -> Vec<(BigUint, Vec<(uint, String)>)> {
2058 let bits = BigDigit::bits;
2059 vec!(( Zero::zero(), vec!(
2060 (2, "0".to_string()), (3, "0".to_string())
2061 )), ( BigUint::from_slice([ 0xff ]), vec!(
2062 (2, "11111111".to_string()),
2063 (3, "100110".to_string()),
2064 (4, "3333".to_string()),
2065 (5, "2010".to_string()),
2066 (6, "1103".to_string()),
2067 (7, "513".to_string()),
2068 (8, "377".to_string()),
2069 (9, "313".to_string()),
2070 (10, "255".to_string()),
2071 (11, "212".to_string()),
2072 (12, "193".to_string()),
2073 (13, "168".to_string()),
2074 (14, "143".to_string()),
2075 (15, "120".to_string()),
2076 (16, "ff".to_string())
2077 )), ( BigUint::from_slice([ 0xfff ]), vec!(
2078 (2, "111111111111".to_string()),
2079 (4, "333333".to_string()),
2080 (16, "fff".to_string())
2081 )), ( BigUint::from_slice([ 1, 2 ]), vec!(
2083 format!("10{}1", "0".repeat(bits - 1))),
2085 format!("2{}1", "0".repeat(bits / 2 - 1))),
2087 32 => "8589934593".to_string(),
2088 16 => "131073".to_string(),
2092 format!("2{}1", "0".repeat(bits / 4 - 1)))
2093 )), ( BigUint::from_slice([ 1, 2, 3 ]), vec!(
2095 format!("11{}10{}1",
2096 "0".repeat(bits - 2),
2097 "0".repeat(bits - 1))),
2100 "0".repeat(bits / 2 - 1),
2101 "0".repeat(bits / 2 - 1))),
2103 32 => "55340232229718589441".to_string(),
2104 16 => "12885032961".to_string(),
2109 "0".repeat(bits / 4 - 1),
2110 "0".repeat(bits / 4 - 1)))
2115 fn test_to_str_radix() {
2116 let r = to_str_pairs();
2117 for num_pair in r.iter() {
2118 let &(ref n, ref rs) = num_pair;
2119 for str_pair in rs.iter() {
2120 let &(ref radix, ref str) = str_pair;
2121 assert_eq!(n.to_str_radix(*radix).as_slice(),
2128 fn test_from_str_radix() {
2129 let r = to_str_pairs();
2130 for num_pair in r.iter() {
2131 let &(ref n, ref rs) = num_pair;
2132 for str_pair in rs.iter() {
2133 let &(ref radix, ref str) = str_pair;
2135 &FromStrRadix::from_str_radix(str.as_slice(),
2140 let zed: Option<BigUint> = FromStrRadix::from_str_radix("Z", 10);
2141 assert_eq!(zed, None);
2142 let blank: Option<BigUint> = FromStrRadix::from_str_radix("_", 2);
2143 assert_eq!(blank, None);
2144 let minus_one: Option<BigUint> = FromStrRadix::from_str_radix("-1",
2146 assert_eq!(minus_one, None);
2151 fn factor(n: uint) -> BigUint {
2152 let mut f: BigUint = One::one();
2153 for i in range(2, n + 1) {
2154 // FIXME(#5992): assignment operator overloads
2155 // f *= FromPrimitive::from_uint(i);
2156 f = f * FromPrimitive::from_uint(i).unwrap();
2161 fn check(n: uint, s: &str) {
2163 let ans = match FromStrRadix::from_str_radix(s, 10) {
2164 Some(x) => x, None => fail!()
2170 check(10, "3628800");
2171 check(20, "2432902008176640000");
2172 check(30, "265252859812191058636308480000000");
2177 assert_eq!(BigUint::new(vec!(0,0,0,0)).bits(), 0);
2178 let n: BigUint = FromPrimitive::from_uint(0).unwrap();
2179 assert_eq!(n.bits(), 0);
2180 let n: BigUint = FromPrimitive::from_uint(1).unwrap();
2181 assert_eq!(n.bits(), 1);
2182 let n: BigUint = FromPrimitive::from_uint(3).unwrap();
2183 assert_eq!(n.bits(), 2);
2184 let n: BigUint = FromStrRadix::from_str_radix("4000000000", 16).unwrap();
2185 assert_eq!(n.bits(), 39);
2186 let one: BigUint = One::one();
2187 assert_eq!((one << 426).bits(), 427);
2192 let mut rng = task_rng();
2193 let _n: BigUint = rng.gen_biguint(137);
2194 assert!(rng.gen_biguint(0).is_zero());
2198 fn test_rand_range() {
2199 let mut rng = task_rng();
2201 for _ in range(0u, 10) {
2202 assert_eq!(rng.gen_bigint_range(&FromPrimitive::from_uint(236).unwrap(),
2203 &FromPrimitive::from_uint(237).unwrap()),
2204 FromPrimitive::from_uint(236).unwrap());
2207 let l = FromPrimitive::from_uint(403469000 + 2352).unwrap();
2208 let u = FromPrimitive::from_uint(403469000 + 3513).unwrap();
2209 for _ in range(0u, 1000) {
2210 let n: BigUint = rng.gen_biguint_below(&u);
2213 let n: BigUint = rng.gen_biguint_range(&l, &u);
2221 fn test_zero_rand_range() {
2222 task_rng().gen_biguint_range(&FromPrimitive::from_uint(54).unwrap(),
2223 &FromPrimitive::from_uint(54).unwrap());
2228 fn test_negative_rand_range() {
2229 let mut rng = task_rng();
2230 let l = FromPrimitive::from_uint(2352).unwrap();
2231 let u = FromPrimitive::from_uint(3513).unwrap();
2232 // Switching u and l should fail:
2233 let _n: BigUint = rng.gen_biguint_range(&u, &l);
2240 use super::{BigDigit, BigUint, ToBigUint};
2241 use super::{Sign, Minus, Zero, Plus, BigInt, RandBigInt, ToBigInt};
2243 use std::cmp::{Less, Equal, Greater};
2245 use std::num::CheckedDiv;
2246 use std::num::{Zero, One, FromStrRadix, ToStrRadix};
2247 use std::num::{ToPrimitive, FromPrimitive};
2248 use std::rand::task_rng;
2252 fn test_from_biguint() {
2253 fn check(inp_s: Sign, inp_n: uint, ans_s: Sign, ans_n: uint) {
2254 let inp = BigInt::from_biguint(inp_s, FromPrimitive::from_uint(inp_n).unwrap());
2255 let ans = BigInt { sign: ans_s, data: FromPrimitive::from_uint(ans_n).unwrap()};
2256 assert_eq!(inp, ans);
2258 check(Plus, 1, Plus, 1);
2259 check(Plus, 0, Zero, 0);
2260 check(Minus, 1, Minus, 1);
2261 check(Zero, 1, Zero, 0);
2266 let vs = [ &[2 as BigDigit], &[1, 1], &[2, 1], &[1, 1, 1] ];
2267 let mut nums = Vec::new();
2268 for s in vs.iter().rev() {
2269 nums.push(BigInt::from_slice(Minus, *s));
2271 nums.push(Zero::zero());
2272 nums.extend(vs.iter().map(|s| BigInt::from_slice(Plus, *s)));
2274 for (i, ni) in nums.iter().enumerate() {
2275 for (j0, nj) in nums.slice(i, nums.len()).iter().enumerate() {
2278 assert_eq!(ni.cmp(nj), Equal);
2279 assert_eq!(nj.cmp(ni), Equal);
2281 assert!(!(ni != nj));
2284 assert!(!(ni < nj));
2285 assert!(!(ni > nj));
2287 assert_eq!(ni.cmp(nj), Less);
2288 assert_eq!(nj.cmp(ni), Greater);
2290 assert!(!(ni == nj));
2294 assert!(!(ni >= nj));
2296 assert!(!(ni > nj));
2298 assert!(!(nj <= ni));
2300 assert!(!(nj < ni));
2308 fn test_convert_i64() {
2309 fn check(b1: BigInt, i: i64) {
2310 let b2: BigInt = FromPrimitive::from_i64(i).unwrap();
2312 assert!(b1.to_i64().unwrap() == i);
2315 check(Zero::zero(), 0);
2316 check(One::one(), 1);
2317 check(i64::MIN.to_bigint().unwrap(), i64::MIN);
2318 check(i64::MAX.to_bigint().unwrap(), i64::MAX);
2321 (i64::MAX as u64 + 1).to_bigint().unwrap().to_i64(),
2325 BigInt::from_biguint(Plus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_i64(),
2329 BigInt::from_biguint(Minus, BigUint::new(vec!(1,0,0,1<<(BigDigit::bits-1)))).to_i64(),
2333 BigInt::from_biguint(Minus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_i64(),
2338 fn test_convert_u64() {
2339 fn check(b1: BigInt, u: u64) {
2340 let b2: BigInt = FromPrimitive::from_u64(u).unwrap();
2342 assert!(b1.to_u64().unwrap() == u);
2345 check(Zero::zero(), 0);
2346 check(One::one(), 1);
2347 check(u64::MIN.to_bigint().unwrap(), u64::MIN);
2348 check(u64::MAX.to_bigint().unwrap(), u64::MAX);
2351 BigInt::from_biguint(Plus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_u64(),
2354 let max_value: BigUint = FromPrimitive::from_u64(u64::MAX).unwrap();
2355 assert_eq!(BigInt::from_biguint(Minus, max_value).to_u64(), None);
2356 assert_eq!(BigInt::from_biguint(Minus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_u64(), None);
2360 fn test_convert_to_biguint() {
2361 fn check(n: BigInt, ans_1: BigUint) {
2362 assert_eq!(n.to_biguint().unwrap(), ans_1);
2363 assert_eq!(n.to_biguint().unwrap().to_bigint().unwrap(), n);
2365 let zero: BigInt = Zero::zero();
2366 let unsigned_zero: BigUint = Zero::zero();
2367 let positive = BigInt::from_biguint(
2368 Plus, BigUint::new(vec!(1,2,3)));
2369 let negative = -positive;
2371 check(zero, unsigned_zero);
2372 check(positive, BigUint::new(vec!(1,2,3)));
2374 assert_eq!(negative.to_biguint(), None);
2377 static sum_triples: &'static [(&'static [BigDigit],
2378 &'static [BigDigit],
2379 &'static [BigDigit])] = &[
2381 (&[], &[ 1], &[ 1]),
2382 (&[ 1], &[ 1], &[ 2]),
2383 (&[ 1], &[ 1, 1], &[ 2, 1]),
2384 (&[ 1], &[-1], &[ 0, 1]),
2385 (&[ 1], &[-1, -1], &[ 0, 0, 1]),
2386 (&[-1, -1], &[-1, -1], &[-2, -1, 1]),
2387 (&[ 1, 1, 1], &[-1, -1], &[ 0, 1, 2]),
2388 (&[ 2, 2, 1], &[-1, -2], &[ 1, 1, 2])
2393 for elm in sum_triples.iter() {
2394 let (a_vec, b_vec, c_vec) = *elm;
2395 let a = BigInt::from_slice(Plus, a_vec);
2396 let b = BigInt::from_slice(Plus, b_vec);
2397 let c = BigInt::from_slice(Plus, c_vec);
2399 assert!(a + b == c);
2400 assert!(b + a == c);
2401 assert!(c + (-a) == b);
2402 assert!(c + (-b) == a);
2403 assert!(a + (-c) == (-b));
2404 assert!(b + (-c) == (-a));
2405 assert!((-a) + (-b) == (-c))
2406 assert!(a + (-a) == Zero::zero());
2412 for elm in sum_triples.iter() {
2413 let (a_vec, b_vec, c_vec) = *elm;
2414 let a = BigInt::from_slice(Plus, a_vec);
2415 let b = BigInt::from_slice(Plus, b_vec);
2416 let c = BigInt::from_slice(Plus, c_vec);
2418 assert!(c - a == b);
2419 assert!(c - b == a);
2420 assert!((-b) - a == (-c))
2421 assert!((-a) - b == (-c))
2422 assert!(b - (-a) == c);
2423 assert!(a - (-b) == c);
2424 assert!((-c) - (-a) == (-b));
2425 assert!(a - a == Zero::zero());
2429 static mul_triples: &'static [(&'static [BigDigit],
2430 &'static [BigDigit],
2431 &'static [BigDigit])] = &[
2435 (&[ 1], &[ 1], &[1]),
2436 (&[ 2], &[ 3], &[ 6]),
2437 (&[ 1], &[ 1, 1, 1], &[1, 1, 1]),
2438 (&[ 1, 2, 3], &[ 3], &[ 3, 6, 9]),
2439 (&[ 1, 1, 1], &[-1], &[-1, -1, -1]),
2440 (&[ 1, 2, 3], &[-1], &[-1, -2, -2, 2]),
2441 (&[ 1, 2, 3, 4], &[-1], &[-1, -2, -2, -2, 3]),
2442 (&[-1], &[-1], &[ 1, -2]),
2443 (&[-1, -1], &[-1], &[ 1, -1, -2]),
2444 (&[-1, -1, -1], &[-1], &[ 1, -1, -1, -2]),
2445 (&[-1, -1, -1, -1], &[-1], &[ 1, -1, -1, -1, -2]),
2446 (&[-1/2 + 1], &[ 2], &[ 0, 1]),
2447 (&[0, -1/2 + 1], &[ 2], &[ 0, 0, 1]),
2448 (&[ 1, 2], &[ 1, 2, 3], &[1, 4, 7, 6]),
2449 (&[-1, -1], &[-1, -1, -1], &[1, 0, -1, -2, -1]),
2450 (&[-1, -1, -1], &[-1, -1, -1, -1], &[1, 0, 0, -1, -2, -1, -1]),
2451 (&[ 0, 0, 1], &[ 1, 2, 3], &[0, 0, 1, 2, 3]),
2452 (&[ 0, 0, 1], &[ 0, 0, 0, 1], &[0, 0, 0, 0, 0, 1])
2455 static div_rem_quadruples: &'static [(&'static [BigDigit],
2456 &'static [BigDigit],
2457 &'static [BigDigit],
2458 &'static [BigDigit])]
2460 (&[ 1], &[ 2], &[], &[1]),
2461 (&[ 1, 1], &[ 2], &[-1/2+1], &[1]),
2462 (&[ 1, 1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
2463 (&[ 0, 1], &[-1], &[1], &[1]),
2464 (&[-1, -1], &[-2], &[2, 1], &[3])
2469 for elm in mul_triples.iter() {
2470 let (a_vec, b_vec, c_vec) = *elm;
2471 let a = BigInt::from_slice(Plus, a_vec);
2472 let b = BigInt::from_slice(Plus, b_vec);
2473 let c = BigInt::from_slice(Plus, c_vec);
2475 assert!(a * b == c);
2476 assert!(b * a == c);
2478 assert!((-a) * b == -c);
2479 assert!((-b) * a == -c);
2482 for elm in div_rem_quadruples.iter() {
2483 let (a_vec, b_vec, c_vec, d_vec) = *elm;
2484 let a = BigInt::from_slice(Plus, a_vec);
2485 let b = BigInt::from_slice(Plus, b_vec);
2486 let c = BigInt::from_slice(Plus, c_vec);
2487 let d = BigInt::from_slice(Plus, d_vec);
2489 assert!(a == b * c + d);
2490 assert!(a == c * b + d);
2495 fn test_div_mod_floor() {
2496 fn check_sub(a: &BigInt, b: &BigInt, ans_d: &BigInt, ans_m: &BigInt) {
2497 let (d, m) = a.div_mod_floor(b);
2499 assert_eq!(m.sign, b.sign);
2501 assert!(m.abs() <= b.abs());
2502 assert!(*a == b * d + m);
2503 assert!(d == *ans_d);
2504 assert!(m == *ans_m);
2507 fn check(a: &BigInt, b: &BigInt, d: &BigInt, m: &BigInt) {
2509 check_sub(a, b, d, m);
2510 check_sub(a, &b.neg(), &d.neg(), m);
2511 check_sub(&a.neg(), b, &d.neg(), m);
2512 check_sub(&a.neg(), &b.neg(), d, m);
2514 check_sub(a, b, d, m);
2515 check_sub(a, &b.neg(), &(d.neg() - One::one()), &(m - *b));
2516 check_sub(&a.neg(), b, &(d.neg() - One::one()), &(b - *m));
2517 check_sub(&a.neg(), &b.neg(), d, &m.neg());
2521 for elm in mul_triples.iter() {
2522 let (a_vec, b_vec, c_vec) = *elm;
2523 let a = BigInt::from_slice(Plus, a_vec);
2524 let b = BigInt::from_slice(Plus, b_vec);
2525 let c = BigInt::from_slice(Plus, c_vec);
2527 if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
2528 if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
2531 for elm in div_rem_quadruples.iter() {
2532 let (a_vec, b_vec, c_vec, d_vec) = *elm;
2533 let a = BigInt::from_slice(Plus, a_vec);
2534 let b = BigInt::from_slice(Plus, b_vec);
2535 let c = BigInt::from_slice(Plus, c_vec);
2536 let d = BigInt::from_slice(Plus, d_vec);
2539 check(&a, &b, &c, &d);
2547 fn check_sub(a: &BigInt, b: &BigInt, ans_q: &BigInt, ans_r: &BigInt) {
2548 let (q, r) = a.div_rem(b);
2550 assert_eq!(r.sign, a.sign);
2552 assert!(r.abs() <= b.abs());
2553 assert!(*a == b * q + r);
2554 assert!(q == *ans_q);
2555 assert!(r == *ans_r);
2558 fn check(a: &BigInt, b: &BigInt, q: &BigInt, r: &BigInt) {
2559 check_sub(a, b, q, r);
2560 check_sub(a, &b.neg(), &q.neg(), r);
2561 check_sub(&a.neg(), b, &q.neg(), &r.neg());
2562 check_sub(&a.neg(), &b.neg(), q, &r.neg());
2564 for elm in mul_triples.iter() {
2565 let (a_vec, b_vec, c_vec) = *elm;
2566 let a = BigInt::from_slice(Plus, a_vec);
2567 let b = BigInt::from_slice(Plus, b_vec);
2568 let c = BigInt::from_slice(Plus, c_vec);
2570 if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
2571 if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
2574 for elm in div_rem_quadruples.iter() {
2575 let (a_vec, b_vec, c_vec, d_vec) = *elm;
2576 let a = BigInt::from_slice(Plus, a_vec);
2577 let b = BigInt::from_slice(Plus, b_vec);
2578 let c = BigInt::from_slice(Plus, c_vec);
2579 let d = BigInt::from_slice(Plus, d_vec);
2582 check(&a, &b, &c, &d);
2588 fn test_checked_add() {
2589 for elm in sum_triples.iter() {
2590 let (aVec, bVec, cVec) = *elm;
2591 let a = BigInt::from_slice(Plus, aVec);
2592 let b = BigInt::from_slice(Plus, bVec);
2593 let c = BigInt::from_slice(Plus, cVec);
2595 assert!(a.checked_add(&b).unwrap() == c);
2596 assert!(b.checked_add(&a).unwrap() == c);
2597 assert!(c.checked_add(&(-a)).unwrap() == b);
2598 assert!(c.checked_add(&(-b)).unwrap() == a);
2599 assert!(a.checked_add(&(-c)).unwrap() == (-b));
2600 assert!(b.checked_add(&(-c)).unwrap() == (-a));
2601 assert!((-a).checked_add(&(-b)).unwrap() == (-c))
2602 assert!(a.checked_add(&(-a)).unwrap() == Zero::zero());
2607 fn test_checked_sub() {
2608 for elm in sum_triples.iter() {
2609 let (aVec, bVec, cVec) = *elm;
2610 let a = BigInt::from_slice(Plus, aVec);
2611 let b = BigInt::from_slice(Plus, bVec);
2612 let c = BigInt::from_slice(Plus, cVec);
2614 assert!(c.checked_sub(&a).unwrap() == b);
2615 assert!(c.checked_sub(&b).unwrap() == a);
2616 assert!((-b).checked_sub(&a).unwrap() == (-c))
2617 assert!((-a).checked_sub(&b).unwrap() == (-c))
2618 assert!(b.checked_sub(&(-a)).unwrap() == c);
2619 assert!(a.checked_sub(&(-b)).unwrap() == c);
2620 assert!((-c).checked_sub(&(-a)).unwrap() == (-b));
2621 assert!(a.checked_sub(&a).unwrap() == Zero::zero());
2626 fn test_checked_mul() {
2627 for elm in mul_triples.iter() {
2628 let (aVec, bVec, cVec) = *elm;
2629 let a = BigInt::from_slice(Plus, aVec);
2630 let b = BigInt::from_slice(Plus, bVec);
2631 let c = BigInt::from_slice(Plus, cVec);
2633 assert!(a.checked_mul(&b).unwrap() == c);
2634 assert!(b.checked_mul(&a).unwrap() == c);
2636 assert!((-a).checked_mul(&b).unwrap() == -c);
2637 assert!((-b).checked_mul(&a).unwrap() == -c);
2640 for elm in div_rem_quadruples.iter() {
2641 let (aVec, bVec, cVec, dVec) = *elm;
2642 let a = BigInt::from_slice(Plus, aVec);
2643 let b = BigInt::from_slice(Plus, bVec);
2644 let c = BigInt::from_slice(Plus, cVec);
2645 let d = BigInt::from_slice(Plus, dVec);
2647 assert!(a == b.checked_mul(&c).unwrap() + d);
2648 assert!(a == c.checked_mul(&b).unwrap() + d);
2652 fn test_checked_div() {
2653 for elm in mul_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);
2660 assert!(c.checked_div(&a).unwrap() == b);
2661 assert!((-c).checked_div(&(-a)).unwrap() == b);
2662 assert!((-c).checked_div(&a).unwrap() == -b);
2665 assert!(c.checked_div(&b).unwrap() == a);
2666 assert!((-c).checked_div(&(-b)).unwrap() == a);
2667 assert!((-c).checked_div(&b).unwrap() == -a);
2670 assert!(c.checked_div(&Zero::zero()).is_none());
2671 assert!((-c).checked_div(&Zero::zero()).is_none());
2677 fn check(a: int, b: int, c: int) {
2678 let big_a: BigInt = FromPrimitive::from_int(a).unwrap();
2679 let big_b: BigInt = FromPrimitive::from_int(b).unwrap();
2680 let big_c: BigInt = FromPrimitive::from_int(c).unwrap();
2682 assert_eq!(big_a.gcd(&big_b), big_c);
2697 fn check(a: int, b: int, c: int) {
2698 let big_a: BigInt = FromPrimitive::from_int(a).unwrap();
2699 let big_b: BigInt = FromPrimitive::from_int(b).unwrap();
2700 let big_c: BigInt = FromPrimitive::from_int(c).unwrap();
2702 assert_eq!(big_a.lcm(&big_b), big_c);
2717 let zero: BigInt = Zero::zero();
2718 let one: BigInt = One::one();
2719 assert_eq!((-one).abs_sub(&one), zero);
2720 let one: BigInt = One::one();
2721 let zero: BigInt = Zero::zero();
2722 assert_eq!(one.abs_sub(&one), zero);
2723 let one: BigInt = One::one();
2724 let zero: BigInt = Zero::zero();
2725 assert_eq!(one.abs_sub(&zero), one);
2726 let one: BigInt = One::one();
2727 let two: BigInt = FromPrimitive::from_int(2).unwrap();
2728 assert_eq!(one.abs_sub(&-one), two);
2732 fn test_to_str_radix() {
2733 fn check(n: int, ans: &str) {
2734 let n: BigInt = FromPrimitive::from_int(n).unwrap();
2735 assert!(ans == n.to_str_radix(10).as_slice());
2746 fn test_from_str_radix() {
2747 fn check(s: &str, ans: Option<int>) {
2748 let ans = ans.map(|n| {
2749 let x: BigInt = FromPrimitive::from_int(n).unwrap();
2752 assert_eq!(FromStrRadix::from_str_radix(s, 10), ans);
2754 check("10", Some(10));
2755 check("1", Some(1));
2756 check("0", Some(0));
2757 check("-1", Some(-1));
2758 check("-10", Some(-10));
2762 // issue 10522, this hit an edge case that caused it to
2763 // attempt to allocate a vector of size (-1u) == huge.
2765 from_str(format!("1{}", "0".repeat(36)).as_slice()).unwrap();
2766 let _y = x.to_string();
2771 assert!(-BigInt::new(Plus, vec!(1, 1, 1)) ==
2772 BigInt::new(Minus, vec!(1, 1, 1)));
2773 assert!(-BigInt::new(Minus, vec!(1, 1, 1)) ==
2774 BigInt::new(Plus, vec!(1, 1, 1)));
2775 let zero: BigInt = Zero::zero();
2776 assert_eq!(-zero, zero);
2781 let mut rng = task_rng();
2782 let _n: BigInt = rng.gen_bigint(137);
2783 assert!(rng.gen_bigint(0).is_zero());
2787 fn test_rand_range() {
2788 let mut rng = task_rng();
2790 for _ in range(0u, 10) {
2791 assert_eq!(rng.gen_bigint_range(&FromPrimitive::from_uint(236).unwrap(),
2792 &FromPrimitive::from_uint(237).unwrap()),
2793 FromPrimitive::from_uint(236).unwrap());
2796 fn check(l: BigInt, u: BigInt) {
2797 let mut rng = task_rng();
2798 for _ in range(0u, 1000) {
2799 let n: BigInt = rng.gen_bigint_range(&l, &u);
2804 let l: BigInt = FromPrimitive::from_uint(403469000 + 2352).unwrap();
2805 let u: BigInt = FromPrimitive::from_uint(403469000 + 3513).unwrap();
2806 check( l.clone(), u.clone());
2807 check(-l.clone(), u.clone());
2808 check(-u.clone(), -l.clone());
2813 fn test_zero_rand_range() {
2814 task_rng().gen_bigint_range(&FromPrimitive::from_int(54).unwrap(),
2815 &FromPrimitive::from_int(54).unwrap());
2820 fn test_negative_rand_range() {
2821 let mut rng = task_rng();
2822 let l = FromPrimitive::from_uint(2352).unwrap();
2823 let u = FromPrimitive::from_uint(3513).unwrap();
2824 // Switching u and l should fail:
2825 let _n: BigInt = rng.gen_bigint_range(&u, &l);
2832 use self::test::Bencher;
2835 use std::mem::replace;
2836 use std::num::{FromPrimitive, Zero, One};
2838 fn factorial(n: uint) -> BigUint {
2839 let mut f: BigUint = One::one();
2840 for i in iter::range_inclusive(1, n) {
2841 f = f * FromPrimitive::from_uint(i).unwrap();
2846 fn fib(n: uint) -> BigUint {
2847 let mut f0: BigUint = Zero::zero();
2848 let mut f1: BigUint = One::one();
2849 for _ in range(0, n) {
2851 f0 = replace(&mut f1, f2);
2857 fn factorial_100(b: &mut Bencher) {
2864 fn fib_100(b: &mut Bencher) {
2871 fn to_string(b: &mut Bencher) {
2872 let fac = factorial(100);
2883 fn shr(b: &mut Bencher) {
2884 let n = { let one : BigUint = One::one(); one << 1000 };
2886 let mut m = n.clone();
2887 for _ in range(0u, 10) {