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.
13 A Big integer (signed version: `BigInt`, unsigned version: `BigUint`).
15 A `BigUint` is represented as an array of `BigDigit`s.
16 A `BigInt` is a combination of `BigUint` and `Sign`.
23 use std::default::Default;
24 use std::from_str::FromStr;
25 use std::num::CheckedDiv;
26 use std::num::{ToPrimitive, FromPrimitive};
27 use std::num::{Zero, One, ToStrRadix, FromStrRadix};
28 use std::string::String;
29 use std::{uint, i64, u64};
32 A `BigDigit` is a `BigUint`'s composing element.
34 pub type BigDigit = u32;
37 A `DoubleBigDigit` is the internal type used to do the computations. Its
38 size is the double of the size of `BigDigit`.
40 pub type DoubleBigDigit = u64;
42 pub static ZERO_BIG_DIGIT: BigDigit = 0;
43 static ZERO_VEC: [BigDigit, ..1] = [ZERO_BIG_DIGIT];
47 use super::DoubleBigDigit;
49 // `DoubleBigDigit` size dependent
50 pub static bits: uint = 32;
52 pub static base: DoubleBigDigit = 1 << bits;
53 static lo_mask: DoubleBigDigit = (-1 as DoubleBigDigit) >> bits;
56 fn get_hi(n: DoubleBigDigit) -> BigDigit { (n >> bits) as BigDigit }
58 fn get_lo(n: DoubleBigDigit) -> BigDigit { (n & lo_mask) as BigDigit }
60 /// Split one `DoubleBigDigit` into two `BigDigit`s.
62 pub fn from_doublebigdigit(n: DoubleBigDigit) -> (BigDigit, BigDigit) {
63 (get_hi(n), get_lo(n))
66 /// Join two `BigDigit`s into one `DoubleBigDigit`
68 pub fn to_doublebigdigit(hi: BigDigit, lo: BigDigit) -> DoubleBigDigit {
69 (lo as DoubleBigDigit) | ((hi as DoubleBigDigit) << bits)
74 A big unsigned integer type.
76 A `BigUint`-typed value `BigUint { data: vec!(a, b, c) }` represents a number
77 `(a + b * BigDigit::base + c * BigDigit::base^2)`.
84 impl PartialEq for BigUint {
86 fn eq(&self, other: &BigUint) -> bool {
87 match self.cmp(other) { Equal => true, _ => false }
90 impl Eq for BigUint {}
92 impl PartialOrd for BigUint {
94 fn partial_cmp(&self, other: &BigUint) -> Option<Ordering> {
99 impl Ord for BigUint {
101 fn cmp(&self, other: &BigUint) -> Ordering {
102 let (s_len, o_len) = (self.data.len(), other.data.len());
103 if s_len < o_len { return Less; }
104 if s_len > o_len { return Greater; }
106 for (&self_i, &other_i) in self.data.iter().rev().zip(other.data.iter().rev()) {
107 if self_i < other_i { return Less; }
108 if self_i > other_i { return Greater; }
114 impl Default for BigUint {
116 fn default() -> BigUint { Zero::zero() }
119 impl fmt::Show for BigUint {
120 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
121 write!(f, "{}", self.to_str_radix(10))
125 impl FromStr for BigUint {
127 fn from_str(s: &str) -> Option<BigUint> {
128 FromStrRadix::from_str_radix(s, 10)
132 impl Num for BigUint {}
134 impl BitAnd<BigUint, BigUint> for BigUint {
135 fn bitand(&self, other: &BigUint) -> BigUint {
136 BigUint::new(self.data.iter().zip(other.data.iter()).map(|(ai, bi)| *ai & *bi).collect())
140 impl BitOr<BigUint, BigUint> for BigUint {
141 fn bitor(&self, other: &BigUint) -> BigUint {
142 let zeros = ZERO_VEC.iter().cycle();
143 let (a, b) = if self.data.len() > other.data.len() { (self, other) } else { (other, self) };
144 let ored = a.data.iter().zip(b.data.iter().chain(zeros)).map(
147 return BigUint::new(ored);
151 impl BitXor<BigUint, BigUint> for BigUint {
152 fn bitxor(&self, other: &BigUint) -> BigUint {
153 let zeros = ZERO_VEC.iter().cycle();
154 let (a, b) = if self.data.len() > other.data.len() { (self, other) } else { (other, self) };
155 let xored = a.data.iter().zip(b.data.iter().chain(zeros)).map(
158 return BigUint::new(xored);
162 impl Shl<uint, BigUint> for BigUint {
164 fn shl(&self, rhs: &uint) -> BigUint {
165 let n_unit = *rhs / BigDigit::bits;
166 let n_bits = *rhs % BigDigit::bits;
167 return self.shl_unit(n_unit).shl_bits(n_bits);
171 impl Shr<uint, BigUint> for BigUint {
173 fn shr(&self, rhs: &uint) -> BigUint {
174 let n_unit = *rhs / BigDigit::bits;
175 let n_bits = *rhs % BigDigit::bits;
176 return self.shr_unit(n_unit).shr_bits(n_bits);
180 impl Zero for BigUint {
182 fn zero() -> BigUint { BigUint::new(Vec::new()) }
185 fn is_zero(&self) -> bool { self.data.is_empty() }
188 impl One for BigUint {
190 fn one() -> BigUint { BigUint::new(vec!(1)) }
193 impl Unsigned for BigUint {}
195 impl Add<BigUint, BigUint> for BigUint {
196 fn add(&self, other: &BigUint) -> BigUint {
197 let zeros = ZERO_VEC.iter().cycle();
198 let (a, b) = if self.data.len() > other.data.len() { (self, other) } else { (other, self) };
201 let mut sum: Vec<BigDigit> = a.data.iter().zip(b.data.iter().chain(zeros)).map(|(ai, bi)| {
202 let (hi, lo) = BigDigit::from_doublebigdigit(
203 (*ai as DoubleBigDigit) + (*bi as DoubleBigDigit) + (carry as DoubleBigDigit));
207 if carry != 0 { sum.push(carry); }
208 return BigUint::new(sum);
212 impl Sub<BigUint, BigUint> for BigUint {
213 fn sub(&self, other: &BigUint) -> BigUint {
214 let new_len = cmp::max(self.data.len(), other.data.len());
215 let zeros = ZERO_VEC.iter().cycle();
216 let (a, b) = (self.data.iter().chain(zeros.clone()), other.data.iter().chain(zeros));
219 let diff: Vec<BigDigit> = a.take(new_len).zip(b).map(|(ai, bi)| {
220 let (hi, lo) = BigDigit::from_doublebigdigit(
222 + (*ai as DoubleBigDigit)
223 - (*bi as DoubleBigDigit)
224 - (borrow as DoubleBigDigit)
227 hi * (base) + lo == 1*(base) + ai - bi - borrow
228 => ai - bi - borrow < 0 <=> hi == 0
230 borrow = if hi == 0 { 1 } else { 0 };
235 "Cannot subtract other from self because other is larger than self.");
236 return BigUint::new(diff);
240 impl Mul<BigUint, BigUint> for BigUint {
241 fn mul(&self, other: &BigUint) -> BigUint {
242 if self.is_zero() || other.is_zero() { return Zero::zero(); }
244 let (s_len, o_len) = (self.data.len(), other.data.len());
245 if s_len == 1 { return mul_digit(other, self.data.as_slice()[0]); }
246 if o_len == 1 { return mul_digit(self, other.data.as_slice()[0]); }
248 // Using Karatsuba multiplication
249 // (a1 * base + a0) * (b1 * base + b0)
250 // = a1*b1 * base^2 +
251 // (a1*b1 + a0*b0 - (a1-b0)*(b1-a0)) * base +
253 let half_len = cmp::max(s_len, o_len) / 2;
254 let (s_hi, s_lo) = cut_at(self, half_len);
255 let (o_hi, o_lo) = cut_at(other, half_len);
257 let ll = s_lo * o_lo;
258 let hh = s_hi * o_hi;
260 let (s1, n1) = sub_sign(s_hi, s_lo);
261 let (s2, n2) = sub_sign(o_hi, o_lo);
263 (Equal, _) | (_, Equal) => hh + ll,
264 (Less, Greater) | (Greater, Less) => hh + ll + (n1 * n2),
265 (Less, Less) | (Greater, Greater) => hh + ll - (n1 * n2)
269 return ll + mm.shl_unit(half_len) + hh.shl_unit(half_len * 2);
272 fn mul_digit(a: &BigUint, n: BigDigit) -> BigUint {
273 if n == 0 { return Zero::zero(); }
274 if n == 1 { return (*a).clone(); }
277 let mut prod: Vec<BigDigit> = a.data.iter().map(|ai| {
278 let (hi, lo) = BigDigit::from_doublebigdigit(
279 (*ai as DoubleBigDigit) * (n as DoubleBigDigit) + (carry as DoubleBigDigit)
284 if carry != 0 { prod.push(carry); }
285 return BigUint::new(prod);
289 fn cut_at(a: &BigUint, n: uint) -> (BigUint, BigUint) {
290 let mid = cmp::min(a.data.len(), n);
291 return (BigUint::from_slice(a.data.slice(mid, a.data.len())),
292 BigUint::from_slice(a.data.slice(0, mid)));
296 fn sub_sign(a: BigUint, b: BigUint) -> (Ordering, BigUint) {
298 Less => (Less, b - a),
299 Greater => (Greater, a - b),
300 _ => (Equal, Zero::zero())
306 impl Div<BigUint, BigUint> for BigUint {
308 fn div(&self, other: &BigUint) -> BigUint {
309 let (q, _) = self.div_rem(other);
314 impl Rem<BigUint, BigUint> for BigUint {
316 fn rem(&self, other: &BigUint) -> BigUint {
317 let (_, r) = self.div_rem(other);
322 impl Neg<BigUint> for BigUint {
324 fn neg(&self) -> BigUint { fail!() }
327 impl CheckedAdd for BigUint {
329 fn checked_add(&self, v: &BigUint) -> Option<BigUint> {
330 return Some(self.add(v));
334 impl CheckedSub for BigUint {
336 fn checked_sub(&self, v: &BigUint) -> Option<BigUint> {
340 return Some(self.sub(v));
344 impl CheckedMul for BigUint {
346 fn checked_mul(&self, v: &BigUint) -> Option<BigUint> {
347 return Some(self.mul(v));
351 impl CheckedDiv for BigUint {
353 fn checked_div(&self, v: &BigUint) -> Option<BigUint> {
357 return Some(self.div(v));
361 impl Integer for BigUint {
363 fn div_rem(&self, other: &BigUint) -> (BigUint, BigUint) {
364 self.div_mod_floor(other)
368 fn div_floor(&self, other: &BigUint) -> BigUint {
369 let (d, _) = self.div_mod_floor(other);
374 fn mod_floor(&self, other: &BigUint) -> BigUint {
375 let (_, m) = self.div_mod_floor(other);
379 fn div_mod_floor(&self, other: &BigUint) -> (BigUint, BigUint) {
380 if other.is_zero() { fail!() }
381 if self.is_zero() { return (Zero::zero(), Zero::zero()); }
382 if *other == One::one() { return ((*self).clone(), Zero::zero()); }
384 match self.cmp(other) {
385 Less => return (Zero::zero(), (*self).clone()),
386 Equal => return (One::one(), Zero::zero()),
387 Greater => {} // Do nothing
391 let mut n = *other.data.last().unwrap();
392 while n < (1 << BigDigit::bits - 2) {
396 assert!(shift < BigDigit::bits);
397 let (d, m) = div_mod_floor_inner(self << shift, other << shift);
398 return (d, m >> shift);
401 fn div_mod_floor_inner(a: BigUint, b: BigUint) -> (BigUint, BigUint) {
403 let mut d: BigUint = Zero::zero();
406 let (d0, d_unit, b_unit) = div_estimate(&m, &b, n);
408 let mut prod = b * d0;
410 // FIXME(#5992): assignment operator overloads
413 // FIXME(#5992): assignment operator overloads
422 // FIXME(#5992): assignment operator overloads
425 // FIXME(#5992): assignment operator overloads
433 fn div_estimate(a: &BigUint, b: &BigUint, n: uint)
434 -> (BigUint, BigUint, BigUint) {
435 if a.data.len() < n {
436 return (Zero::zero(), Zero::zero(), (*a).clone());
439 let an = a.data.tailn(a.data.len() - n);
440 let bn = *b.data.last().unwrap();
441 let mut d = Vec::with_capacity(an.len());
443 for elt in an.iter().rev() {
444 let ai = BigDigit::to_doublebigdigit(carry, *elt);
445 let di = ai / (bn as DoubleBigDigit);
446 assert!(di < BigDigit::base);
447 carry = (ai % (bn as DoubleBigDigit)) as BigDigit;
448 d.push(di as BigDigit)
452 let shift = (a.data.len() - an.len()) - (b.data.len() - 1);
454 return (BigUint::new(d), One::one(), (*b).clone());
456 let one: BigUint = One::one();
457 return (BigUint::new(d).shl_unit(shift),
464 * Calculates the Greatest Common Divisor (GCD) of the number and `other`
466 * The result is always positive
469 fn gcd(&self, other: &BigUint) -> BigUint {
470 // Use Euclid's algorithm
471 let mut m = (*self).clone();
472 let mut n = (*other).clone();
482 * Calculates the Lowest Common Multiple (LCM) of the number and `other`
485 fn lcm(&self, other: &BigUint) -> BigUint { ((*self * *other) / self.gcd(other)) }
487 /// Returns `true` if the number can be divided by `other` without leaving a remainder
489 fn divides(&self, other: &BigUint) -> bool { (*self % *other).is_zero() }
491 /// Returns `true` if the number is divisible by `2`
493 fn is_even(&self) -> bool {
494 // Considering only the last digit.
495 match self.data.as_slice().head() {
496 Some(x) => x.is_even(),
501 /// Returns `true` if the number is not divisible by `2`
503 fn is_odd(&self) -> bool { !self.is_even() }
506 impl ToPrimitive for BigUint {
508 fn to_i64(&self) -> Option<i64> {
509 self.to_u64().and_then(|n| {
510 // If top bit of u64 is set, it's too large to convert to i64.
519 // `DoubleBigDigit` size dependent
521 fn to_u64(&self) -> Option<u64> {
522 match self.data.len() {
524 1 => Some(self.data.as_slice()[0] as u64),
525 2 => Some(BigDigit::to_doublebigdigit(self.data.as_slice()[1], self.data.as_slice()[0])
532 impl FromPrimitive for BigUint {
534 fn from_i64(n: i64) -> Option<BigUint> {
536 FromPrimitive::from_u64(n as u64)
544 // `DoubleBigDigit` size dependent
546 fn from_u64(n: u64) -> Option<BigUint> {
547 let n = match BigDigit::from_doublebigdigit(n) {
548 (0, 0) => Zero::zero(),
549 (0, n0) => BigUint::new(vec!(n0)),
550 (n1, n0) => BigUint::new(vec!(n0, n1))
556 /// A generic trait for converting a value to a `BigUint`.
557 pub trait ToBigUint {
558 /// Converts the value of `self` to a `BigUint`.
559 fn to_biguint(&self) -> Option<BigUint>;
562 impl ToBigUint for BigInt {
564 fn to_biguint(&self) -> Option<BigUint> {
565 if self.sign == Plus {
566 Some(self.data.clone())
567 } else if self.sign == Zero {
575 impl ToBigUint for BigUint {
577 fn to_biguint(&self) -> Option<BigUint> {
582 macro_rules! impl_to_biguint(
583 ($T:ty, $from_ty:path) => {
584 impl ToBigUint for $T {
586 fn to_biguint(&self) -> Option<BigUint> {
593 impl_to_biguint!(int, FromPrimitive::from_int)
594 impl_to_biguint!(i8, FromPrimitive::from_i8)
595 impl_to_biguint!(i16, FromPrimitive::from_i16)
596 impl_to_biguint!(i32, FromPrimitive::from_i32)
597 impl_to_biguint!(i64, FromPrimitive::from_i64)
598 impl_to_biguint!(uint, FromPrimitive::from_uint)
599 impl_to_biguint!(u8, FromPrimitive::from_u8)
600 impl_to_biguint!(u16, FromPrimitive::from_u16)
601 impl_to_biguint!(u32, FromPrimitive::from_u32)
602 impl_to_biguint!(u64, FromPrimitive::from_u64)
604 impl ToStrRadix for BigUint {
605 fn to_str_radix(&self, radix: uint) -> String {
606 assert!(1 < radix && radix <= 16, "The radix must be within (1, 16]");
607 let (base, max_len) = get_radix_base(radix);
608 if base == BigDigit::base {
609 return fill_concat(self.data.as_slice(), radix, max_len)
611 return fill_concat(convert_base(self, base).as_slice(), radix, max_len);
613 fn convert_base(n: &BigUint, base: DoubleBigDigit) -> Vec<BigDigit> {
614 let divider = base.to_biguint().unwrap();
615 let mut result = Vec::new();
616 let mut m = n.clone();
618 let (d, m0) = m.div_mod_floor(÷r);
619 result.push(m0.to_uint().unwrap() as BigDigit);
623 result.push(m.to_uint().unwrap() as BigDigit);
628 fn fill_concat(v: &[BigDigit], radix: uint, l: uint) -> String {
630 return "0".to_string()
632 let mut s = String::with_capacity(v.len() * l);
633 for n in v.iter().rev() {
634 let ss = (*n as uint).to_str_radix(radix);
635 s.push_str("0".repeat(l - ss.len()).as_slice());
636 s.push_str(ss.as_slice());
638 s.as_slice().trim_left_chars('0').to_string()
643 impl FromStrRadix for BigUint {
644 /// Creates and initializes a `BigUint`.
646 fn from_str_radix(s: &str, radix: uint) -> Option<BigUint> {
647 BigUint::parse_bytes(s.as_bytes(), radix)
652 /// Creates and initializes a `BigUint`.
654 /// The digits are be in base 2^32.
656 pub fn new(mut digits: Vec<BigDigit>) -> BigUint {
657 // omit trailing zeros
658 let new_len = digits.iter().rposition(|n| *n != 0).map_or(0, |p| p + 1);
659 digits.truncate(new_len);
660 BigUint { data: digits }
663 /// Creates and initializes a `BigUint`.
665 /// The digits are be in base 2^32.
667 pub fn from_slice(slice: &[BigDigit]) -> BigUint {
668 BigUint::new(Vec::from_slice(slice))
671 /// Creates and initializes a `BigUint`.
672 pub fn parse_bytes(buf: &[u8], radix: uint) -> Option<BigUint> {
673 let (base, unit_len) = get_radix_base(radix);
674 let base_num = match base.to_biguint() {
675 Some(base_num) => base_num,
676 None => { return None; }
679 let mut end = buf.len();
680 let mut n: BigUint = Zero::zero();
681 let mut power: BigUint = One::one();
683 let start = cmp::max(end, unit_len) - unit_len;
684 match uint::parse_bytes(buf.slice(start, end), radix) {
686 let d: Option<BigUint> = FromPrimitive::from_uint(d);
689 // FIXME(#5992): assignment operator overloads
693 None => { return None; }
696 None => { return None; }
702 // FIXME(#5992): assignment operator overloads
703 // power *= base_num;
704 power = power * base_num;
709 fn shl_unit(&self, n_unit: uint) -> BigUint {
710 if n_unit == 0 || self.is_zero() { return (*self).clone(); }
712 BigUint::new(Vec::from_elem(n_unit, ZERO_BIG_DIGIT).append(self.data.as_slice()))
716 fn shl_bits(&self, n_bits: uint) -> BigUint {
717 if n_bits == 0 || self.is_zero() { return (*self).clone(); }
720 let mut shifted: Vec<BigDigit> = self.data.iter().map(|elem| {
721 let (hi, lo) = BigDigit::from_doublebigdigit(
722 (*elem as DoubleBigDigit) << n_bits | (carry as DoubleBigDigit)
727 if carry != 0 { shifted.push(carry); }
728 return BigUint::new(shifted);
732 fn shr_unit(&self, n_unit: uint) -> BigUint {
733 if n_unit == 0 { return (*self).clone(); }
734 if self.data.len() < n_unit { return Zero::zero(); }
735 return BigUint::from_slice(
736 self.data.slice(n_unit, self.data.len())
741 fn shr_bits(&self, n_bits: uint) -> BigUint {
742 if n_bits == 0 || self.data.is_empty() { return (*self).clone(); }
745 let mut shifted_rev = Vec::with_capacity(self.data.len());
746 for elem in self.data.iter().rev() {
747 shifted_rev.push((*elem >> n_bits) | borrow);
748 borrow = *elem << (BigDigit::bits - n_bits);
750 let shifted = { shifted_rev.reverse(); shifted_rev };
751 return BigUint::new(shifted);
754 /// Determines the fewest bits necessary to express the `BigUint`.
755 pub fn bits(&self) -> uint {
756 if self.is_zero() { return 0; }
757 let zeros = self.data.last().unwrap().leading_zeros();
758 return self.data.len()*BigDigit::bits - (zeros as uint);
762 // `DoubleBigDigit` size dependent
764 fn get_radix_base(radix: uint) -> (DoubleBigDigit, uint) {
766 2 => (4294967296, 32),
767 3 => (3486784401, 20),
768 4 => (4294967296, 16),
769 5 => (1220703125, 13),
770 6 => (2176782336, 12),
771 7 => (1977326743, 11),
772 8 => (1073741824, 10),
773 9 => (3486784401, 10),
774 10 => (1000000000, 9),
775 11 => (2357947691, 9),
776 12 => (429981696, 8),
777 13 => (815730721, 8),
778 14 => (1475789056, 8),
779 15 => (2562890625, 8),
780 16 => (4294967296, 8),
781 _ => fail!("The radix must be within (1, 16]")
785 /// A Sign is a `BigInt`'s composing element.
786 #[deriving(PartialEq, PartialOrd, Eq, Ord, Clone, Show)]
787 pub enum Sign { Minus, Zero, Plus }
789 impl Neg<Sign> for Sign {
790 /// Negate Sign value.
792 fn neg(&self) -> Sign {
801 /// A big signed integer type.
808 impl PartialEq for BigInt {
810 fn eq(&self, other: &BigInt) -> bool {
811 self.cmp(other) == Equal
815 impl Eq for BigInt {}
817 impl PartialOrd for BigInt {
819 fn partial_cmp(&self, other: &BigInt) -> Option<Ordering> {
820 Some(self.cmp(other))
824 impl Ord for BigInt {
826 fn cmp(&self, other: &BigInt) -> Ordering {
827 let scmp = self.sign.cmp(&other.sign);
828 if scmp != Equal { return scmp; }
832 Plus => self.data.cmp(&other.data),
833 Minus => other.data.cmp(&self.data),
838 impl Default for BigInt {
840 fn default() -> BigInt { Zero::zero() }
843 impl fmt::Show for BigInt {
844 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
845 write!(f, "{}", self.to_str_radix(10))
849 impl FromStr for BigInt {
851 fn from_str(s: &str) -> Option<BigInt> {
852 FromStrRadix::from_str_radix(s, 10)
856 impl Num for BigInt {}
858 impl Shl<uint, BigInt> for BigInt {
860 fn shl(&self, rhs: &uint) -> BigInt {
861 BigInt::from_biguint(self.sign, self.data << *rhs)
865 impl Shr<uint, BigInt> for BigInt {
867 fn shr(&self, rhs: &uint) -> BigInt {
868 BigInt::from_biguint(self.sign, self.data >> *rhs)
872 impl Zero for BigInt {
874 fn zero() -> BigInt {
875 BigInt::from_biguint(Zero, Zero::zero())
879 fn is_zero(&self) -> bool { self.sign == Zero }
882 impl One for BigInt {
885 BigInt::from_biguint(Plus, One::one())
889 impl Signed for BigInt {
891 fn abs(&self) -> BigInt {
893 Plus | Zero => self.clone(),
894 Minus => BigInt::from_biguint(Plus, self.data.clone())
899 fn abs_sub(&self, other: &BigInt) -> BigInt {
900 if *self <= *other { Zero::zero() } else { *self - *other }
904 fn signum(&self) -> BigInt {
906 Plus => BigInt::from_biguint(Plus, One::one()),
907 Minus => BigInt::from_biguint(Minus, One::one()),
908 Zero => Zero::zero(),
913 fn is_positive(&self) -> bool { self.sign == Plus }
916 fn is_negative(&self) -> bool { self.sign == Minus }
919 impl Add<BigInt, BigInt> for BigInt {
921 fn add(&self, other: &BigInt) -> BigInt {
922 match (self.sign, other.sign) {
923 (Zero, _) => other.clone(),
924 (_, Zero) => self.clone(),
925 (Plus, Plus) => BigInt::from_biguint(Plus, self.data + other.data),
926 (Plus, Minus) => self - (-*other),
927 (Minus, Plus) => other - (-*self),
928 (Minus, Minus) => -((-self) + (-*other))
933 impl Sub<BigInt, BigInt> for BigInt {
935 fn sub(&self, other: &BigInt) -> BigInt {
936 match (self.sign, other.sign) {
938 (_, Zero) => self.clone(),
939 (Plus, Plus) => match self.data.cmp(&other.data) {
940 Less => BigInt::from_biguint(Minus, other.data - self.data),
941 Greater => BigInt::from_biguint(Plus, self.data - other.data),
942 Equal => Zero::zero()
944 (Plus, Minus) => self + (-*other),
945 (Minus, Plus) => -((-self) + *other),
946 (Minus, Minus) => (-other) - (-*self)
951 impl Mul<BigInt, BigInt> for BigInt {
953 fn mul(&self, other: &BigInt) -> BigInt {
954 match (self.sign, other.sign) {
955 (Zero, _) | (_, Zero) => Zero::zero(),
956 (Plus, Plus) | (Minus, Minus) => {
957 BigInt::from_biguint(Plus, self.data * other.data)
959 (Plus, Minus) | (Minus, Plus) => {
960 BigInt::from_biguint(Minus, self.data * other.data)
966 impl Div<BigInt, BigInt> for BigInt {
968 fn div(&self, other: &BigInt) -> BigInt {
969 let (q, _) = self.div_rem(other);
974 impl Rem<BigInt, BigInt> for BigInt {
976 fn rem(&self, other: &BigInt) -> BigInt {
977 let (_, r) = self.div_rem(other);
982 impl Neg<BigInt> for BigInt {
984 fn neg(&self) -> BigInt {
985 BigInt::from_biguint(self.sign.neg(), self.data.clone())
989 impl CheckedAdd for BigInt {
991 fn checked_add(&self, v: &BigInt) -> Option<BigInt> {
992 return Some(self.add(v));
996 impl CheckedSub for BigInt {
998 fn checked_sub(&self, v: &BigInt) -> Option<BigInt> {
999 return Some(self.sub(v));
1003 impl CheckedMul for BigInt {
1005 fn checked_mul(&self, v: &BigInt) -> Option<BigInt> {
1006 return Some(self.mul(v));
1010 impl CheckedDiv for BigInt {
1012 fn checked_div(&self, v: &BigInt) -> Option<BigInt> {
1016 return Some(self.div(v));
1021 impl Integer for BigInt {
1023 fn div_rem(&self, other: &BigInt) -> (BigInt, BigInt) {
1024 // r.sign == self.sign
1025 let (d_ui, r_ui) = self.data.div_mod_floor(&other.data);
1026 let d = BigInt::from_biguint(Plus, d_ui);
1027 let r = BigInt::from_biguint(Plus, r_ui);
1028 match (self.sign, other.sign) {
1029 (_, Zero) => fail!(),
1030 (Plus, Plus) | (Zero, Plus) => ( d, r),
1031 (Plus, Minus) | (Zero, Minus) => (-d, r),
1032 (Minus, Plus) => (-d, -r),
1033 (Minus, Minus) => ( d, -r)
1038 fn div_floor(&self, other: &BigInt) -> BigInt {
1039 let (d, _) = self.div_mod_floor(other);
1044 fn mod_floor(&self, other: &BigInt) -> BigInt {
1045 let (_, m) = self.div_mod_floor(other);
1049 fn div_mod_floor(&self, other: &BigInt) -> (BigInt, BigInt) {
1050 // m.sign == other.sign
1051 let (d_ui, m_ui) = self.data.div_rem(&other.data);
1052 let d = BigInt::from_biguint(Plus, d_ui);
1053 let m = BigInt::from_biguint(Plus, m_ui);
1054 match (self.sign, other.sign) {
1055 (_, Zero) => fail!(),
1056 (Plus, Plus) | (Zero, Plus) => (d, m),
1057 (Plus, Minus) | (Zero, Minus) => if m.is_zero() {
1060 (-d - One::one(), m + *other)
1062 (Minus, Plus) => if m.is_zero() {
1065 (-d - One::one(), other - m)
1067 (Minus, Minus) => (d, -m)
1072 * Calculates the Greatest Common Divisor (GCD) of the number and `other`
1074 * The result is always positive
1077 fn gcd(&self, other: &BigInt) -> BigInt {
1078 BigInt::from_biguint(Plus, self.data.gcd(&other.data))
1082 * Calculates the Lowest Common Multiple (LCM) of the number and `other`
1085 fn lcm(&self, other: &BigInt) -> BigInt {
1086 BigInt::from_biguint(Plus, self.data.lcm(&other.data))
1089 /// Returns `true` if the number can be divided by `other` without leaving a remainder
1091 fn divides(&self, other: &BigInt) -> bool { self.data.divides(&other.data) }
1093 /// Returns `true` if the number is divisible by `2`
1095 fn is_even(&self) -> bool { self.data.is_even() }
1097 /// Returns `true` if the number is not divisible by `2`
1099 fn is_odd(&self) -> bool { self.data.is_odd() }
1102 impl ToPrimitive for BigInt {
1104 fn to_i64(&self) -> Option<i64> {
1106 Plus => self.data.to_i64(),
1109 self.data.to_u64().and_then(|n| {
1110 let m: u64 = 1 << 63;
1124 fn to_u64(&self) -> Option<u64> {
1126 Plus => self.data.to_u64(),
1133 impl FromPrimitive for BigInt {
1135 fn from_i64(n: i64) -> Option<BigInt> {
1137 FromPrimitive::from_u64(n as u64).and_then(|n| {
1138 Some(BigInt::from_biguint(Plus, n))
1141 FromPrimitive::from_u64(u64::MAX - (n as u64) + 1).and_then(
1143 Some(BigInt::from_biguint(Minus, n))
1151 fn from_u64(n: u64) -> Option<BigInt> {
1155 FromPrimitive::from_u64(n).and_then(|n| {
1156 Some(BigInt::from_biguint(Plus, n))
1162 /// A generic trait for converting a value to a `BigInt`.
1163 pub trait ToBigInt {
1164 /// Converts the value of `self` to a `BigInt`.
1165 fn to_bigint(&self) -> Option<BigInt>;
1168 impl ToBigInt for BigInt {
1170 fn to_bigint(&self) -> Option<BigInt> {
1175 impl ToBigInt for BigUint {
1177 fn to_bigint(&self) -> Option<BigInt> {
1181 Some(BigInt { sign: Plus, data: self.clone() })
1186 macro_rules! impl_to_bigint(
1187 ($T:ty, $from_ty:path) => {
1188 impl ToBigInt for $T {
1190 fn to_bigint(&self) -> Option<BigInt> {
1197 impl_to_bigint!(int, FromPrimitive::from_int)
1198 impl_to_bigint!(i8, FromPrimitive::from_i8)
1199 impl_to_bigint!(i16, FromPrimitive::from_i16)
1200 impl_to_bigint!(i32, FromPrimitive::from_i32)
1201 impl_to_bigint!(i64, FromPrimitive::from_i64)
1202 impl_to_bigint!(uint, FromPrimitive::from_uint)
1203 impl_to_bigint!(u8, FromPrimitive::from_u8)
1204 impl_to_bigint!(u16, FromPrimitive::from_u16)
1205 impl_to_bigint!(u32, FromPrimitive::from_u32)
1206 impl_to_bigint!(u64, FromPrimitive::from_u64)
1208 impl ToStrRadix for BigInt {
1210 fn to_str_radix(&self, radix: uint) -> String {
1212 Plus => self.data.to_str_radix(radix),
1213 Zero => "0".to_string(),
1214 Minus => format!("-{}", self.data.to_str_radix(radix)),
1219 impl FromStrRadix for BigInt {
1220 /// Creates and initializes a BigInt.
1222 fn from_str_radix(s: &str, radix: uint) -> Option<BigInt> {
1223 BigInt::parse_bytes(s.as_bytes(), radix)
1227 pub trait RandBigInt {
1228 /// Generate a random `BigUint` of the given bit size.
1229 fn gen_biguint(&mut self, bit_size: uint) -> BigUint;
1231 /// Generate a random BigInt of the given bit size.
1232 fn gen_bigint(&mut self, bit_size: uint) -> BigInt;
1234 /// Generate a random `BigUint` less than the given bound. Fails
1235 /// when the bound is zero.
1236 fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint;
1238 /// Generate a random `BigUint` within the given range. The lower
1239 /// bound is inclusive; the upper bound is exclusive. Fails when
1240 /// the upper bound is not greater than the lower bound.
1241 fn gen_biguint_range(&mut self, lbound: &BigUint, ubound: &BigUint) -> BigUint;
1243 /// Generate a random `BigInt` within the given range. The lower
1244 /// bound is inclusive; the upper bound is exclusive. Fails when
1245 /// the upper bound is not greater than the lower bound.
1246 fn gen_bigint_range(&mut self, lbound: &BigInt, ubound: &BigInt) -> BigInt;
1249 impl<R: Rng> RandBigInt for R {
1250 fn gen_biguint(&mut self, bit_size: uint) -> BigUint {
1251 let (digits, rem) = bit_size.div_rem(&BigDigit::bits);
1252 let mut data = Vec::with_capacity(digits+1);
1253 for _ in range(0, digits) {
1254 data.push(self.gen());
1257 let final_digit: BigDigit = self.gen();
1258 data.push(final_digit >> (BigDigit::bits - rem));
1263 fn gen_bigint(&mut self, bit_size: uint) -> BigInt {
1264 // Generate a random BigUint...
1265 let biguint = self.gen_biguint(bit_size);
1266 // ...and then randomly assign it a Sign...
1267 let sign = if biguint.is_zero() {
1268 // ...except that if the BigUint is zero, we need to try
1269 // again with probability 0.5. This is because otherwise,
1270 // the probability of generating a zero BigInt would be
1271 // double that of any other number.
1273 return self.gen_bigint(bit_size);
1277 } else if self.gen() {
1282 BigInt::from_biguint(sign, biguint)
1285 fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint {
1286 assert!(!bound.is_zero());
1287 let bits = bound.bits();
1289 let n = self.gen_biguint(bits);
1290 if n < *bound { return n; }
1294 fn gen_biguint_range(&mut self,
1298 assert!(*lbound < *ubound);
1299 return *lbound + self.gen_biguint_below(&(*ubound - *lbound));
1302 fn gen_bigint_range(&mut self,
1306 assert!(*lbound < *ubound);
1307 let delta = (*ubound - *lbound).to_biguint().unwrap();
1308 return *lbound + self.gen_biguint_below(&delta).to_bigint().unwrap();
1313 /// Creates and initializes a BigInt.
1315 /// The digits are be in base 2^32.
1317 pub fn new(sign: Sign, digits: Vec<BigDigit>) -> BigInt {
1318 BigInt::from_biguint(sign, BigUint::new(digits))
1321 /// Creates and initializes a `BigInt`.
1323 /// The digits are be in base 2^32.
1325 pub fn from_biguint(sign: Sign, data: BigUint) -> BigInt {
1326 if sign == Zero || data.is_zero() {
1327 return BigInt { sign: Zero, data: Zero::zero() };
1329 BigInt { sign: sign, data: data }
1332 /// Creates and initializes a `BigInt`.
1334 pub fn from_slice(sign: Sign, slice: &[BigDigit]) -> BigInt {
1335 BigInt::from_biguint(sign, BigUint::from_slice(slice))
1338 /// Creates and initializes a `BigInt`.
1339 pub fn parse_bytes(buf: &[u8], radix: uint) -> Option<BigInt> {
1340 if buf.is_empty() { return None; }
1341 let mut sign = Plus;
1343 if buf[0] == ('-' as u8) {
1347 return BigUint::parse_bytes(buf.slice(start, buf.len()), radix)
1348 .map(|bu| BigInt::from_biguint(sign, bu));
1351 /// Converts this `BigInt` into a `BigUint`, if it's not negative.
1353 pub fn to_biguint(&self) -> Option<BigUint> {
1355 Plus => Some(self.data.clone()),
1356 Zero => Some(Zero::zero()),
1365 use super::{BigDigit, BigUint, ToBigUint};
1366 use super::{Plus, BigInt, RandBigInt, ToBigInt};
1368 use std::cmp::{Less, Equal, Greater};
1369 use std::from_str::FromStr;
1371 use std::num::{Zero, One, FromStrRadix, ToStrRadix};
1372 use std::num::{ToPrimitive, FromPrimitive};
1373 use std::num::CheckedDiv;
1374 use std::rand::task_rng;
1378 fn test_from_slice() {
1379 fn check(slice: &[BigDigit], data: &[BigDigit]) {
1380 assert!(data == BigUint::from_slice(slice).data.as_slice());
1383 check([0, 0, 0], []);
1384 check([1, 2, 0, 0], [1, 2]);
1385 check([0, 0, 1, 2], [0, 0, 1, 2]);
1386 check([0, 0, 1, 2, 0, 0], [0, 0, 1, 2]);
1392 let data: Vec<BigUint> = [ &[], &[1], &[2], &[-1], &[0, 1], &[2, 1], &[1, 1, 1] ]
1393 .iter().map(|v| BigUint::from_slice(*v)).collect();
1394 for (i, ni) in data.iter().enumerate() {
1395 for (j0, nj) in data.slice(i, data.len()).iter().enumerate() {
1398 assert_eq!(ni.cmp(nj), Equal);
1399 assert_eq!(nj.cmp(ni), Equal);
1401 assert!(!(ni != nj));
1404 assert!(!(ni < nj));
1405 assert!(!(ni > nj));
1407 assert_eq!(ni.cmp(nj), Less);
1408 assert_eq!(nj.cmp(ni), Greater);
1410 assert!(!(ni == nj));
1414 assert!(!(ni >= nj));
1416 assert!(!(ni > nj));
1418 assert!(!(nj <= ni));
1420 assert!(!(nj < ni));
1429 fn check(left: &[BigDigit],
1431 expected: &[BigDigit]) {
1432 assert_eq!(BigUint::from_slice(left) & BigUint::from_slice(right),
1433 BigUint::from_slice(expected));
1436 check([268, 482, 17],
1443 fn check(left: &[BigDigit],
1445 expected: &[BigDigit]) {
1446 assert_eq!(BigUint::from_slice(left) | BigUint::from_slice(right),
1447 BigUint::from_slice(expected));
1450 check([268, 482, 17],
1457 fn check(left: &[BigDigit],
1459 expected: &[BigDigit]) {
1460 assert_eq!(BigUint::from_slice(left) ^ BigUint::from_slice(right),
1461 BigUint::from_slice(expected));
1464 check([268, 482, 17],
1471 fn check(s: &str, shift: uint, ans: &str) {
1472 let opt_biguint: Option<BigUint> = FromStrRadix::from_str_radix(s, 16);
1473 let bu = (opt_biguint.unwrap() << shift).to_str_radix(16);
1474 assert_eq!(bu.as_slice(), ans);
1586 check("88887777666655554444333322221111", 16,
1587 "888877776666555544443333222211110000");
1592 fn check(s: &str, shift: uint, ans: &str) {
1593 let opt_biguint: Option<BigUint> =
1594 FromStrRadix::from_str_radix(s, 16);
1595 let bu = (opt_biguint.unwrap() >> shift).to_str_radix(16);
1596 assert_eq!(bu.as_slice(), ans);
1704 check("888877776666555544443333222211110000", 16,
1705 "88887777666655554444333322221111");
1708 // `DoubleBigDigit` size dependent
1710 fn test_convert_i64() {
1711 fn check(b1: BigUint, i: i64) {
1712 let b2: BigUint = FromPrimitive::from_i64(i).unwrap();
1714 assert!(b1.to_i64().unwrap() == i);
1717 check(Zero::zero(), 0);
1718 check(One::one(), 1);
1719 check(i64::MAX.to_biguint().unwrap(), i64::MAX);
1721 check(BigUint::new(vec!( )), 0);
1722 check(BigUint::new(vec!( 1 )), (1 << (0*BigDigit::bits)));
1723 check(BigUint::new(vec!(-1 )), (1 << (1*BigDigit::bits)) - 1);
1724 check(BigUint::new(vec!( 0, 1 )), (1 << (1*BigDigit::bits)));
1725 check(BigUint::new(vec!(-1, -1 >> 1)), i64::MAX);
1727 assert_eq!(i64::MIN.to_biguint(), None);
1728 assert_eq!(BigUint::new(vec!(-1, -1 )).to_i64(), None);
1729 assert_eq!(BigUint::new(vec!( 0, 0, 1)).to_i64(), None);
1730 assert_eq!(BigUint::new(vec!(-1, -1, -1)).to_i64(), None);
1733 // `DoubleBigDigit` size dependent
1735 fn test_convert_u64() {
1736 fn check(b1: BigUint, u: u64) {
1737 let b2: BigUint = FromPrimitive::from_u64(u).unwrap();
1739 assert!(b1.to_u64().unwrap() == u);
1742 check(Zero::zero(), 0);
1743 check(One::one(), 1);
1744 check(u64::MIN.to_biguint().unwrap(), u64::MIN);
1745 check(u64::MAX.to_biguint().unwrap(), u64::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)), u64::MAX);
1753 assert_eq!(BigUint::new(vec!( 0, 0, 1)).to_u64(), None);
1754 assert_eq!(BigUint::new(vec!(-1, -1, -1)).to_u64(), None);
1758 fn test_convert_to_bigint() {
1759 fn check(n: BigUint, ans: BigInt) {
1760 assert_eq!(n.to_bigint().unwrap(), ans);
1761 assert_eq!(n.to_bigint().unwrap().to_biguint().unwrap(), n);
1763 check(Zero::zero(), Zero::zero());
1764 check(BigUint::new(vec!(1,2,3)),
1765 BigInt::from_biguint(Plus, BigUint::new(vec!(1,2,3))));
1768 static sum_triples: &'static [(&'static [BigDigit],
1769 &'static [BigDigit],
1770 &'static [BigDigit])] = &[
1772 (&[], &[ 1], &[ 1]),
1773 (&[ 1], &[ 1], &[ 2]),
1774 (&[ 1], &[ 1, 1], &[ 2, 1]),
1775 (&[ 1], &[-1], &[ 0, 1]),
1776 (&[ 1], &[-1, -1], &[ 0, 0, 1]),
1777 (&[-1, -1], &[-1, -1], &[-2, -1, 1]),
1778 (&[ 1, 1, 1], &[-1, -1], &[ 0, 1, 2]),
1779 (&[ 2, 2, 1], &[-1, -2], &[ 1, 1, 2])
1784 for elm in sum_triples.iter() {
1785 let (a_vec, b_vec, c_vec) = *elm;
1786 let a = BigUint::from_slice(a_vec);
1787 let b = BigUint::from_slice(b_vec);
1788 let c = BigUint::from_slice(c_vec);
1790 assert!(a + b == c);
1791 assert!(b + a == c);
1797 for elm in sum_triples.iter() {
1798 let (a_vec, b_vec, c_vec) = *elm;
1799 let a = BigUint::from_slice(a_vec);
1800 let b = BigUint::from_slice(b_vec);
1801 let c = BigUint::from_slice(c_vec);
1803 assert!(c - a == b);
1804 assert!(c - b == a);
1810 fn test_sub_fail_on_underflow() {
1811 let (a, b) : (BigUint, BigUint) = (Zero::zero(), One::one());
1815 static mul_triples: &'static [(&'static [BigDigit],
1816 &'static [BigDigit],
1817 &'static [BigDigit])] = &[
1821 (&[ 1], &[ 1], &[1]),
1822 (&[ 2], &[ 3], &[ 6]),
1823 (&[ 1], &[ 1, 1, 1], &[1, 1, 1]),
1824 (&[ 1, 2, 3], &[ 3], &[ 3, 6, 9]),
1825 (&[ 1, 1, 1], &[-1], &[-1, -1, -1]),
1826 (&[ 1, 2, 3], &[-1], &[-1, -2, -2, 2]),
1827 (&[ 1, 2, 3, 4], &[-1], &[-1, -2, -2, -2, 3]),
1828 (&[-1], &[-1], &[ 1, -2]),
1829 (&[-1, -1], &[-1], &[ 1, -1, -2]),
1830 (&[-1, -1, -1], &[-1], &[ 1, -1, -1, -2]),
1831 (&[-1, -1, -1, -1], &[-1], &[ 1, -1, -1, -1, -2]),
1832 (&[-1/2 + 1], &[ 2], &[ 0, 1]),
1833 (&[0, -1/2 + 1], &[ 2], &[ 0, 0, 1]),
1834 (&[ 1, 2], &[ 1, 2, 3], &[1, 4, 7, 6]),
1835 (&[-1, -1], &[-1, -1, -1], &[1, 0, -1, -2, -1]),
1836 (&[-1, -1, -1], &[-1, -1, -1, -1], &[1, 0, 0, -1, -2, -1, -1]),
1837 (&[ 0, 0, 1], &[ 1, 2, 3], &[0, 0, 1, 2, 3]),
1838 (&[ 0, 0, 1], &[ 0, 0, 0, 1], &[0, 0, 0, 0, 0, 1])
1841 static div_rem_quadruples: &'static [(&'static [BigDigit],
1842 &'static [BigDigit],
1843 &'static [BigDigit],
1844 &'static [BigDigit])]
1846 (&[ 1], &[ 2], &[], &[1]),
1847 (&[ 1, 1], &[ 2], &[-1/2+1], &[1]),
1848 (&[ 1, 1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
1849 (&[ 0, 1], &[-1], &[1], &[1]),
1850 (&[-1, -1], &[-2], &[2, 1], &[3])
1855 for elm in mul_triples.iter() {
1856 let (a_vec, b_vec, c_vec) = *elm;
1857 let a = BigUint::from_slice(a_vec);
1858 let b = BigUint::from_slice(b_vec);
1859 let c = BigUint::from_slice(c_vec);
1861 assert!(a * b == c);
1862 assert!(b * a == c);
1865 for elm in div_rem_quadruples.iter() {
1866 let (a_vec, b_vec, c_vec, d_vec) = *elm;
1867 let a = BigUint::from_slice(a_vec);
1868 let b = BigUint::from_slice(b_vec);
1869 let c = BigUint::from_slice(c_vec);
1870 let d = BigUint::from_slice(d_vec);
1872 assert!(a == b * c + d);
1873 assert!(a == c * b + d);
1879 for elm in mul_triples.iter() {
1880 let (a_vec, b_vec, c_vec) = *elm;
1881 let a = BigUint::from_slice(a_vec);
1882 let b = BigUint::from_slice(b_vec);
1883 let c = BigUint::from_slice(c_vec);
1886 assert_eq!(c.div_rem(&a), (b.clone(), Zero::zero()));
1889 assert_eq!(c.div_rem(&b), (a.clone(), Zero::zero()));
1893 for elm in div_rem_quadruples.iter() {
1894 let (a_vec, b_vec, c_vec, d_vec) = *elm;
1895 let a = BigUint::from_slice(a_vec);
1896 let b = BigUint::from_slice(b_vec);
1897 let c = BigUint::from_slice(c_vec);
1898 let d = BigUint::from_slice(d_vec);
1900 if !b.is_zero() { assert!(a.div_rem(&b) == (c, d)); }
1905 fn test_checked_add() {
1906 for elm in sum_triples.iter() {
1907 let (aVec, bVec, cVec) = *elm;
1908 let a = BigUint::from_slice(aVec);
1909 let b = BigUint::from_slice(bVec);
1910 let c = BigUint::from_slice(cVec);
1912 assert!(a.checked_add(&b).unwrap() == c);
1913 assert!(b.checked_add(&a).unwrap() == c);
1918 fn test_checked_sub() {
1919 for elm in sum_triples.iter() {
1920 let (aVec, bVec, cVec) = *elm;
1921 let a = BigUint::from_slice(aVec);
1922 let b = BigUint::from_slice(bVec);
1923 let c = BigUint::from_slice(cVec);
1925 assert!(c.checked_sub(&a).unwrap() == b);
1926 assert!(c.checked_sub(&b).unwrap() == a);
1929 assert!(a.checked_sub(&c).is_none());
1932 assert!(b.checked_sub(&c).is_none());
1938 fn test_checked_mul() {
1939 for elm in mul_triples.iter() {
1940 let (aVec, bVec, cVec) = *elm;
1941 let a = BigUint::from_slice(aVec);
1942 let b = BigUint::from_slice(bVec);
1943 let c = BigUint::from_slice(cVec);
1945 assert!(a.checked_mul(&b).unwrap() == c);
1946 assert!(b.checked_mul(&a).unwrap() == c);
1949 for elm in div_rem_quadruples.iter() {
1950 let (aVec, bVec, cVec, dVec) = *elm;
1951 let a = BigUint::from_slice(aVec);
1952 let b = BigUint::from_slice(bVec);
1953 let c = BigUint::from_slice(cVec);
1954 let d = BigUint::from_slice(dVec);
1956 assert!(a == b.checked_mul(&c).unwrap() + d);
1957 assert!(a == c.checked_mul(&b).unwrap() + d);
1962 fn test_checked_div() {
1963 for elm in mul_triples.iter() {
1964 let (aVec, bVec, cVec) = *elm;
1965 let a = BigUint::from_slice(aVec);
1966 let b = BigUint::from_slice(bVec);
1967 let c = BigUint::from_slice(cVec);
1970 assert!(c.checked_div(&a).unwrap() == b);
1973 assert!(c.checked_div(&b).unwrap() == a);
1976 assert!(c.checked_div(&Zero::zero()).is_none());
1982 fn check(a: uint, b: uint, c: uint) {
1983 let big_a: BigUint = FromPrimitive::from_uint(a).unwrap();
1984 let big_b: BigUint = FromPrimitive::from_uint(b).unwrap();
1985 let big_c: BigUint = FromPrimitive::from_uint(c).unwrap();
1987 assert_eq!(big_a.gcd(&big_b), big_c);
1999 fn check(a: uint, b: uint, c: uint) {
2000 let big_a: BigUint = FromPrimitive::from_uint(a).unwrap();
2001 let big_b: BigUint = FromPrimitive::from_uint(b).unwrap();
2002 let big_c: BigUint = FromPrimitive::from_uint(c).unwrap();
2004 assert_eq!(big_a.lcm(&big_b), big_c);
2012 check(99, 17, 1683);
2017 let one: BigUint = FromStr::from_str("1").unwrap();
2018 let two: BigUint = FromStr::from_str("2").unwrap();
2019 let thousand: BigUint = FromStr::from_str("1000").unwrap();
2020 let big: BigUint = FromStr::from_str("1000000000000000000000").unwrap();
2021 let bigger: BigUint = FromStr::from_str("1000000000000000000001").unwrap();
2022 assert!(one.is_odd());
2023 assert!(two.is_even());
2024 assert!(thousand.is_even());
2025 assert!(big.is_even());
2026 assert!(bigger.is_odd());
2027 assert!((one << 64).is_even());
2028 assert!(((one << 64) + one).is_odd());
2031 fn to_str_pairs() -> Vec<(BigUint, Vec<(uint, String)>)> {
2032 let bits = BigDigit::bits;
2033 vec!(( Zero::zero(), vec!(
2034 (2, "0".to_string()), (3, "0".to_string())
2035 )), ( BigUint::from_slice([ 0xff ]), vec!(
2036 (2, "11111111".to_string()),
2037 (3, "100110".to_string()),
2038 (4, "3333".to_string()),
2039 (5, "2010".to_string()),
2040 (6, "1103".to_string()),
2041 (7, "513".to_string()),
2042 (8, "377".to_string()),
2043 (9, "313".to_string()),
2044 (10, "255".to_string()),
2045 (11, "212".to_string()),
2046 (12, "193".to_string()),
2047 (13, "168".to_string()),
2048 (14, "143".to_string()),
2049 (15, "120".to_string()),
2050 (16, "ff".to_string())
2051 )), ( BigUint::from_slice([ 0xfff ]), vec!(
2052 (2, "111111111111".to_string()),
2053 (4, "333333".to_string()),
2054 (16, "fff".to_string())
2055 )), ( BigUint::from_slice([ 1, 2 ]), vec!(
2057 format!("10{}1", "0".repeat(bits - 1))),
2059 format!("2{}1", "0".repeat(bits / 2 - 1))),
2061 32 => "8589934593".to_string(),
2062 16 => "131073".to_string(),
2066 format!("2{}1", "0".repeat(bits / 4 - 1)))
2067 )), ( BigUint::from_slice([ 1, 2, 3 ]), vec!(
2069 format!("11{}10{}1",
2070 "0".repeat(bits - 2),
2071 "0".repeat(bits - 1))),
2074 "0".repeat(bits / 2 - 1),
2075 "0".repeat(bits / 2 - 1))),
2077 32 => "55340232229718589441".to_string(),
2078 16 => "12885032961".to_string(),
2083 "0".repeat(bits / 4 - 1),
2084 "0".repeat(bits / 4 - 1)))
2089 fn test_to_str_radix() {
2090 let r = to_str_pairs();
2091 for num_pair in r.iter() {
2092 let &(ref n, ref rs) = num_pair;
2093 for str_pair in rs.iter() {
2094 let &(ref radix, ref str) = str_pair;
2095 assert_eq!(n.to_str_radix(*radix).as_slice(),
2102 fn test_from_str_radix() {
2103 let r = to_str_pairs();
2104 for num_pair in r.iter() {
2105 let &(ref n, ref rs) = num_pair;
2106 for str_pair in rs.iter() {
2107 let &(ref radix, ref str) = str_pair;
2109 &FromStrRadix::from_str_radix(str.as_slice(),
2114 let zed: Option<BigUint> = FromStrRadix::from_str_radix("Z", 10);
2115 assert_eq!(zed, None);
2116 let blank: Option<BigUint> = FromStrRadix::from_str_radix("_", 2);
2117 assert_eq!(blank, None);
2118 let minus_one: Option<BigUint> = FromStrRadix::from_str_radix("-1",
2120 assert_eq!(minus_one, None);
2125 fn factor(n: uint) -> BigUint {
2126 let mut f: BigUint = One::one();
2127 for i in range(2, n + 1) {
2128 // FIXME(#5992): assignment operator overloads
2129 // f *= FromPrimitive::from_uint(i);
2130 f = f * FromPrimitive::from_uint(i).unwrap();
2135 fn check(n: uint, s: &str) {
2137 let ans = match FromStrRadix::from_str_radix(s, 10) {
2138 Some(x) => x, None => fail!()
2144 check(10, "3628800");
2145 check(20, "2432902008176640000");
2146 check(30, "265252859812191058636308480000000");
2151 assert_eq!(BigUint::new(vec!(0,0,0,0)).bits(), 0);
2152 let n: BigUint = FromPrimitive::from_uint(0).unwrap();
2153 assert_eq!(n.bits(), 0);
2154 let n: BigUint = FromPrimitive::from_uint(1).unwrap();
2155 assert_eq!(n.bits(), 1);
2156 let n: BigUint = FromPrimitive::from_uint(3).unwrap();
2157 assert_eq!(n.bits(), 2);
2158 let n: BigUint = FromStrRadix::from_str_radix("4000000000", 16).unwrap();
2159 assert_eq!(n.bits(), 39);
2160 let one: BigUint = One::one();
2161 assert_eq!((one << 426).bits(), 427);
2166 let mut rng = task_rng();
2167 let _n: BigUint = rng.gen_biguint(137);
2168 assert!(rng.gen_biguint(0).is_zero());
2172 fn test_rand_range() {
2173 let mut rng = task_rng();
2175 for _ in range(0u, 10) {
2176 assert_eq!(rng.gen_bigint_range(&FromPrimitive::from_uint(236).unwrap(),
2177 &FromPrimitive::from_uint(237).unwrap()),
2178 FromPrimitive::from_uint(236).unwrap());
2181 let l = FromPrimitive::from_uint(403469000 + 2352).unwrap();
2182 let u = FromPrimitive::from_uint(403469000 + 3513).unwrap();
2183 for _ in range(0u, 1000) {
2184 let n: BigUint = rng.gen_biguint_below(&u);
2187 let n: BigUint = rng.gen_biguint_range(&l, &u);
2195 fn test_zero_rand_range() {
2196 task_rng().gen_biguint_range(&FromPrimitive::from_uint(54).unwrap(),
2197 &FromPrimitive::from_uint(54).unwrap());
2202 fn test_negative_rand_range() {
2203 let mut rng = task_rng();
2204 let l = FromPrimitive::from_uint(2352).unwrap();
2205 let u = FromPrimitive::from_uint(3513).unwrap();
2206 // Switching u and l should fail:
2207 let _n: BigUint = rng.gen_biguint_range(&u, &l);
2214 use super::{BigDigit, BigUint, ToBigUint};
2215 use super::{Sign, Minus, Zero, Plus, BigInt, RandBigInt, ToBigInt};
2217 use std::cmp::{Less, Equal, Greater};
2219 use std::num::CheckedDiv;
2220 use std::num::{Zero, One, FromStrRadix, ToStrRadix};
2221 use std::num::{ToPrimitive, FromPrimitive};
2222 use std::rand::task_rng;
2226 fn test_from_biguint() {
2227 fn check(inp_s: Sign, inp_n: uint, ans_s: Sign, ans_n: uint) {
2228 let inp = BigInt::from_biguint(inp_s, FromPrimitive::from_uint(inp_n).unwrap());
2229 let ans = BigInt { sign: ans_s, data: FromPrimitive::from_uint(ans_n).unwrap()};
2230 assert_eq!(inp, ans);
2232 check(Plus, 1, Plus, 1);
2233 check(Plus, 0, Zero, 0);
2234 check(Minus, 1, Minus, 1);
2235 check(Zero, 1, Zero, 0);
2240 let vs = [ &[2 as BigDigit], &[1, 1], &[2, 1], &[1, 1, 1] ];
2241 let mut nums = Vec::new();
2242 for s in vs.iter().rev() {
2243 nums.push(BigInt::from_slice(Minus, *s));
2245 nums.push(Zero::zero());
2246 nums.extend(vs.iter().map(|s| BigInt::from_slice(Plus, *s)));
2248 for (i, ni) in nums.iter().enumerate() {
2249 for (j0, nj) in nums.slice(i, nums.len()).iter().enumerate() {
2252 assert_eq!(ni.cmp(nj), Equal);
2253 assert_eq!(nj.cmp(ni), Equal);
2255 assert!(!(ni != nj));
2258 assert!(!(ni < nj));
2259 assert!(!(ni > nj));
2261 assert_eq!(ni.cmp(nj), Less);
2262 assert_eq!(nj.cmp(ni), Greater);
2264 assert!(!(ni == nj));
2268 assert!(!(ni >= nj));
2270 assert!(!(ni > nj));
2272 assert!(!(nj <= ni));
2274 assert!(!(nj < ni));
2282 fn test_convert_i64() {
2283 fn check(b1: BigInt, i: i64) {
2284 let b2: BigInt = FromPrimitive::from_i64(i).unwrap();
2286 assert!(b1.to_i64().unwrap() == i);
2289 check(Zero::zero(), 0);
2290 check(One::one(), 1);
2291 check(i64::MIN.to_bigint().unwrap(), i64::MIN);
2292 check(i64::MAX.to_bigint().unwrap(), i64::MAX);
2295 (i64::MAX as u64 + 1).to_bigint().unwrap().to_i64(),
2299 BigInt::from_biguint(Plus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_i64(),
2303 BigInt::from_biguint(Minus, BigUint::new(vec!(1,0,0,1<<(BigDigit::bits-1)))).to_i64(),
2307 BigInt::from_biguint(Minus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_i64(),
2312 fn test_convert_u64() {
2313 fn check(b1: BigInt, u: u64) {
2314 let b2: BigInt = FromPrimitive::from_u64(u).unwrap();
2316 assert!(b1.to_u64().unwrap() == u);
2319 check(Zero::zero(), 0);
2320 check(One::one(), 1);
2321 check(u64::MIN.to_bigint().unwrap(), u64::MIN);
2322 check(u64::MAX.to_bigint().unwrap(), u64::MAX);
2325 BigInt::from_biguint(Plus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_u64(),
2328 let max_value: BigUint = FromPrimitive::from_u64(u64::MAX).unwrap();
2329 assert_eq!(BigInt::from_biguint(Minus, max_value).to_u64(), None);
2330 assert_eq!(BigInt::from_biguint(Minus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_u64(), None);
2334 fn test_convert_to_biguint() {
2335 fn check(n: BigInt, ans_1: BigUint) {
2336 assert_eq!(n.to_biguint().unwrap(), ans_1);
2337 assert_eq!(n.to_biguint().unwrap().to_bigint().unwrap(), n);
2339 let zero: BigInt = Zero::zero();
2340 let unsigned_zero: BigUint = Zero::zero();
2341 let positive = BigInt::from_biguint(
2342 Plus, BigUint::new(vec!(1,2,3)));
2343 let negative = -positive;
2345 check(zero, unsigned_zero);
2346 check(positive, BigUint::new(vec!(1,2,3)));
2348 assert_eq!(negative.to_biguint(), None);
2351 static sum_triples: &'static [(&'static [BigDigit],
2352 &'static [BigDigit],
2353 &'static [BigDigit])] = &[
2355 (&[], &[ 1], &[ 1]),
2356 (&[ 1], &[ 1], &[ 2]),
2357 (&[ 1], &[ 1, 1], &[ 2, 1]),
2358 (&[ 1], &[-1], &[ 0, 1]),
2359 (&[ 1], &[-1, -1], &[ 0, 0, 1]),
2360 (&[-1, -1], &[-1, -1], &[-2, -1, 1]),
2361 (&[ 1, 1, 1], &[-1, -1], &[ 0, 1, 2]),
2362 (&[ 2, 2, 1], &[-1, -2], &[ 1, 1, 2])
2367 for elm in sum_triples.iter() {
2368 let (a_vec, b_vec, c_vec) = *elm;
2369 let a = BigInt::from_slice(Plus, a_vec);
2370 let b = BigInt::from_slice(Plus, b_vec);
2371 let c = BigInt::from_slice(Plus, c_vec);
2373 assert!(a + b == c);
2374 assert!(b + a == c);
2375 assert!(c + (-a) == b);
2376 assert!(c + (-b) == a);
2377 assert!(a + (-c) == (-b));
2378 assert!(b + (-c) == (-a));
2379 assert!((-a) + (-b) == (-c))
2380 assert!(a + (-a) == Zero::zero());
2386 for elm in sum_triples.iter() {
2387 let (a_vec, b_vec, c_vec) = *elm;
2388 let a = BigInt::from_slice(Plus, a_vec);
2389 let b = BigInt::from_slice(Plus, b_vec);
2390 let c = BigInt::from_slice(Plus, c_vec);
2392 assert!(c - a == b);
2393 assert!(c - b == a);
2394 assert!((-b) - a == (-c))
2395 assert!((-a) - b == (-c))
2396 assert!(b - (-a) == c);
2397 assert!(a - (-b) == c);
2398 assert!((-c) - (-a) == (-b));
2399 assert!(a - a == Zero::zero());
2403 static mul_triples: &'static [(&'static [BigDigit],
2404 &'static [BigDigit],
2405 &'static [BigDigit])] = &[
2409 (&[ 1], &[ 1], &[1]),
2410 (&[ 2], &[ 3], &[ 6]),
2411 (&[ 1], &[ 1, 1, 1], &[1, 1, 1]),
2412 (&[ 1, 2, 3], &[ 3], &[ 3, 6, 9]),
2413 (&[ 1, 1, 1], &[-1], &[-1, -1, -1]),
2414 (&[ 1, 2, 3], &[-1], &[-1, -2, -2, 2]),
2415 (&[ 1, 2, 3, 4], &[-1], &[-1, -2, -2, -2, 3]),
2416 (&[-1], &[-1], &[ 1, -2]),
2417 (&[-1, -1], &[-1], &[ 1, -1, -2]),
2418 (&[-1, -1, -1], &[-1], &[ 1, -1, -1, -2]),
2419 (&[-1, -1, -1, -1], &[-1], &[ 1, -1, -1, -1, -2]),
2420 (&[-1/2 + 1], &[ 2], &[ 0, 1]),
2421 (&[0, -1/2 + 1], &[ 2], &[ 0, 0, 1]),
2422 (&[ 1, 2], &[ 1, 2, 3], &[1, 4, 7, 6]),
2423 (&[-1, -1], &[-1, -1, -1], &[1, 0, -1, -2, -1]),
2424 (&[-1, -1, -1], &[-1, -1, -1, -1], &[1, 0, 0, -1, -2, -1, -1]),
2425 (&[ 0, 0, 1], &[ 1, 2, 3], &[0, 0, 1, 2, 3]),
2426 (&[ 0, 0, 1], &[ 0, 0, 0, 1], &[0, 0, 0, 0, 0, 1])
2429 static div_rem_quadruples: &'static [(&'static [BigDigit],
2430 &'static [BigDigit],
2431 &'static [BigDigit],
2432 &'static [BigDigit])]
2434 (&[ 1], &[ 2], &[], &[1]),
2435 (&[ 1, 1], &[ 2], &[-1/2+1], &[1]),
2436 (&[ 1, 1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
2437 (&[ 0, 1], &[-1], &[1], &[1]),
2438 (&[-1, -1], &[-2], &[2, 1], &[3])
2443 for elm in mul_triples.iter() {
2444 let (a_vec, b_vec, c_vec) = *elm;
2445 let a = BigInt::from_slice(Plus, a_vec);
2446 let b = BigInt::from_slice(Plus, b_vec);
2447 let c = BigInt::from_slice(Plus, c_vec);
2449 assert!(a * b == c);
2450 assert!(b * a == c);
2452 assert!((-a) * b == -c);
2453 assert!((-b) * a == -c);
2456 for elm in div_rem_quadruples.iter() {
2457 let (a_vec, b_vec, c_vec, d_vec) = *elm;
2458 let a = BigInt::from_slice(Plus, a_vec);
2459 let b = BigInt::from_slice(Plus, b_vec);
2460 let c = BigInt::from_slice(Plus, c_vec);
2461 let d = BigInt::from_slice(Plus, d_vec);
2463 assert!(a == b * c + d);
2464 assert!(a == c * b + d);
2469 fn test_div_mod_floor() {
2470 fn check_sub(a: &BigInt, b: &BigInt, ans_d: &BigInt, ans_m: &BigInt) {
2471 let (d, m) = a.div_mod_floor(b);
2473 assert_eq!(m.sign, b.sign);
2475 assert!(m.abs() <= b.abs());
2476 assert!(*a == b * d + m);
2477 assert!(d == *ans_d);
2478 assert!(m == *ans_m);
2481 fn check(a: &BigInt, b: &BigInt, d: &BigInt, m: &BigInt) {
2483 check_sub(a, b, d, m);
2484 check_sub(a, &b.neg(), &d.neg(), m);
2485 check_sub(&a.neg(), b, &d.neg(), m);
2486 check_sub(&a.neg(), &b.neg(), d, m);
2488 check_sub(a, b, d, m);
2489 check_sub(a, &b.neg(), &(d.neg() - One::one()), &(m - *b));
2490 check_sub(&a.neg(), b, &(d.neg() - One::one()), &(b - *m));
2491 check_sub(&a.neg(), &b.neg(), d, &m.neg());
2495 for elm in mul_triples.iter() {
2496 let (a_vec, b_vec, c_vec) = *elm;
2497 let a = BigInt::from_slice(Plus, a_vec);
2498 let b = BigInt::from_slice(Plus, b_vec);
2499 let c = BigInt::from_slice(Plus, c_vec);
2501 if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
2502 if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
2505 for elm in div_rem_quadruples.iter() {
2506 let (a_vec, b_vec, c_vec, d_vec) = *elm;
2507 let a = BigInt::from_slice(Plus, a_vec);
2508 let b = BigInt::from_slice(Plus, b_vec);
2509 let c = BigInt::from_slice(Plus, c_vec);
2510 let d = BigInt::from_slice(Plus, d_vec);
2513 check(&a, &b, &c, &d);
2521 fn check_sub(a: &BigInt, b: &BigInt, ans_q: &BigInt, ans_r: &BigInt) {
2522 let (q, r) = a.div_rem(b);
2524 assert_eq!(r.sign, a.sign);
2526 assert!(r.abs() <= b.abs());
2527 assert!(*a == b * q + r);
2528 assert!(q == *ans_q);
2529 assert!(r == *ans_r);
2532 fn check(a: &BigInt, b: &BigInt, q: &BigInt, r: &BigInt) {
2533 check_sub(a, b, q, r);
2534 check_sub(a, &b.neg(), &q.neg(), r);
2535 check_sub(&a.neg(), b, &q.neg(), &r.neg());
2536 check_sub(&a.neg(), &b.neg(), q, &r.neg());
2538 for elm in mul_triples.iter() {
2539 let (a_vec, b_vec, c_vec) = *elm;
2540 let a = BigInt::from_slice(Plus, a_vec);
2541 let b = BigInt::from_slice(Plus, b_vec);
2542 let c = BigInt::from_slice(Plus, c_vec);
2544 if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
2545 if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
2548 for elm in div_rem_quadruples.iter() {
2549 let (a_vec, b_vec, c_vec, d_vec) = *elm;
2550 let a = BigInt::from_slice(Plus, a_vec);
2551 let b = BigInt::from_slice(Plus, b_vec);
2552 let c = BigInt::from_slice(Plus, c_vec);
2553 let d = BigInt::from_slice(Plus, d_vec);
2556 check(&a, &b, &c, &d);
2562 fn test_checked_add() {
2563 for elm in sum_triples.iter() {
2564 let (aVec, bVec, cVec) = *elm;
2565 let a = BigInt::from_slice(Plus, aVec);
2566 let b = BigInt::from_slice(Plus, bVec);
2567 let c = BigInt::from_slice(Plus, cVec);
2569 assert!(a.checked_add(&b).unwrap() == c);
2570 assert!(b.checked_add(&a).unwrap() == c);
2571 assert!(c.checked_add(&(-a)).unwrap() == b);
2572 assert!(c.checked_add(&(-b)).unwrap() == a);
2573 assert!(a.checked_add(&(-c)).unwrap() == (-b));
2574 assert!(b.checked_add(&(-c)).unwrap() == (-a));
2575 assert!((-a).checked_add(&(-b)).unwrap() == (-c))
2576 assert!(a.checked_add(&(-a)).unwrap() == Zero::zero());
2581 fn test_checked_sub() {
2582 for elm in sum_triples.iter() {
2583 let (aVec, bVec, cVec) = *elm;
2584 let a = BigInt::from_slice(Plus, aVec);
2585 let b = BigInt::from_slice(Plus, bVec);
2586 let c = BigInt::from_slice(Plus, cVec);
2588 assert!(c.checked_sub(&a).unwrap() == b);
2589 assert!(c.checked_sub(&b).unwrap() == a);
2590 assert!((-b).checked_sub(&a).unwrap() == (-c))
2591 assert!((-a).checked_sub(&b).unwrap() == (-c))
2592 assert!(b.checked_sub(&(-a)).unwrap() == c);
2593 assert!(a.checked_sub(&(-b)).unwrap() == c);
2594 assert!((-c).checked_sub(&(-a)).unwrap() == (-b));
2595 assert!(a.checked_sub(&a).unwrap() == Zero::zero());
2600 fn test_checked_mul() {
2601 for elm in mul_triples.iter() {
2602 let (aVec, bVec, cVec) = *elm;
2603 let a = BigInt::from_slice(Plus, aVec);
2604 let b = BigInt::from_slice(Plus, bVec);
2605 let c = BigInt::from_slice(Plus, cVec);
2607 assert!(a.checked_mul(&b).unwrap() == c);
2608 assert!(b.checked_mul(&a).unwrap() == c);
2610 assert!((-a).checked_mul(&b).unwrap() == -c);
2611 assert!((-b).checked_mul(&a).unwrap() == -c);
2614 for elm in div_rem_quadruples.iter() {
2615 let (aVec, bVec, cVec, dVec) = *elm;
2616 let a = BigInt::from_slice(Plus, aVec);
2617 let b = BigInt::from_slice(Plus, bVec);
2618 let c = BigInt::from_slice(Plus, cVec);
2619 let d = BigInt::from_slice(Plus, dVec);
2621 assert!(a == b.checked_mul(&c).unwrap() + d);
2622 assert!(a == c.checked_mul(&b).unwrap() + d);
2626 fn test_checked_div() {
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);
2634 assert!(c.checked_div(&a).unwrap() == b);
2635 assert!((-c).checked_div(&(-a)).unwrap() == b);
2636 assert!((-c).checked_div(&a).unwrap() == -b);
2639 assert!(c.checked_div(&b).unwrap() == a);
2640 assert!((-c).checked_div(&(-b)).unwrap() == a);
2641 assert!((-c).checked_div(&b).unwrap() == -a);
2644 assert!(c.checked_div(&Zero::zero()).is_none());
2645 assert!((-c).checked_div(&Zero::zero()).is_none());
2651 fn check(a: int, b: int, c: int) {
2652 let big_a: BigInt = FromPrimitive::from_int(a).unwrap();
2653 let big_b: BigInt = FromPrimitive::from_int(b).unwrap();
2654 let big_c: BigInt = FromPrimitive::from_int(c).unwrap();
2656 assert_eq!(big_a.gcd(&big_b), big_c);
2671 fn check(a: int, b: int, c: int) {
2672 let big_a: BigInt = FromPrimitive::from_int(a).unwrap();
2673 let big_b: BigInt = FromPrimitive::from_int(b).unwrap();
2674 let big_c: BigInt = FromPrimitive::from_int(c).unwrap();
2676 assert_eq!(big_a.lcm(&big_b), big_c);
2691 let zero: BigInt = Zero::zero();
2692 let one: BigInt = One::one();
2693 assert_eq!((-one).abs_sub(&one), zero);
2694 let one: BigInt = One::one();
2695 let zero: BigInt = Zero::zero();
2696 assert_eq!(one.abs_sub(&one), zero);
2697 let one: BigInt = One::one();
2698 let zero: BigInt = Zero::zero();
2699 assert_eq!(one.abs_sub(&zero), one);
2700 let one: BigInt = One::one();
2701 let two: BigInt = FromPrimitive::from_int(2).unwrap();
2702 assert_eq!(one.abs_sub(&-one), two);
2706 fn test_to_str_radix() {
2707 fn check(n: int, ans: &str) {
2708 let n: BigInt = FromPrimitive::from_int(n).unwrap();
2709 assert!(ans == n.to_str_radix(10).as_slice());
2720 fn test_from_str_radix() {
2721 fn check(s: &str, ans: Option<int>) {
2722 let ans = ans.map(|n| {
2723 let x: BigInt = FromPrimitive::from_int(n).unwrap();
2726 assert_eq!(FromStrRadix::from_str_radix(s, 10), ans);
2728 check("10", Some(10));
2729 check("1", Some(1));
2730 check("0", Some(0));
2731 check("-1", Some(-1));
2732 check("-10", Some(-10));
2736 // issue 10522, this hit an edge case that caused it to
2737 // attempt to allocate a vector of size (-1u) == huge.
2739 from_str(format!("1{}", "0".repeat(36)).as_slice()).unwrap();
2740 let _y = x.to_string();
2745 assert!(-BigInt::new(Plus, vec!(1, 1, 1)) ==
2746 BigInt::new(Minus, vec!(1, 1, 1)));
2747 assert!(-BigInt::new(Minus, vec!(1, 1, 1)) ==
2748 BigInt::new(Plus, vec!(1, 1, 1)));
2749 let zero: BigInt = Zero::zero();
2750 assert_eq!(-zero, zero);
2755 let mut rng = task_rng();
2756 let _n: BigInt = rng.gen_bigint(137);
2757 assert!(rng.gen_bigint(0).is_zero());
2761 fn test_rand_range() {
2762 let mut rng = task_rng();
2764 for _ in range(0u, 10) {
2765 assert_eq!(rng.gen_bigint_range(&FromPrimitive::from_uint(236).unwrap(),
2766 &FromPrimitive::from_uint(237).unwrap()),
2767 FromPrimitive::from_uint(236).unwrap());
2770 fn check(l: BigInt, u: BigInt) {
2771 let mut rng = task_rng();
2772 for _ in range(0u, 1000) {
2773 let n: BigInt = rng.gen_bigint_range(&l, &u);
2778 let l: BigInt = FromPrimitive::from_uint(403469000 + 2352).unwrap();
2779 let u: BigInt = FromPrimitive::from_uint(403469000 + 3513).unwrap();
2780 check( l.clone(), u.clone());
2781 check(-l.clone(), u.clone());
2782 check(-u.clone(), -l.clone());
2787 fn test_zero_rand_range() {
2788 task_rng().gen_bigint_range(&FromPrimitive::from_int(54).unwrap(),
2789 &FromPrimitive::from_int(54).unwrap());
2794 fn test_negative_rand_range() {
2795 let mut rng = task_rng();
2796 let l = FromPrimitive::from_uint(2352).unwrap();
2797 let u = FromPrimitive::from_uint(3513).unwrap();
2798 // Switching u and l should fail:
2799 let _n: BigInt = rng.gen_bigint_range(&u, &l);
2806 use self::test::Bencher;
2809 use std::mem::replace;
2810 use std::num::{FromPrimitive, Zero, One};
2812 fn factorial(n: uint) -> BigUint {
2813 let mut f: BigUint = One::one();
2814 for i in iter::range_inclusive(1, n) {
2815 f = f * FromPrimitive::from_uint(i).unwrap();
2820 fn fib(n: uint) -> BigUint {
2821 let mut f0: BigUint = Zero::zero();
2822 let mut f1: BigUint = One::one();
2823 for _ in range(0, n) {
2825 f0 = replace(&mut f1, f2);
2831 fn factorial_100(b: &mut Bencher) {
2838 fn fib_100(b: &mut Bencher) {
2845 fn to_string(b: &mut Bencher) {
2846 let fac = factorial(100);
2857 fn shr(b: &mut Bencher) {
2858 let n = { let one : BigUint = One::one(); one << 1000 };
2860 let mut m = n.clone();
2861 for _ in range(0u, 10) {