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`.
22 use std::default::Default;
24 use std::from_str::FromStr;
25 use std::num::CheckedDiv;
26 use std::num::{Bitwise, ToPrimitive, FromPrimitive};
27 use std::num::{Zero, One, ToStrRadix, FromStrRadix};
29 use std::string::String;
34 A `BigDigit` is a `BigUint`'s composing element.
36 pub type BigDigit = u32;
39 A `DoubleBigDigit` is the internal type used to do the computations. Its
40 size is the double of the size of `BigDigit`.
42 pub type DoubleBigDigit = u64;
44 pub static ZERO_BIG_DIGIT: BigDigit = 0;
45 static ZERO_VEC: [BigDigit, ..1] = [ZERO_BIG_DIGIT];
49 use super::DoubleBigDigit;
51 // `DoubleBigDigit` size dependent
52 pub static bits: uint = 32;
54 pub static base: DoubleBigDigit = 1 << bits;
55 static lo_mask: DoubleBigDigit = (-1 as DoubleBigDigit) >> bits;
58 fn get_hi(n: DoubleBigDigit) -> BigDigit { (n >> bits) as BigDigit }
60 fn get_lo(n: DoubleBigDigit) -> BigDigit { (n & lo_mask) as BigDigit }
62 /// Split one `DoubleBigDigit` into two `BigDigit`s.
64 pub fn from_doublebigdigit(n: DoubleBigDigit) -> (BigDigit, BigDigit) {
65 (get_hi(n), get_lo(n))
68 /// Join two `BigDigit`s into one `DoubleBigDigit`
70 pub fn to_doublebigdigit(hi: BigDigit, lo: BigDigit) -> DoubleBigDigit {
71 (lo as DoubleBigDigit) | ((hi as DoubleBigDigit) << bits)
76 A big unsigned integer type.
78 A `BigUint`-typed value `BigUint { data: vec!(a, b, c) }` represents a number
79 `(a + b * BigDigit::base + c * BigDigit::base^2)`.
86 impl PartialEq for BigUint {
88 fn eq(&self, other: &BigUint) -> bool {
89 match self.cmp(other) { Equal => true, _ => false }
92 impl Eq for BigUint {}
94 impl PartialOrd for BigUint {
96 fn lt(&self, other: &BigUint) -> bool {
97 match self.cmp(other) { Less => true, _ => false}
101 impl Ord for BigUint {
103 fn cmp(&self, other: &BigUint) -> Ordering {
104 let (s_len, o_len) = (self.data.len(), other.data.len());
105 if s_len < o_len { return Less; }
106 if s_len > o_len { return Greater; }
108 for (&self_i, &other_i) in self.data.iter().rev().zip(other.data.iter().rev()) {
109 if self_i < other_i { return Less; }
110 if self_i > other_i { return Greater; }
116 impl Default for BigUint {
118 fn default() -> BigUint { BigUint::new(Vec::new()) }
121 impl fmt::Show for BigUint {
122 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
123 write!(f, "{}", self.to_str_radix(10))
127 impl FromStr for BigUint {
129 fn from_str(s: &str) -> Option<BigUint> {
130 FromStrRadix::from_str_radix(s, 10)
134 impl Num for BigUint {}
136 impl BitAnd<BigUint, BigUint> for BigUint {
137 fn bitand(&self, other: &BigUint) -> BigUint {
138 BigUint::new(self.data.iter().zip(other.data.iter()).map(|(ai, bi)| *ai & *bi).collect())
142 impl BitOr<BigUint, BigUint> for BigUint {
143 fn bitor(&self, other: &BigUint) -> BigUint {
144 let zeros = ZERO_VEC.iter().cycle();
145 let (a, b) = if self.data.len() > other.data.len() { (self, other) } else { (other, self) };
146 let ored = a.data.iter().zip(b.data.iter().chain(zeros)).map(
149 return BigUint::new(ored);
153 impl BitXor<BigUint, BigUint> for BigUint {
154 fn bitxor(&self, other: &BigUint) -> BigUint {
155 let zeros = ZERO_VEC.iter().cycle();
156 let (a, b) = if self.data.len() > other.data.len() { (self, other) } else { (other, self) };
157 let xored = a.data.iter().zip(b.data.iter().chain(zeros)).map(
160 return BigUint::new(xored);
164 impl Shl<uint, BigUint> for BigUint {
166 fn shl(&self, rhs: &uint) -> BigUint {
167 let n_unit = *rhs / BigDigit::bits;
168 let n_bits = *rhs % BigDigit::bits;
169 return self.shl_unit(n_unit).shl_bits(n_bits);
173 impl Shr<uint, BigUint> for BigUint {
175 fn shr(&self, rhs: &uint) -> BigUint {
176 let n_unit = *rhs / BigDigit::bits;
177 let n_bits = *rhs % BigDigit::bits;
178 return self.shr_unit(n_unit).shr_bits(n_bits);
182 impl Zero for BigUint {
184 fn zero() -> BigUint { BigUint::new(Vec::new()) }
187 fn is_zero(&self) -> bool { self.data.is_empty() }
190 impl One for BigUint {
192 fn one() -> BigUint { BigUint::new(vec!(1)) }
195 impl Unsigned for BigUint {}
197 impl Add<BigUint, BigUint> for BigUint {
198 fn add(&self, other: &BigUint) -> BigUint {
199 let zeros = ZERO_VEC.iter().cycle();
200 let (a, b) = if self.data.len() > other.data.len() { (self, other) } else { (other, self) };
203 let mut sum: Vec<BigDigit> = a.data.iter().zip(b.data.iter().chain(zeros)).map(|(ai, bi)| {
204 let (hi, lo) = BigDigit::from_doublebigdigit(
205 (*ai as DoubleBigDigit) + (*bi as DoubleBigDigit) + (carry as DoubleBigDigit));
209 if carry != 0 { sum.push(carry); }
210 return BigUint::new(sum);
214 impl Sub<BigUint, BigUint> for BigUint {
215 fn sub(&self, other: &BigUint) -> BigUint {
216 let new_len = cmp::max(self.data.len(), other.data.len());
217 let zeros = ZERO_VEC.iter().cycle();
218 let (a, b) = (self.data.iter().chain(zeros.clone()), other.data.iter().chain(zeros));
221 let diff: Vec<BigDigit> = a.take(new_len).zip(b).map(|(ai, bi)| {
222 let (hi, lo) = BigDigit::from_doublebigdigit(
224 + (*ai as DoubleBigDigit)
225 - (*bi as DoubleBigDigit)
226 - (borrow as DoubleBigDigit)
229 hi * (base) + lo == 1*(base) + ai - bi - borrow
230 => ai - bi - borrow < 0 <=> hi == 0
232 borrow = if hi == 0 { 1 } else { 0 };
237 "Cannot subtract other from self because other is larger than self.");
238 return BigUint::new(diff);
242 impl Mul<BigUint, BigUint> for BigUint {
243 fn mul(&self, other: &BigUint) -> BigUint {
244 if self.is_zero() || other.is_zero() { return Zero::zero(); }
246 let (s_len, o_len) = (self.data.len(), other.data.len());
247 if s_len == 1 { return mul_digit(other, self.data.as_slice()[0]); }
248 if o_len == 1 { return mul_digit(self, other.data.as_slice()[0]); }
250 // Using Karatsuba multiplication
251 // (a1 * base + a0) * (b1 * base + b0)
252 // = a1*b1 * base^2 +
253 // (a1*b1 + a0*b0 - (a1-b0)*(b1-a0)) * base +
255 let half_len = cmp::max(s_len, o_len) / 2;
256 let (s_hi, s_lo) = cut_at(self, half_len);
257 let (o_hi, o_lo) = cut_at(other, half_len);
259 let ll = s_lo * o_lo;
260 let hh = s_hi * o_hi;
262 let (s1, n1) = sub_sign(s_hi, s_lo);
263 let (s2, n2) = sub_sign(o_hi, o_lo);
265 (Equal, _) | (_, Equal) => hh + ll,
266 (Less, Greater) | (Greater, Less) => hh + ll + (n1 * n2),
267 (Less, Less) | (Greater, Greater) => hh + ll - (n1 * n2)
271 return ll + mm.shl_unit(half_len) + hh.shl_unit(half_len * 2);
274 fn mul_digit(a: &BigUint, n: BigDigit) -> BigUint {
275 if n == 0 { return Zero::zero(); }
276 if n == 1 { return (*a).clone(); }
279 let mut prod: Vec<BigDigit> = a.data.iter().map(|ai| {
280 let (hi, lo) = BigDigit::from_doublebigdigit(
281 (*ai as DoubleBigDigit) * (n as DoubleBigDigit) + (carry as DoubleBigDigit)
286 if carry != 0 { prod.push(carry); }
287 return BigUint::new(prod);
291 fn cut_at(a: &BigUint, n: uint) -> (BigUint, BigUint) {
292 let mid = cmp::min(a.data.len(), n);
293 return (BigUint::from_slice(a.data.slice(mid, a.data.len())),
294 BigUint::from_slice(a.data.slice(0, mid)));
298 fn sub_sign(a: BigUint, b: BigUint) -> (Ordering, BigUint) {
300 Less => (Less, b - a),
301 Greater => (Greater, a - b),
302 _ => (Equal, Zero::zero())
308 impl Div<BigUint, BigUint> for BigUint {
310 fn div(&self, other: &BigUint) -> BigUint {
311 let (q, _) = self.div_rem(other);
316 impl Rem<BigUint, BigUint> for BigUint {
318 fn rem(&self, other: &BigUint) -> BigUint {
319 let (_, r) = self.div_rem(other);
324 impl Neg<BigUint> for BigUint {
326 fn neg(&self) -> BigUint { fail!() }
329 impl CheckedAdd for BigUint {
331 fn checked_add(&self, v: &BigUint) -> Option<BigUint> {
332 return Some(self.add(v));
336 impl CheckedSub for BigUint {
338 fn checked_sub(&self, v: &BigUint) -> Option<BigUint> {
342 return Some(self.sub(v));
346 impl CheckedMul for BigUint {
348 fn checked_mul(&self, v: &BigUint) -> Option<BigUint> {
349 return Some(self.mul(v));
353 impl CheckedDiv for BigUint {
355 fn checked_div(&self, v: &BigUint) -> Option<BigUint> {
359 return Some(self.div(v));
363 impl Integer for BigUint {
365 fn div_rem(&self, other: &BigUint) -> (BigUint, BigUint) {
366 self.div_mod_floor(other)
370 fn div_floor(&self, other: &BigUint) -> BigUint {
371 let (d, _) = self.div_mod_floor(other);
376 fn mod_floor(&self, other: &BigUint) -> BigUint {
377 let (_, m) = self.div_mod_floor(other);
381 fn div_mod_floor(&self, other: &BigUint) -> (BigUint, BigUint) {
382 if other.is_zero() { fail!() }
383 if self.is_zero() { return (Zero::zero(), Zero::zero()); }
384 if *other == One::one() { return ((*self).clone(), Zero::zero()); }
386 match self.cmp(other) {
387 Less => return (Zero::zero(), (*self).clone()),
388 Equal => return (One::one(), Zero::zero()),
389 Greater => {} // Do nothing
393 let mut n = *other.data.last().unwrap();
394 while n < (1 << BigDigit::bits - 2) {
398 assert!(shift < BigDigit::bits);
399 let (d, m) = div_mod_floor_inner(self << shift, other << shift);
400 return (d, m >> shift);
403 fn div_mod_floor_inner(a: BigUint, b: BigUint) -> (BigUint, BigUint) {
405 let mut d: BigUint = Zero::zero();
408 let (d0, d_unit, b_unit) = div_estimate(&m, &b, n);
410 let mut prod = b * d0;
412 // FIXME(#5992): assignment operator overloads
415 // FIXME(#5992): assignment operator overloads
424 // FIXME(#5992): assignment operator overloads
427 // FIXME(#5992): assignment operator overloads
435 fn div_estimate(a: &BigUint, b: &BigUint, n: uint)
436 -> (BigUint, BigUint, BigUint) {
437 if a.data.len() < n {
438 return (Zero::zero(), Zero::zero(), (*a).clone());
441 let an = a.data.tailn(a.data.len() - n);
442 let bn = *b.data.last().unwrap();
443 let mut d = Vec::with_capacity(an.len());
445 for elt in an.iter().rev() {
446 let ai = BigDigit::to_doublebigdigit(carry, *elt);
447 let di = ai / (bn as DoubleBigDigit);
448 assert!(di < BigDigit::base);
449 carry = (ai % (bn as DoubleBigDigit)) as BigDigit;
450 d.push(di as BigDigit)
454 let shift = (a.data.len() - an.len()) - (b.data.len() - 1);
456 return (BigUint::new(d), One::one(), (*b).clone());
458 let one: BigUint = One::one();
459 return (BigUint::new(d).shl_unit(shift),
466 * Calculates the Greatest Common Divisor (GCD) of the number and `other`
468 * The result is always positive
471 fn gcd(&self, other: &BigUint) -> BigUint {
472 // Use Euclid's algorithm
473 let mut m = (*self).clone();
474 let mut n = (*other).clone();
484 * Calculates the Lowest Common Multiple (LCM) of the number and `other`
487 fn lcm(&self, other: &BigUint) -> BigUint { ((*self * *other) / self.gcd(other)) }
489 /// Returns `true` if the number can be divided by `other` without leaving a remainder
491 fn divides(&self, other: &BigUint) -> bool { (*self % *other).is_zero() }
493 /// Returns `true` if the number is divisible by `2`
495 fn is_even(&self) -> bool {
496 // Considering only the last digit.
497 match self.data.as_slice().head() {
498 Some(x) => x.is_even(),
503 /// Returns `true` if the number is not divisible by `2`
505 fn is_odd(&self) -> bool { !self.is_even() }
508 impl ToPrimitive for BigUint {
510 fn to_i64(&self) -> Option<i64> {
511 self.to_u64().and_then(|n| {
512 // If top bit of u64 is set, it's too large to convert to i64.
521 // `DoubleBigDigit` size dependent
523 fn to_u64(&self) -> Option<u64> {
524 match self.data.len() {
526 1 => Some(self.data.as_slice()[0] as u64),
527 2 => Some(BigDigit::to_doublebigdigit(self.data.as_slice()[1], self.data.as_slice()[0])
534 impl FromPrimitive for BigUint {
536 fn from_i64(n: i64) -> Option<BigUint> {
538 FromPrimitive::from_u64(n as u64)
546 // `DoubleBigDigit` size dependent
548 fn from_u64(n: u64) -> Option<BigUint> {
549 let n = match BigDigit::from_doublebigdigit(n) {
550 (0, 0) => Zero::zero(),
551 (0, n0) => BigUint::new(vec!(n0)),
552 (n1, n0) => BigUint::new(vec!(n0, n1))
558 /// A generic trait for converting a value to a `BigUint`.
559 pub trait ToBigUint {
560 /// Converts the value of `self` to a `BigUint`.
561 fn to_biguint(&self) -> Option<BigUint>;
564 impl ToBigUint for BigInt {
566 fn to_biguint(&self) -> Option<BigUint> {
567 if self.sign == Plus {
568 Some(self.data.clone())
569 } else if self.sign == Zero {
577 impl ToBigUint for BigUint {
579 fn to_biguint(&self) -> Option<BigUint> {
584 macro_rules! impl_to_biguint(
585 ($T:ty, $from_ty:path) => {
586 impl ToBigUint for $T {
588 fn to_biguint(&self) -> Option<BigUint> {
595 impl_to_biguint!(int, FromPrimitive::from_int)
596 impl_to_biguint!(i8, FromPrimitive::from_i8)
597 impl_to_biguint!(i16, FromPrimitive::from_i16)
598 impl_to_biguint!(i32, FromPrimitive::from_i32)
599 impl_to_biguint!(i64, FromPrimitive::from_i64)
600 impl_to_biguint!(uint, FromPrimitive::from_uint)
601 impl_to_biguint!(u8, FromPrimitive::from_u8)
602 impl_to_biguint!(u16, FromPrimitive::from_u16)
603 impl_to_biguint!(u32, FromPrimitive::from_u32)
604 impl_to_biguint!(u64, FromPrimitive::from_u64)
606 impl ToStrRadix for BigUint {
607 fn to_str_radix(&self, radix: uint) -> String {
608 assert!(1 < radix && radix <= 16);
609 let (base, max_len) = get_radix_base(radix);
610 if base == BigDigit::base {
611 return fill_concat(self.data.as_slice(), radix, max_len)
613 return fill_concat(convert_base(self, base).as_slice(), radix, max_len);
615 fn convert_base(n: &BigUint, base: DoubleBigDigit) -> Vec<BigDigit> {
616 let divider = base.to_biguint().unwrap();
617 let mut result = Vec::new();
618 let mut m = n.clone();
620 let (d, m0) = m.div_mod_floor(÷r);
621 result.push(m0.to_uint().unwrap() as BigDigit);
625 result.push(m.to_uint().unwrap() as BigDigit);
630 fn fill_concat(v: &[BigDigit], radix: uint, l: uint) -> String {
632 return "0".to_string()
634 let mut s = String::with_capacity(v.len() * l);
635 for n in v.iter().rev() {
636 let ss = (*n as uint).to_str_radix(radix);
637 s.push_str("0".repeat(l - ss.len()).as_slice());
638 s.push_str(ss.as_slice());
640 s.as_slice().trim_left_chars('0').to_string()
645 impl FromStrRadix for BigUint {
646 /// Creates and initializes a `BigUint`.
648 fn from_str_radix(s: &str, radix: uint)
650 BigUint::parse_bytes(s.as_bytes(), radix)
655 /// Creates and initializes a `BigUint`.
657 /// The digits are be in base 2^32.
659 pub fn new(v: Vec<BigDigit>) -> BigUint {
660 // omit trailing zeros
661 let new_len = v.iter().rposition(|n| *n != 0).map_or(0, |p| p + 1);
663 if new_len == v.len() { return BigUint { data: v }; }
666 return BigUint { data: v };
669 /// Creates and initializes a `BigUint`.
671 /// The digits are be in base 2^32.
673 pub fn from_slice(slice: &[BigDigit]) -> BigUint {
674 return BigUint::new(Vec::from_slice(slice));
677 /// Creates and initializes a `BigUint`.
678 pub fn parse_bytes(buf: &[u8], radix: uint) -> Option<BigUint> {
679 let (base, unit_len) = get_radix_base(radix);
680 let base_num = match base.to_biguint() {
681 Some(base_num) => base_num,
682 None => { return None; }
685 let mut end = buf.len();
686 let mut n: BigUint = Zero::zero();
687 let mut power: BigUint = One::one();
689 let start = cmp::max(end, unit_len) - unit_len;
690 match uint::parse_bytes(buf.slice(start, end), radix) {
692 let d: Option<BigUint> = FromPrimitive::from_uint(d);
695 // FIXME(#5992): assignment operator overloads
699 None => { return None; }
702 None => { return None; }
708 // FIXME(#5992): assignment operator overloads
709 // power *= base_num;
710 power = power * base_num;
715 fn shl_unit(&self, n_unit: uint) -> BigUint {
716 if n_unit == 0 || self.is_zero() { return (*self).clone(); }
718 BigUint::new(Vec::from_elem(n_unit, ZERO_BIG_DIGIT).append(self.data.as_slice()))
722 fn shl_bits(&self, n_bits: uint) -> BigUint {
723 if n_bits == 0 || self.is_zero() { return (*self).clone(); }
726 let mut shifted: Vec<BigDigit> = self.data.iter().map(|elem| {
727 let (hi, lo) = BigDigit::from_doublebigdigit(
728 (*elem as DoubleBigDigit) << n_bits | (carry as DoubleBigDigit)
733 if carry != 0 { shifted.push(carry); }
734 return BigUint::new(shifted);
738 fn shr_unit(&self, n_unit: uint) -> BigUint {
739 if n_unit == 0 { return (*self).clone(); }
740 if self.data.len() < n_unit { return Zero::zero(); }
741 return BigUint::from_slice(
742 self.data.slice(n_unit, self.data.len())
747 fn shr_bits(&self, n_bits: uint) -> BigUint {
748 if n_bits == 0 || self.data.is_empty() { return (*self).clone(); }
751 let mut shifted_rev = Vec::with_capacity(self.data.len());
752 for elem in self.data.iter().rev() {
753 shifted_rev.push((*elem >> n_bits) | borrow);
754 borrow = *elem << (BigDigit::bits - n_bits);
756 let shifted = { shifted_rev.reverse(); shifted_rev };
757 return BigUint::new(shifted);
760 /// Determines the fewest bits necessary to express the `BigUint`.
761 pub fn bits(&self) -> uint {
762 if self.is_zero() { return 0; }
763 let zeros = self.data.last().unwrap().leading_zeros();
764 return self.data.len()*BigDigit::bits - (zeros as uint);
768 // `DoubleBigDigit` size dependent
770 fn get_radix_base(radix: uint) -> (DoubleBigDigit, uint) {
771 assert!(1 < radix && radix <= 16);
773 2 => (4294967296, 32),
774 3 => (3486784401, 20),
775 4 => (4294967296, 16),
776 5 => (1220703125, 13),
777 6 => (2176782336, 12),
778 7 => (1977326743, 11),
779 8 => (1073741824, 10),
780 9 => (3486784401, 10),
781 10 => (1000000000, 9),
782 11 => (2357947691, 9),
783 12 => (429981696, 8),
784 13 => (815730721, 8),
785 14 => (1475789056, 8),
786 15 => (2562890625, 8),
787 16 => (4294967296, 8),
792 /// A Sign is a `BigInt`'s composing element.
793 #[deriving(PartialEq, PartialOrd, Eq, Ord, Clone, Show)]
794 pub enum Sign { Minus, Zero, Plus }
796 impl Neg<Sign> for Sign {
797 /// Negate Sign value.
799 fn neg(&self) -> Sign {
808 /// A big signed integer type.
815 impl PartialEq for BigInt {
817 fn eq(&self, other: &BigInt) -> bool {
818 match self.cmp(other) { Equal => true, _ => false }
822 impl Eq for BigInt {}
824 impl PartialOrd for BigInt {
826 fn lt(&self, other: &BigInt) -> bool {
827 match self.cmp(other) { Less => true, _ => false}
831 impl Ord for BigInt {
833 fn cmp(&self, other: &BigInt) -> Ordering {
834 let scmp = self.sign.cmp(&other.sign);
835 if scmp != Equal { return scmp; }
839 Plus => self.data.cmp(&other.data),
840 Minus => other.data.cmp(&self.data),
845 impl Default for BigInt {
847 fn default() -> BigInt { BigInt::new(Zero, Vec::new()) }
850 impl fmt::Show for BigInt {
851 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
852 write!(f, "{}", self.to_str_radix(10))
856 impl FromStr for BigInt {
858 fn from_str(s: &str) -> Option<BigInt> {
859 FromStrRadix::from_str_radix(s, 10)
863 impl Num for BigInt {}
865 impl Shl<uint, BigInt> for BigInt {
867 fn shl(&self, rhs: &uint) -> BigInt {
868 BigInt::from_biguint(self.sign, self.data << *rhs)
872 impl Shr<uint, BigInt> for BigInt {
874 fn shr(&self, rhs: &uint) -> BigInt {
875 BigInt::from_biguint(self.sign, self.data >> *rhs)
879 impl Zero for BigInt {
881 fn zero() -> BigInt {
882 BigInt::from_biguint(Zero, Zero::zero())
886 fn is_zero(&self) -> bool { self.sign == Zero }
889 impl One for BigInt {
892 BigInt::from_biguint(Plus, One::one())
896 impl Signed for BigInt {
898 fn abs(&self) -> BigInt {
900 Plus | Zero => self.clone(),
901 Minus => BigInt::from_biguint(Plus, self.data.clone())
906 fn abs_sub(&self, other: &BigInt) -> BigInt {
907 if *self <= *other { Zero::zero() } else { *self - *other }
911 fn signum(&self) -> BigInt {
913 Plus => BigInt::from_biguint(Plus, One::one()),
914 Minus => BigInt::from_biguint(Minus, One::one()),
915 Zero => Zero::zero(),
920 fn is_positive(&self) -> bool { self.sign == Plus }
923 fn is_negative(&self) -> bool { self.sign == Minus }
926 impl Add<BigInt, BigInt> for BigInt {
928 fn add(&self, other: &BigInt) -> BigInt {
929 match (self.sign, other.sign) {
930 (Zero, _) => other.clone(),
931 (_, Zero) => self.clone(),
932 (Plus, Plus) => BigInt::from_biguint(Plus,
933 self.data + other.data),
934 (Plus, Minus) => self - (-*other),
935 (Minus, Plus) => other - (-*self),
936 (Minus, Minus) => -((-self) + (-*other))
941 impl Sub<BigInt, BigInt> for BigInt {
943 fn sub(&self, other: &BigInt) -> BigInt {
944 match (self.sign, other.sign) {
946 (_, Zero) => self.clone(),
947 (Plus, Plus) => match self.data.cmp(&other.data) {
948 Less => BigInt::from_biguint(Minus, other.data - self.data),
949 Greater => BigInt::from_biguint(Plus, self.data - other.data),
950 Equal => Zero::zero()
952 (Plus, Minus) => self + (-*other),
953 (Minus, Plus) => -((-self) + *other),
954 (Minus, Minus) => (-other) - (-*self)
959 impl Mul<BigInt, BigInt> for BigInt {
961 fn mul(&self, other: &BigInt) -> BigInt {
962 match (self.sign, other.sign) {
963 (Zero, _) | (_, Zero) => Zero::zero(),
964 (Plus, Plus) | (Minus, Minus) => {
965 BigInt::from_biguint(Plus, self.data * other.data)
967 (Plus, Minus) | (Minus, Plus) => {
968 BigInt::from_biguint(Minus, self.data * other.data)
974 impl Div<BigInt, BigInt> for BigInt {
976 fn div(&self, other: &BigInt) -> BigInt {
977 let (q, _) = self.div_rem(other);
982 impl Rem<BigInt, BigInt> for BigInt {
984 fn rem(&self, other: &BigInt) -> BigInt {
985 let (_, r) = self.div_rem(other);
990 impl Neg<BigInt> for BigInt {
992 fn neg(&self) -> BigInt {
993 BigInt::from_biguint(self.sign.neg(), self.data.clone())
997 impl CheckedAdd for BigInt {
999 fn checked_add(&self, v: &BigInt) -> Option<BigInt> {
1000 return Some(self.add(v));
1004 impl CheckedSub for BigInt {
1006 fn checked_sub(&self, v: &BigInt) -> Option<BigInt> {
1007 return Some(self.sub(v));
1011 impl CheckedMul for BigInt {
1013 fn checked_mul(&self, v: &BigInt) -> Option<BigInt> {
1014 return Some(self.mul(v));
1018 impl CheckedDiv for BigInt {
1020 fn checked_div(&self, v: &BigInt) -> Option<BigInt> {
1024 return Some(self.div(v));
1029 impl Integer for BigInt {
1031 fn div_rem(&self, other: &BigInt) -> (BigInt, BigInt) {
1032 // r.sign == self.sign
1033 let (d_ui, r_ui) = self.data.div_mod_floor(&other.data);
1034 let d = BigInt::from_biguint(Plus, d_ui);
1035 let r = BigInt::from_biguint(Plus, r_ui);
1036 match (self.sign, other.sign) {
1037 (_, Zero) => fail!(),
1038 (Plus, Plus) | (Zero, Plus) => ( d, r),
1039 (Plus, Minus) | (Zero, Minus) => (-d, r),
1040 (Minus, Plus) => (-d, -r),
1041 (Minus, Minus) => ( d, -r)
1046 fn div_floor(&self, other: &BigInt) -> BigInt {
1047 let (d, _) = self.div_mod_floor(other);
1052 fn mod_floor(&self, other: &BigInt) -> BigInt {
1053 let (_, m) = self.div_mod_floor(other);
1057 fn div_mod_floor(&self, other: &BigInt) -> (BigInt, BigInt) {
1058 // m.sign == other.sign
1059 let (d_ui, m_ui) = self.data.div_rem(&other.data);
1060 let d = BigInt::from_biguint(Plus, d_ui);
1061 let m = BigInt::from_biguint(Plus, m_ui);
1062 match (self.sign, other.sign) {
1063 (_, Zero) => fail!(),
1064 (Plus, Plus) | (Zero, Plus) => (d, m),
1065 (Plus, Minus) | (Zero, Minus) => if m.is_zero() {
1068 (-d - One::one(), m + *other)
1070 (Minus, Plus) => if m.is_zero() {
1073 (-d - One::one(), other - m)
1075 (Minus, Minus) => (d, -m)
1080 * Calculates the Greatest Common Divisor (GCD) of the number and `other`
1082 * The result is always positive
1085 fn gcd(&self, other: &BigInt) -> BigInt {
1086 BigInt::from_biguint(Plus, self.data.gcd(&other.data))
1090 * Calculates the Lowest Common Multiple (LCM) of the number and `other`
1093 fn lcm(&self, other: &BigInt) -> BigInt {
1094 BigInt::from_biguint(Plus, self.data.lcm(&other.data))
1097 /// Returns `true` if the number can be divided by `other` without leaving a remainder
1099 fn divides(&self, other: &BigInt) -> bool { self.data.divides(&other.data) }
1101 /// Returns `true` if the number is divisible by `2`
1103 fn is_even(&self) -> bool { self.data.is_even() }
1105 /// Returns `true` if the number is not divisible by `2`
1107 fn is_odd(&self) -> bool { self.data.is_odd() }
1110 impl ToPrimitive for BigInt {
1112 fn to_i64(&self) -> Option<i64> {
1114 Plus => self.data.to_i64(),
1117 self.data.to_u64().and_then(|n| {
1118 let m: u64 = 1 << 63;
1132 fn to_u64(&self) -> Option<u64> {
1134 Plus => self.data.to_u64(),
1141 impl FromPrimitive for BigInt {
1143 fn from_i64(n: i64) -> Option<BigInt> {
1145 FromPrimitive::from_u64(n as u64).and_then(|n| {
1146 Some(BigInt::from_biguint(Plus, n))
1149 FromPrimitive::from_u64(u64::MAX - (n as u64) + 1).and_then(
1151 Some(BigInt::from_biguint(Minus, n))
1159 fn from_u64(n: u64) -> Option<BigInt> {
1163 FromPrimitive::from_u64(n).and_then(|n| {
1164 Some(BigInt::from_biguint(Plus, n))
1170 /// A generic trait for converting a value to a `BigInt`.
1171 pub trait ToBigInt {
1172 /// Converts the value of `self` to a `BigInt`.
1173 fn to_bigint(&self) -> Option<BigInt>;
1176 impl ToBigInt for BigInt {
1178 fn to_bigint(&self) -> Option<BigInt> {
1183 impl ToBigInt for BigUint {
1185 fn to_bigint(&self) -> Option<BigInt> {
1189 Some(BigInt { sign: Plus, data: self.clone() })
1194 macro_rules! impl_to_bigint(
1195 ($T:ty, $from_ty:path) => {
1196 impl ToBigInt for $T {
1198 fn to_bigint(&self) -> Option<BigInt> {
1205 impl_to_bigint!(int, FromPrimitive::from_int)
1206 impl_to_bigint!(i8, FromPrimitive::from_i8)
1207 impl_to_bigint!(i16, FromPrimitive::from_i16)
1208 impl_to_bigint!(i32, FromPrimitive::from_i32)
1209 impl_to_bigint!(i64, FromPrimitive::from_i64)
1210 impl_to_bigint!(uint, FromPrimitive::from_uint)
1211 impl_to_bigint!(u8, FromPrimitive::from_u8)
1212 impl_to_bigint!(u16, FromPrimitive::from_u16)
1213 impl_to_bigint!(u32, FromPrimitive::from_u32)
1214 impl_to_bigint!(u64, FromPrimitive::from_u64)
1216 impl ToStrRadix for BigInt {
1218 fn to_str_radix(&self, radix: uint) -> String {
1220 Plus => self.data.to_str_radix(radix),
1221 Zero => "0".to_string(),
1222 Minus => format!("-{}", self.data.to_str_radix(radix)),
1227 impl FromStrRadix for BigInt {
1228 /// Creates and initializes a BigInt.
1230 fn from_str_radix(s: &str, radix: uint) -> Option<BigInt> {
1231 BigInt::parse_bytes(s.as_bytes(), radix)
1235 pub trait RandBigInt {
1236 /// Generate a random `BigUint` of the given bit size.
1237 fn gen_biguint(&mut self, bit_size: uint) -> BigUint;
1239 /// Generate a random BigInt of the given bit size.
1240 fn gen_bigint(&mut self, bit_size: uint) -> BigInt;
1242 /// Generate a random `BigUint` less than the given bound. Fails
1243 /// when the bound is zero.
1244 fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint;
1246 /// Generate a random `BigUint` within the given range. The lower
1247 /// bound is inclusive; the upper bound is exclusive. Fails when
1248 /// the upper bound is not greater than the lower bound.
1249 fn gen_biguint_range(&mut self, lbound: &BigUint, ubound: &BigUint) -> BigUint;
1251 /// Generate a random `BigInt` within the given range. The lower
1252 /// bound is inclusive; the upper bound is exclusive. Fails when
1253 /// the upper bound is not greater than the lower bound.
1254 fn gen_bigint_range(&mut self, lbound: &BigInt, ubound: &BigInt) -> BigInt;
1257 impl<R: Rng> RandBigInt for R {
1258 fn gen_biguint(&mut self, bit_size: uint) -> BigUint {
1259 let (digits, rem) = bit_size.div_rem(&BigDigit::bits);
1260 let mut data = Vec::with_capacity(digits+1);
1261 for _ in range(0, digits) {
1262 data.push(self.gen());
1265 let final_digit: BigDigit = self.gen();
1266 data.push(final_digit >> (BigDigit::bits - rem));
1268 return BigUint::new(data);
1271 fn gen_bigint(&mut self, bit_size: uint) -> BigInt {
1272 // Generate a random BigUint...
1273 let biguint = self.gen_biguint(bit_size);
1274 // ...and then randomly assign it a Sign...
1275 let sign = if biguint.is_zero() {
1276 // ...except that if the BigUint is zero, we need to try
1277 // again with probability 0.5. This is because otherwise,
1278 // the probability of generating a zero BigInt would be
1279 // double that of any other number.
1281 return self.gen_bigint(bit_size);
1285 } else if self.gen() {
1290 return BigInt::from_biguint(sign, biguint);
1293 fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint {
1294 assert!(!bound.is_zero());
1295 let bits = bound.bits();
1297 let n = self.gen_biguint(bits);
1298 if n < *bound { return n; }
1302 fn gen_biguint_range(&mut self,
1306 assert!(*lbound < *ubound);
1307 return *lbound + self.gen_biguint_below(&(*ubound - *lbound));
1310 fn gen_bigint_range(&mut self,
1314 assert!(*lbound < *ubound);
1315 let delta = (*ubound - *lbound).to_biguint().unwrap();
1316 return *lbound + self.gen_biguint_below(&delta).to_bigint().unwrap();
1321 /// Creates and initializes a BigInt.
1323 /// The digits are be in base 2^32.
1325 pub fn new(sign: Sign, v: Vec<BigDigit>) -> BigInt {
1326 BigInt::from_biguint(sign, BigUint::new(v))
1329 /// Creates and initializes a `BigInt`.
1331 /// The digits are be in base 2^32.
1333 pub fn from_biguint(sign: Sign, data: BigUint) -> BigInt {
1334 if sign == Zero || data.is_zero() {
1335 return BigInt { sign: Zero, data: Zero::zero() };
1337 return BigInt { sign: sign, data: data };
1340 /// Creates and initializes a `BigInt`.
1342 pub fn from_slice(sign: Sign, slice: &[BigDigit]) -> BigInt {
1343 BigInt::from_biguint(sign, BigUint::from_slice(slice))
1346 /// Creates and initializes a `BigInt`.
1347 pub fn parse_bytes(buf: &[u8], radix: uint)
1349 if buf.is_empty() { return None; }
1350 let mut sign = Plus;
1352 if buf[0] == ('-' as u8) {
1356 return BigUint::parse_bytes(buf.slice(start, buf.len()), radix)
1357 .map(|bu| BigInt::from_biguint(sign, bu));
1360 /// Converts this `BigInt` into a `BigUint`, if it's not negative.
1362 pub fn to_biguint(&self) -> Option<BigUint> {
1364 Plus => Some(self.data.clone()),
1365 Zero => Some(Zero::zero()),
1374 use super::{BigDigit, BigUint, ToBigUint};
1375 use super::{Plus, BigInt, RandBigInt, ToBigInt};
1377 use std::cmp::{Less, Equal, Greater};
1378 use std::from_str::FromStr;
1380 use std::num::{Zero, One, FromStrRadix, ToStrRadix};
1381 use std::num::{ToPrimitive, FromPrimitive};
1382 use std::num::CheckedDiv;
1383 use std::rand::task_rng;
1387 fn test_from_slice() {
1388 fn check(slice: &[BigDigit], data: &[BigDigit]) {
1389 assert!(data == BigUint::from_slice(slice).data.as_slice());
1392 check([0, 0, 0], []);
1393 check([1, 2, 0, 0], [1, 2]);
1394 check([0, 0, 1, 2], [0, 0, 1, 2]);
1395 check([0, 0, 1, 2, 0, 0], [0, 0, 1, 2]);
1401 let data: Vec<BigUint> = [ &[], &[1], &[2], &[-1], &[0, 1], &[2, 1], &[1, 1, 1] ]
1402 .iter().map(|v| BigUint::from_slice(*v)).collect();
1403 for (i, ni) in data.iter().enumerate() {
1404 for (j0, nj) in data.slice(i, data.len()).iter().enumerate() {
1407 assert_eq!(ni.cmp(nj), Equal);
1408 assert_eq!(nj.cmp(ni), Equal);
1410 assert!(!(ni != nj));
1413 assert!(!(ni < nj));
1414 assert!(!(ni > nj));
1416 assert_eq!(ni.cmp(nj), Less);
1417 assert_eq!(nj.cmp(ni), Greater);
1419 assert!(!(ni == nj));
1423 assert!(!(ni >= nj));
1425 assert!(!(ni > nj));
1427 assert!(!(nj <= ni));
1429 assert!(!(nj < ni));
1438 fn check(left: &[BigDigit],
1440 expected: &[BigDigit]) {
1441 assert_eq!(BigUint::from_slice(left) & BigUint::from_slice(right),
1442 BigUint::from_slice(expected));
1445 check([268, 482, 17],
1452 fn check(left: &[BigDigit],
1454 expected: &[BigDigit]) {
1455 assert_eq!(BigUint::from_slice(left) | BigUint::from_slice(right),
1456 BigUint::from_slice(expected));
1459 check([268, 482, 17],
1466 fn check(left: &[BigDigit],
1468 expected: &[BigDigit]) {
1469 assert_eq!(BigUint::from_slice(left) ^ BigUint::from_slice(right),
1470 BigUint::from_slice(expected));
1473 check([268, 482, 17],
1480 fn check(s: &str, shift: uint, ans: &str) {
1481 let opt_biguint: Option<BigUint> = FromStrRadix::from_str_radix(s, 16);
1482 let bu = (opt_biguint.unwrap() << shift).to_str_radix(16);
1483 assert_eq!(bu.as_slice(), ans);
1595 check("88887777666655554444333322221111", 16,
1596 "888877776666555544443333222211110000");
1601 fn check(s: &str, shift: uint, ans: &str) {
1602 let opt_biguint: Option<BigUint> =
1603 FromStrRadix::from_str_radix(s, 16);
1604 let bu = (opt_biguint.unwrap() >> shift).to_str_radix(16);
1605 assert_eq!(bu.as_slice(), ans);
1713 check("888877776666555544443333222211110000", 16,
1714 "88887777666655554444333322221111");
1717 // `DoubleBigDigit` size dependent
1719 fn test_convert_i64() {
1720 fn check(b1: BigUint, i: i64) {
1721 let b2: BigUint = FromPrimitive::from_i64(i).unwrap();
1723 assert!(b1.to_i64().unwrap() == i);
1726 check(Zero::zero(), 0);
1727 check(One::one(), 1);
1728 check(i64::MAX.to_biguint().unwrap(), i64::MAX);
1730 check(BigUint::new(vec!( )), 0);
1731 check(BigUint::new(vec!( 1 )), (1 << (0*BigDigit::bits)));
1732 check(BigUint::new(vec!(-1 )), (1 << (1*BigDigit::bits)) - 1);
1733 check(BigUint::new(vec!( 0, 1 )), (1 << (1*BigDigit::bits)));
1734 check(BigUint::new(vec!(-1, -1 >> 1)), i64::MAX);
1736 assert_eq!(i64::MIN.to_biguint(), None);
1737 assert_eq!(BigUint::new(vec!(-1, -1 )).to_i64(), None);
1738 assert_eq!(BigUint::new(vec!( 0, 0, 1)).to_i64(), None);
1739 assert_eq!(BigUint::new(vec!(-1, -1, -1)).to_i64(), None);
1742 // `DoubleBigDigit` size dependent
1744 fn test_convert_u64() {
1745 fn check(b1: BigUint, u: u64) {
1746 let b2: BigUint = FromPrimitive::from_u64(u).unwrap();
1748 assert!(b1.to_u64().unwrap() == u);
1751 check(Zero::zero(), 0);
1752 check(One::one(), 1);
1753 check(u64::MIN.to_biguint().unwrap(), u64::MIN);
1754 check(u64::MAX.to_biguint().unwrap(), u64::MAX);
1756 check(BigUint::new(vec!( )), 0);
1757 check(BigUint::new(vec!( 1 )), (1 << (0*BigDigit::bits)));
1758 check(BigUint::new(vec!(-1 )), (1 << (1*BigDigit::bits)) - 1);
1759 check(BigUint::new(vec!( 0, 1)), (1 << (1*BigDigit::bits)));
1760 check(BigUint::new(vec!(-1, -1)), u64::MAX);
1762 assert_eq!(BigUint::new(vec!( 0, 0, 1)).to_u64(), None);
1763 assert_eq!(BigUint::new(vec!(-1, -1, -1)).to_u64(), None);
1767 fn test_convert_to_bigint() {
1768 fn check(n: BigUint, ans: BigInt) {
1769 assert_eq!(n.to_bigint().unwrap(), ans);
1770 assert_eq!(n.to_bigint().unwrap().to_biguint().unwrap(), n);
1772 check(Zero::zero(), Zero::zero());
1773 check(BigUint::new(vec!(1,2,3)),
1774 BigInt::from_biguint(Plus, BigUint::new(vec!(1,2,3))));
1777 static sum_triples: &'static [(&'static [BigDigit],
1778 &'static [BigDigit],
1779 &'static [BigDigit])] = &[
1781 (&[], &[ 1], &[ 1]),
1782 (&[ 1], &[ 1], &[ 2]),
1783 (&[ 1], &[ 1, 1], &[ 2, 1]),
1784 (&[ 1], &[-1], &[ 0, 1]),
1785 (&[ 1], &[-1, -1], &[ 0, 0, 1]),
1786 (&[-1, -1], &[-1, -1], &[-2, -1, 1]),
1787 (&[ 1, 1, 1], &[-1, -1], &[ 0, 1, 2]),
1788 (&[ 2, 2, 1], &[-1, -2], &[ 1, 1, 2])
1793 for elm in sum_triples.iter() {
1794 let (a_vec, b_vec, c_vec) = *elm;
1795 let a = BigUint::from_slice(a_vec);
1796 let b = BigUint::from_slice(b_vec);
1797 let c = BigUint::from_slice(c_vec);
1799 assert!(a + b == c);
1800 assert!(b + a == c);
1806 for elm in sum_triples.iter() {
1807 let (a_vec, b_vec, c_vec) = *elm;
1808 let a = BigUint::from_slice(a_vec);
1809 let b = BigUint::from_slice(b_vec);
1810 let c = BigUint::from_slice(c_vec);
1812 assert!(c - a == b);
1813 assert!(c - b == a);
1819 fn test_sub_fail_on_underflow() {
1820 let (a, b) : (BigUint, BigUint) = (Zero::zero(), One::one());
1824 static mul_triples: &'static [(&'static [BigDigit],
1825 &'static [BigDigit],
1826 &'static [BigDigit])] = &[
1830 (&[ 1], &[ 1], &[1]),
1831 (&[ 2], &[ 3], &[ 6]),
1832 (&[ 1], &[ 1, 1, 1], &[1, 1, 1]),
1833 (&[ 1, 2, 3], &[ 3], &[ 3, 6, 9]),
1834 (&[ 1, 1, 1], &[-1], &[-1, -1, -1]),
1835 (&[ 1, 2, 3], &[-1], &[-1, -2, -2, 2]),
1836 (&[ 1, 2, 3, 4], &[-1], &[-1, -2, -2, -2, 3]),
1837 (&[-1], &[-1], &[ 1, -2]),
1838 (&[-1, -1], &[-1], &[ 1, -1, -2]),
1839 (&[-1, -1, -1], &[-1], &[ 1, -1, -1, -2]),
1840 (&[-1, -1, -1, -1], &[-1], &[ 1, -1, -1, -1, -2]),
1841 (&[-1/2 + 1], &[ 2], &[ 0, 1]),
1842 (&[0, -1/2 + 1], &[ 2], &[ 0, 0, 1]),
1843 (&[ 1, 2], &[ 1, 2, 3], &[1, 4, 7, 6]),
1844 (&[-1, -1], &[-1, -1, -1], &[1, 0, -1, -2, -1]),
1845 (&[-1, -1, -1], &[-1, -1, -1, -1], &[1, 0, 0, -1, -2, -1, -1]),
1846 (&[ 0, 0, 1], &[ 1, 2, 3], &[0, 0, 1, 2, 3]),
1847 (&[ 0, 0, 1], &[ 0, 0, 0, 1], &[0, 0, 0, 0, 0, 1])
1850 static div_rem_quadruples: &'static [(&'static [BigDigit],
1851 &'static [BigDigit],
1852 &'static [BigDigit],
1853 &'static [BigDigit])]
1855 (&[ 1], &[ 2], &[], &[1]),
1856 (&[ 1, 1], &[ 2], &[-1/2+1], &[1]),
1857 (&[ 1, 1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
1858 (&[ 0, 1], &[-1], &[1], &[1]),
1859 (&[-1, -1], &[-2], &[2, 1], &[3])
1864 for elm in mul_triples.iter() {
1865 let (a_vec, b_vec, c_vec) = *elm;
1866 let a = BigUint::from_slice(a_vec);
1867 let b = BigUint::from_slice(b_vec);
1868 let c = BigUint::from_slice(c_vec);
1870 assert!(a * b == c);
1871 assert!(b * a == c);
1874 for elm in div_rem_quadruples.iter() {
1875 let (a_vec, b_vec, c_vec, d_vec) = *elm;
1876 let a = BigUint::from_slice(a_vec);
1877 let b = BigUint::from_slice(b_vec);
1878 let c = BigUint::from_slice(c_vec);
1879 let d = BigUint::from_slice(d_vec);
1881 assert!(a == b * c + d);
1882 assert!(a == c * b + d);
1888 for elm in mul_triples.iter() {
1889 let (a_vec, b_vec, c_vec) = *elm;
1890 let a = BigUint::from_slice(a_vec);
1891 let b = BigUint::from_slice(b_vec);
1892 let c = BigUint::from_slice(c_vec);
1895 assert_eq!(c.div_rem(&a), (b.clone(), Zero::zero()));
1898 assert_eq!(c.div_rem(&b), (a.clone(), Zero::zero()));
1902 for elm in div_rem_quadruples.iter() {
1903 let (a_vec, b_vec, c_vec, d_vec) = *elm;
1904 let a = BigUint::from_slice(a_vec);
1905 let b = BigUint::from_slice(b_vec);
1906 let c = BigUint::from_slice(c_vec);
1907 let d = BigUint::from_slice(d_vec);
1909 if !b.is_zero() { assert!(a.div_rem(&b) == (c, d)); }
1914 fn test_checked_add() {
1915 for elm in sum_triples.iter() {
1916 let (aVec, bVec, cVec) = *elm;
1917 let a = BigUint::from_slice(aVec);
1918 let b = BigUint::from_slice(bVec);
1919 let c = BigUint::from_slice(cVec);
1921 assert!(a.checked_add(&b).unwrap() == c);
1922 assert!(b.checked_add(&a).unwrap() == c);
1927 fn test_checked_sub() {
1928 for elm in sum_triples.iter() {
1929 let (aVec, bVec, cVec) = *elm;
1930 let a = BigUint::from_slice(aVec);
1931 let b = BigUint::from_slice(bVec);
1932 let c = BigUint::from_slice(cVec);
1934 assert!(c.checked_sub(&a).unwrap() == b);
1935 assert!(c.checked_sub(&b).unwrap() == a);
1938 assert!(a.checked_sub(&c).is_none());
1941 assert!(b.checked_sub(&c).is_none());
1947 fn test_checked_mul() {
1948 for elm in mul_triples.iter() {
1949 let (aVec, bVec, cVec) = *elm;
1950 let a = BigUint::from_slice(aVec);
1951 let b = BigUint::from_slice(bVec);
1952 let c = BigUint::from_slice(cVec);
1954 assert!(a.checked_mul(&b).unwrap() == c);
1955 assert!(b.checked_mul(&a).unwrap() == c);
1958 for elm in div_rem_quadruples.iter() {
1959 let (aVec, bVec, cVec, dVec) = *elm;
1960 let a = BigUint::from_slice(aVec);
1961 let b = BigUint::from_slice(bVec);
1962 let c = BigUint::from_slice(cVec);
1963 let d = BigUint::from_slice(dVec);
1965 assert!(a == b.checked_mul(&c).unwrap() + d);
1966 assert!(a == c.checked_mul(&b).unwrap() + d);
1971 fn test_checked_div() {
1972 for elm in mul_triples.iter() {
1973 let (aVec, bVec, cVec) = *elm;
1974 let a = BigUint::from_slice(aVec);
1975 let b = BigUint::from_slice(bVec);
1976 let c = BigUint::from_slice(cVec);
1979 assert!(c.checked_div(&a).unwrap() == b);
1982 assert!(c.checked_div(&b).unwrap() == a);
1985 assert!(c.checked_div(&Zero::zero()).is_none());
1991 fn check(a: uint, b: uint, c: uint) {
1992 let big_a: BigUint = FromPrimitive::from_uint(a).unwrap();
1993 let big_b: BigUint = FromPrimitive::from_uint(b).unwrap();
1994 let big_c: BigUint = FromPrimitive::from_uint(c).unwrap();
1996 assert_eq!(big_a.gcd(&big_b), big_c);
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.lcm(&big_b), big_c);
2021 check(99, 17, 1683);
2026 let one: BigUint = FromStr::from_str("1").unwrap();
2027 let two: BigUint = FromStr::from_str("2").unwrap();
2028 let thousand: BigUint = FromStr::from_str("1000").unwrap();
2029 let big: BigUint = FromStr::from_str("1000000000000000000000").unwrap();
2030 let bigger: BigUint = FromStr::from_str("1000000000000000000001").unwrap();
2031 assert!(one.is_odd());
2032 assert!(two.is_even());
2033 assert!(thousand.is_even());
2034 assert!(big.is_even());
2035 assert!(bigger.is_odd());
2036 assert!((one << 64).is_even());
2037 assert!(((one << 64) + one).is_odd());
2040 fn to_str_pairs() -> Vec<(BigUint, Vec<(uint, String)>)> {
2041 let bits = BigDigit::bits;
2042 vec!(( Zero::zero(), vec!(
2043 (2, "0".to_string()), (3, "0".to_string())
2044 )), ( BigUint::from_slice([ 0xff ]), vec!(
2045 (2, "11111111".to_string()),
2046 (3, "100110".to_string()),
2047 (4, "3333".to_string()),
2048 (5, "2010".to_string()),
2049 (6, "1103".to_string()),
2050 (7, "513".to_string()),
2051 (8, "377".to_string()),
2052 (9, "313".to_string()),
2053 (10, "255".to_string()),
2054 (11, "212".to_string()),
2055 (12, "193".to_string()),
2056 (13, "168".to_string()),
2057 (14, "143".to_string()),
2058 (15, "120".to_string()),
2059 (16, "ff".to_string())
2060 )), ( BigUint::from_slice([ 0xfff ]), vec!(
2061 (2, "111111111111".to_string()),
2062 (4, "333333".to_string()),
2063 (16, "fff".to_string())
2064 )), ( BigUint::from_slice([ 1, 2 ]), vec!(
2066 format!("10{}1", "0".repeat(bits - 1))),
2068 format!("2{}1", "0".repeat(bits / 2 - 1))),
2070 32 => "8589934593".to_string(),
2071 16 => "131073".to_string(),
2075 format!("2{}1", "0".repeat(bits / 4 - 1)))
2076 )), ( BigUint::from_slice([ 1, 2, 3 ]), vec!(
2078 format!("11{}10{}1",
2079 "0".repeat(bits - 2),
2080 "0".repeat(bits - 1))),
2083 "0".repeat(bits / 2 - 1),
2084 "0".repeat(bits / 2 - 1))),
2086 32 => "55340232229718589441".to_string(),
2087 16 => "12885032961".to_string(),
2092 "0".repeat(bits / 4 - 1),
2093 "0".repeat(bits / 4 - 1)))
2098 fn test_to_str_radix() {
2099 let r = to_str_pairs();
2100 for num_pair in r.iter() {
2101 let &(ref n, ref rs) = num_pair;
2102 for str_pair in rs.iter() {
2103 let &(ref radix, ref str) = str_pair;
2104 assert_eq!(n.to_str_radix(*radix).as_slice(),
2111 fn test_from_str_radix() {
2112 let r = to_str_pairs();
2113 for num_pair in r.iter() {
2114 let &(ref n, ref rs) = num_pair;
2115 for str_pair in rs.iter() {
2116 let &(ref radix, ref str) = str_pair;
2118 &FromStrRadix::from_str_radix(str.as_slice(),
2123 let zed: Option<BigUint> = FromStrRadix::from_str_radix("Z", 10);
2124 assert_eq!(zed, None);
2125 let blank: Option<BigUint> = FromStrRadix::from_str_radix("_", 2);
2126 assert_eq!(blank, None);
2127 let minus_one: Option<BigUint> = FromStrRadix::from_str_radix("-1",
2129 assert_eq!(minus_one, None);
2134 fn factor(n: uint) -> BigUint {
2135 let mut f: BigUint = One::one();
2136 for i in range(2, n + 1) {
2137 // FIXME(#5992): assignment operator overloads
2138 // f *= FromPrimitive::from_uint(i);
2139 f = f * FromPrimitive::from_uint(i).unwrap();
2144 fn check(n: uint, s: &str) {
2146 let ans = match FromStrRadix::from_str_radix(s, 10) {
2147 Some(x) => x, None => fail!()
2153 check(10, "3628800");
2154 check(20, "2432902008176640000");
2155 check(30, "265252859812191058636308480000000");
2160 assert_eq!(BigUint::new(vec!(0,0,0,0)).bits(), 0);
2161 let n: BigUint = FromPrimitive::from_uint(0).unwrap();
2162 assert_eq!(n.bits(), 0);
2163 let n: BigUint = FromPrimitive::from_uint(1).unwrap();
2164 assert_eq!(n.bits(), 1);
2165 let n: BigUint = FromPrimitive::from_uint(3).unwrap();
2166 assert_eq!(n.bits(), 2);
2167 let n: BigUint = FromStrRadix::from_str_radix("4000000000", 16).unwrap();
2168 assert_eq!(n.bits(), 39);
2169 let one: BigUint = One::one();
2170 assert_eq!((one << 426).bits(), 427);
2175 let mut rng = task_rng();
2176 let _n: BigUint = rng.gen_biguint(137);
2177 assert!(rng.gen_biguint(0).is_zero());
2181 fn test_rand_range() {
2182 let mut rng = task_rng();
2184 for _ in range(0, 10) {
2185 assert_eq!(rng.gen_bigint_range(&FromPrimitive::from_uint(236).unwrap(),
2186 &FromPrimitive::from_uint(237).unwrap()),
2187 FromPrimitive::from_uint(236).unwrap());
2190 let l = FromPrimitive::from_uint(403469000 + 2352).unwrap();
2191 let u = FromPrimitive::from_uint(403469000 + 3513).unwrap();
2192 for _ in range(0, 1000) {
2193 let n: BigUint = rng.gen_biguint_below(&u);
2196 let n: BigUint = rng.gen_biguint_range(&l, &u);
2204 fn test_zero_rand_range() {
2205 task_rng().gen_biguint_range(&FromPrimitive::from_uint(54).unwrap(),
2206 &FromPrimitive::from_uint(54).unwrap());
2211 fn test_negative_rand_range() {
2212 let mut rng = task_rng();
2213 let l = FromPrimitive::from_uint(2352).unwrap();
2214 let u = FromPrimitive::from_uint(3513).unwrap();
2215 // Switching u and l should fail:
2216 let _n: BigUint = rng.gen_biguint_range(&u, &l);
2223 use super::{BigDigit, BigUint, ToBigUint};
2224 use super::{Sign, Minus, Zero, Plus, BigInt, RandBigInt, ToBigInt};
2226 use std::cmp::{Less, Equal, Greater};
2228 use std::num::CheckedDiv;
2229 use std::num::{Zero, One, FromStrRadix, ToStrRadix};
2230 use std::num::{ToPrimitive, FromPrimitive};
2231 use std::rand::task_rng;
2235 fn test_from_biguint() {
2236 fn check(inp_s: Sign, inp_n: uint, ans_s: Sign, ans_n: uint) {
2237 let inp = BigInt::from_biguint(inp_s, FromPrimitive::from_uint(inp_n).unwrap());
2238 let ans = BigInt { sign: ans_s, data: FromPrimitive::from_uint(ans_n).unwrap()};
2239 assert_eq!(inp, ans);
2241 check(Plus, 1, Plus, 1);
2242 check(Plus, 0, Zero, 0);
2243 check(Minus, 1, Minus, 1);
2244 check(Zero, 1, Zero, 0);
2249 let vs = [ &[2 as BigDigit], &[1, 1], &[2, 1], &[1, 1, 1] ];
2250 let mut nums = Vec::new();
2251 for s in vs.iter().rev() {
2252 nums.push(BigInt::from_slice(Minus, *s));
2254 nums.push(Zero::zero());
2255 nums.extend(vs.iter().map(|s| BigInt::from_slice(Plus, *s)));
2257 for (i, ni) in nums.iter().enumerate() {
2258 for (j0, nj) in nums.slice(i, nums.len()).iter().enumerate() {
2261 assert_eq!(ni.cmp(nj), Equal);
2262 assert_eq!(nj.cmp(ni), Equal);
2264 assert!(!(ni != nj));
2267 assert!(!(ni < nj));
2268 assert!(!(ni > nj));
2270 assert_eq!(ni.cmp(nj), Less);
2271 assert_eq!(nj.cmp(ni), Greater);
2273 assert!(!(ni == nj));
2277 assert!(!(ni >= nj));
2279 assert!(!(ni > nj));
2281 assert!(!(nj <= ni));
2283 assert!(!(nj < ni));
2291 fn test_convert_i64() {
2292 fn check(b1: BigInt, i: i64) {
2293 let b2: BigInt = FromPrimitive::from_i64(i).unwrap();
2295 assert!(b1.to_i64().unwrap() == i);
2298 check(Zero::zero(), 0);
2299 check(One::one(), 1);
2300 check(i64::MIN.to_bigint().unwrap(), i64::MIN);
2301 check(i64::MAX.to_bigint().unwrap(), i64::MAX);
2304 (i64::MAX as u64 + 1).to_bigint().unwrap().to_i64(),
2308 BigInt::from_biguint(Plus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_i64(),
2312 BigInt::from_biguint(Minus, BigUint::new(vec!(1,0,0,1<<(BigDigit::bits-1)))).to_i64(),
2316 BigInt::from_biguint(Minus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_i64(),
2321 fn test_convert_u64() {
2322 fn check(b1: BigInt, u: u64) {
2323 let b2: BigInt = FromPrimitive::from_u64(u).unwrap();
2325 assert!(b1.to_u64().unwrap() == u);
2328 check(Zero::zero(), 0);
2329 check(One::one(), 1);
2330 check(u64::MIN.to_bigint().unwrap(), u64::MIN);
2331 check(u64::MAX.to_bigint().unwrap(), u64::MAX);
2334 BigInt::from_biguint(Plus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_u64(),
2337 let max_value: BigUint = FromPrimitive::from_u64(u64::MAX).unwrap();
2338 assert_eq!(BigInt::from_biguint(Minus, max_value).to_u64(), None);
2339 assert_eq!(BigInt::from_biguint(Minus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_u64(), None);
2343 fn test_convert_to_biguint() {
2344 fn check(n: BigInt, ans_1: BigUint) {
2345 assert_eq!(n.to_biguint().unwrap(), ans_1);
2346 assert_eq!(n.to_biguint().unwrap().to_bigint().unwrap(), n);
2348 let zero: BigInt = Zero::zero();
2349 let unsigned_zero: BigUint = Zero::zero();
2350 let positive = BigInt::from_biguint(
2351 Plus, BigUint::new(vec!(1,2,3)));
2352 let negative = -positive;
2354 check(zero, unsigned_zero);
2355 check(positive, BigUint::new(vec!(1,2,3)));
2357 assert_eq!(negative.to_biguint(), None);
2360 static sum_triples: &'static [(&'static [BigDigit],
2361 &'static [BigDigit],
2362 &'static [BigDigit])] = &[
2364 (&[], &[ 1], &[ 1]),
2365 (&[ 1], &[ 1], &[ 2]),
2366 (&[ 1], &[ 1, 1], &[ 2, 1]),
2367 (&[ 1], &[-1], &[ 0, 1]),
2368 (&[ 1], &[-1, -1], &[ 0, 0, 1]),
2369 (&[-1, -1], &[-1, -1], &[-2, -1, 1]),
2370 (&[ 1, 1, 1], &[-1, -1], &[ 0, 1, 2]),
2371 (&[ 2, 2, 1], &[-1, -2], &[ 1, 1, 2])
2376 for elm in sum_triples.iter() {
2377 let (a_vec, b_vec, c_vec) = *elm;
2378 let a = BigInt::from_slice(Plus, a_vec);
2379 let b = BigInt::from_slice(Plus, b_vec);
2380 let c = BigInt::from_slice(Plus, c_vec);
2382 assert!(a + b == c);
2383 assert!(b + a == c);
2384 assert!(c + (-a) == b);
2385 assert!(c + (-b) == a);
2386 assert!(a + (-c) == (-b));
2387 assert!(b + (-c) == (-a));
2388 assert!((-a) + (-b) == (-c))
2389 assert!(a + (-a) == Zero::zero());
2395 for elm in sum_triples.iter() {
2396 let (a_vec, b_vec, c_vec) = *elm;
2397 let a = BigInt::from_slice(Plus, a_vec);
2398 let b = BigInt::from_slice(Plus, b_vec);
2399 let c = BigInt::from_slice(Plus, c_vec);
2401 assert!(c - a == b);
2402 assert!(c - b == a);
2403 assert!((-b) - a == (-c))
2404 assert!((-a) - b == (-c))
2405 assert!(b - (-a) == c);
2406 assert!(a - (-b) == c);
2407 assert!((-c) - (-a) == (-b));
2408 assert!(a - a == Zero::zero());
2412 static mul_triples: &'static [(&'static [BigDigit],
2413 &'static [BigDigit],
2414 &'static [BigDigit])] = &[
2418 (&[ 1], &[ 1], &[1]),
2419 (&[ 2], &[ 3], &[ 6]),
2420 (&[ 1], &[ 1, 1, 1], &[1, 1, 1]),
2421 (&[ 1, 2, 3], &[ 3], &[ 3, 6, 9]),
2422 (&[ 1, 1, 1], &[-1], &[-1, -1, -1]),
2423 (&[ 1, 2, 3], &[-1], &[-1, -2, -2, 2]),
2424 (&[ 1, 2, 3, 4], &[-1], &[-1, -2, -2, -2, 3]),
2425 (&[-1], &[-1], &[ 1, -2]),
2426 (&[-1, -1], &[-1], &[ 1, -1, -2]),
2427 (&[-1, -1, -1], &[-1], &[ 1, -1, -1, -2]),
2428 (&[-1, -1, -1, -1], &[-1], &[ 1, -1, -1, -1, -2]),
2429 (&[-1/2 + 1], &[ 2], &[ 0, 1]),
2430 (&[0, -1/2 + 1], &[ 2], &[ 0, 0, 1]),
2431 (&[ 1, 2], &[ 1, 2, 3], &[1, 4, 7, 6]),
2432 (&[-1, -1], &[-1, -1, -1], &[1, 0, -1, -2, -1]),
2433 (&[-1, -1, -1], &[-1, -1, -1, -1], &[1, 0, 0, -1, -2, -1, -1]),
2434 (&[ 0, 0, 1], &[ 1, 2, 3], &[0, 0, 1, 2, 3]),
2435 (&[ 0, 0, 1], &[ 0, 0, 0, 1], &[0, 0, 0, 0, 0, 1])
2438 static div_rem_quadruples: &'static [(&'static [BigDigit],
2439 &'static [BigDigit],
2440 &'static [BigDigit],
2441 &'static [BigDigit])]
2443 (&[ 1], &[ 2], &[], &[1]),
2444 (&[ 1, 1], &[ 2], &[-1/2+1], &[1]),
2445 (&[ 1, 1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
2446 (&[ 0, 1], &[-1], &[1], &[1]),
2447 (&[-1, -1], &[-2], &[2, 1], &[3])
2452 for elm in mul_triples.iter() {
2453 let (a_vec, b_vec, c_vec) = *elm;
2454 let a = BigInt::from_slice(Plus, a_vec);
2455 let b = BigInt::from_slice(Plus, b_vec);
2456 let c = BigInt::from_slice(Plus, c_vec);
2458 assert!(a * b == c);
2459 assert!(b * a == c);
2461 assert!((-a) * b == -c);
2462 assert!((-b) * a == -c);
2465 for elm in div_rem_quadruples.iter() {
2466 let (a_vec, b_vec, c_vec, d_vec) = *elm;
2467 let a = BigInt::from_slice(Plus, a_vec);
2468 let b = BigInt::from_slice(Plus, b_vec);
2469 let c = BigInt::from_slice(Plus, c_vec);
2470 let d = BigInt::from_slice(Plus, d_vec);
2472 assert!(a == b * c + d);
2473 assert!(a == c * b + d);
2478 fn test_div_mod_floor() {
2479 fn check_sub(a: &BigInt, b: &BigInt, ans_d: &BigInt, ans_m: &BigInt) {
2480 let (d, m) = a.div_mod_floor(b);
2482 assert_eq!(m.sign, b.sign);
2484 assert!(m.abs() <= b.abs());
2485 assert!(*a == b * d + m);
2486 assert!(d == *ans_d);
2487 assert!(m == *ans_m);
2490 fn check(a: &BigInt, b: &BigInt, d: &BigInt, m: &BigInt) {
2492 check_sub(a, b, d, m);
2493 check_sub(a, &b.neg(), &d.neg(), m);
2494 check_sub(&a.neg(), b, &d.neg(), m);
2495 check_sub(&a.neg(), &b.neg(), d, m);
2497 check_sub(a, b, d, m);
2498 check_sub(a, &b.neg(), &(d.neg() - One::one()), &(m - *b));
2499 check_sub(&a.neg(), b, &(d.neg() - One::one()), &(b - *m));
2500 check_sub(&a.neg(), &b.neg(), d, &m.neg());
2504 for elm in mul_triples.iter() {
2505 let (a_vec, b_vec, c_vec) = *elm;
2506 let a = BigInt::from_slice(Plus, a_vec);
2507 let b = BigInt::from_slice(Plus, b_vec);
2508 let c = BigInt::from_slice(Plus, c_vec);
2510 if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
2511 if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
2514 for elm in div_rem_quadruples.iter() {
2515 let (a_vec, b_vec, c_vec, d_vec) = *elm;
2516 let a = BigInt::from_slice(Plus, a_vec);
2517 let b = BigInt::from_slice(Plus, b_vec);
2518 let c = BigInt::from_slice(Plus, c_vec);
2519 let d = BigInt::from_slice(Plus, d_vec);
2522 check(&a, &b, &c, &d);
2530 fn check_sub(a: &BigInt, b: &BigInt, ans_q: &BigInt, ans_r: &BigInt) {
2531 let (q, r) = a.div_rem(b);
2533 assert_eq!(r.sign, a.sign);
2535 assert!(r.abs() <= b.abs());
2536 assert!(*a == b * q + r);
2537 assert!(q == *ans_q);
2538 assert!(r == *ans_r);
2541 fn check(a: &BigInt, b: &BigInt, q: &BigInt, r: &BigInt) {
2542 check_sub(a, b, q, r);
2543 check_sub(a, &b.neg(), &q.neg(), r);
2544 check_sub(&a.neg(), b, &q.neg(), &r.neg());
2545 check_sub(&a.neg(), &b.neg(), q, &r.neg());
2547 for elm in mul_triples.iter() {
2548 let (a_vec, b_vec, c_vec) = *elm;
2549 let a = BigInt::from_slice(Plus, a_vec);
2550 let b = BigInt::from_slice(Plus, b_vec);
2551 let c = BigInt::from_slice(Plus, c_vec);
2553 if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
2554 if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
2557 for elm in div_rem_quadruples.iter() {
2558 let (a_vec, b_vec, c_vec, d_vec) = *elm;
2559 let a = BigInt::from_slice(Plus, a_vec);
2560 let b = BigInt::from_slice(Plus, b_vec);
2561 let c = BigInt::from_slice(Plus, c_vec);
2562 let d = BigInt::from_slice(Plus, d_vec);
2565 check(&a, &b, &c, &d);
2571 fn test_checked_add() {
2572 for elm in sum_triples.iter() {
2573 let (aVec, bVec, cVec) = *elm;
2574 let a = BigInt::from_slice(Plus, aVec);
2575 let b = BigInt::from_slice(Plus, bVec);
2576 let c = BigInt::from_slice(Plus, cVec);
2578 assert!(a.checked_add(&b).unwrap() == c);
2579 assert!(b.checked_add(&a).unwrap() == c);
2580 assert!(c.checked_add(&(-a)).unwrap() == b);
2581 assert!(c.checked_add(&(-b)).unwrap() == a);
2582 assert!(a.checked_add(&(-c)).unwrap() == (-b));
2583 assert!(b.checked_add(&(-c)).unwrap() == (-a));
2584 assert!((-a).checked_add(&(-b)).unwrap() == (-c))
2585 assert!(a.checked_add(&(-a)).unwrap() == Zero::zero());
2590 fn test_checked_sub() {
2591 for elm in sum_triples.iter() {
2592 let (aVec, bVec, cVec) = *elm;
2593 let a = BigInt::from_slice(Plus, aVec);
2594 let b = BigInt::from_slice(Plus, bVec);
2595 let c = BigInt::from_slice(Plus, cVec);
2597 assert!(c.checked_sub(&a).unwrap() == b);
2598 assert!(c.checked_sub(&b).unwrap() == a);
2599 assert!((-b).checked_sub(&a).unwrap() == (-c))
2600 assert!((-a).checked_sub(&b).unwrap() == (-c))
2601 assert!(b.checked_sub(&(-a)).unwrap() == c);
2602 assert!(a.checked_sub(&(-b)).unwrap() == c);
2603 assert!((-c).checked_sub(&(-a)).unwrap() == (-b));
2604 assert!(a.checked_sub(&a).unwrap() == Zero::zero());
2609 fn test_checked_mul() {
2610 for elm in mul_triples.iter() {
2611 let (aVec, bVec, cVec) = *elm;
2612 let a = BigInt::from_slice(Plus, aVec);
2613 let b = BigInt::from_slice(Plus, bVec);
2614 let c = BigInt::from_slice(Plus, cVec);
2616 assert!(a.checked_mul(&b).unwrap() == c);
2617 assert!(b.checked_mul(&a).unwrap() == c);
2619 assert!((-a).checked_mul(&b).unwrap() == -c);
2620 assert!((-b).checked_mul(&a).unwrap() == -c);
2623 for elm in div_rem_quadruples.iter() {
2624 let (aVec, bVec, cVec, dVec) = *elm;
2625 let a = BigInt::from_slice(Plus, aVec);
2626 let b = BigInt::from_slice(Plus, bVec);
2627 let c = BigInt::from_slice(Plus, cVec);
2628 let d = BigInt::from_slice(Plus, dVec);
2630 assert!(a == b.checked_mul(&c).unwrap() + d);
2631 assert!(a == c.checked_mul(&b).unwrap() + d);
2635 fn test_checked_div() {
2636 for elm in mul_triples.iter() {
2637 let (aVec, bVec, cVec) = *elm;
2638 let a = BigInt::from_slice(Plus, aVec);
2639 let b = BigInt::from_slice(Plus, bVec);
2640 let c = BigInt::from_slice(Plus, cVec);
2643 assert!(c.checked_div(&a).unwrap() == b);
2644 assert!((-c).checked_div(&(-a)).unwrap() == b);
2645 assert!((-c).checked_div(&a).unwrap() == -b);
2648 assert!(c.checked_div(&b).unwrap() == a);
2649 assert!((-c).checked_div(&(-b)).unwrap() == a);
2650 assert!((-c).checked_div(&b).unwrap() == -a);
2653 assert!(c.checked_div(&Zero::zero()).is_none());
2654 assert!((-c).checked_div(&Zero::zero()).is_none());
2660 fn check(a: int, b: int, c: int) {
2661 let big_a: BigInt = FromPrimitive::from_int(a).unwrap();
2662 let big_b: BigInt = FromPrimitive::from_int(b).unwrap();
2663 let big_c: BigInt = FromPrimitive::from_int(c).unwrap();
2665 assert_eq!(big_a.gcd(&big_b), big_c);
2680 fn check(a: int, b: int, c: int) {
2681 let big_a: BigInt = FromPrimitive::from_int(a).unwrap();
2682 let big_b: BigInt = FromPrimitive::from_int(b).unwrap();
2683 let big_c: BigInt = FromPrimitive::from_int(c).unwrap();
2685 assert_eq!(big_a.lcm(&big_b), big_c);
2700 let zero: BigInt = Zero::zero();
2701 let one: BigInt = One::one();
2702 assert_eq!((-one).abs_sub(&one), zero);
2703 let one: BigInt = One::one();
2704 let zero: BigInt = Zero::zero();
2705 assert_eq!(one.abs_sub(&one), zero);
2706 let one: BigInt = One::one();
2707 let zero: BigInt = Zero::zero();
2708 assert_eq!(one.abs_sub(&zero), one);
2709 let one: BigInt = One::one();
2710 let two: BigInt = FromPrimitive::from_int(2).unwrap();
2711 assert_eq!(one.abs_sub(&-one), two);
2715 fn test_to_str_radix() {
2716 fn check(n: int, ans: &str) {
2717 let n: BigInt = FromPrimitive::from_int(n).unwrap();
2718 assert!(ans == n.to_str_radix(10).as_slice());
2729 fn test_from_str_radix() {
2730 fn check(s: &str, ans: Option<int>) {
2731 let ans = ans.map(|n| {
2732 let x: BigInt = FromPrimitive::from_int(n).unwrap();
2735 assert_eq!(FromStrRadix::from_str_radix(s, 10), ans);
2737 check("10", Some(10));
2738 check("1", Some(1));
2739 check("0", Some(0));
2740 check("-1", Some(-1));
2741 check("-10", Some(-10));
2745 // issue 10522, this hit an edge case that caused it to
2746 // attempt to allocate a vector of size (-1u) == huge.
2748 from_str(format!("1{}", "0".repeat(36)).as_slice()).unwrap();
2749 let _y = x.to_str();
2754 assert!(-BigInt::new(Plus, vec!(1, 1, 1)) ==
2755 BigInt::new(Minus, vec!(1, 1, 1)));
2756 assert!(-BigInt::new(Minus, vec!(1, 1, 1)) ==
2757 BigInt::new(Plus, vec!(1, 1, 1)));
2758 let zero: BigInt = Zero::zero();
2759 assert_eq!(-zero, zero);
2764 let mut rng = task_rng();
2765 let _n: BigInt = rng.gen_bigint(137);
2766 assert!(rng.gen_bigint(0).is_zero());
2770 fn test_rand_range() {
2771 let mut rng = task_rng();
2773 for _ in range(0, 10) {
2774 assert_eq!(rng.gen_bigint_range(&FromPrimitive::from_uint(236).unwrap(),
2775 &FromPrimitive::from_uint(237).unwrap()),
2776 FromPrimitive::from_uint(236).unwrap());
2779 fn check(l: BigInt, u: BigInt) {
2780 let mut rng = task_rng();
2781 for _ in range(0, 1000) {
2782 let n: BigInt = rng.gen_bigint_range(&l, &u);
2787 let l: BigInt = FromPrimitive::from_uint(403469000 + 2352).unwrap();
2788 let u: BigInt = FromPrimitive::from_uint(403469000 + 3513).unwrap();
2789 check( l.clone(), u.clone());
2790 check(-l.clone(), u.clone());
2791 check(-u.clone(), -l.clone());
2796 fn test_zero_rand_range() {
2797 task_rng().gen_bigint_range(&FromPrimitive::from_int(54).unwrap(),
2798 &FromPrimitive::from_int(54).unwrap());
2803 fn test_negative_rand_range() {
2804 let mut rng = task_rng();
2805 let l = FromPrimitive::from_uint(2352).unwrap();
2806 let u = FromPrimitive::from_uint(3513).unwrap();
2807 // Switching u and l should fail:
2808 let _n: BigInt = rng.gen_bigint_range(&u, &l);
2815 use self::test::Bencher;
2818 use std::mem::replace;
2819 use std::num::{FromPrimitive, Zero, One};
2821 fn factorial(n: uint) -> BigUint {
2822 let mut f: BigUint = One::one();
2823 for i in iter::range_inclusive(1, n) {
2824 f = f * FromPrimitive::from_uint(i).unwrap();
2829 fn fib(n: uint) -> BigUint {
2830 let mut f0: BigUint = Zero::zero();
2831 let mut f1: BigUint = One::one();
2832 for _ in range(0, n) {
2834 f0 = replace(&mut f1, f2);
2840 fn factorial_100(b: &mut Bencher) {
2847 fn fib_100(b: &mut Bencher) {
2854 fn to_str(b: &mut Bencher) {
2855 let fac = factorial(100);
2866 fn shr(b: &mut Bencher) {
2867 let n = { let one : BigUint = One::one(); one << 1000 };
2869 let mut m = n.clone();
2870 for _ in range(0, 10) {