src/libnum/bigint.rs

   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.
   4 //
   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.
  10
  11 //! A Big integer (signed version: `BigInt`, unsigned version: `BigUint`).
  12 //!
  13 //! A `BigUint` is represented as an array of `BigDigit`s.
  14 //! A `BigInt` is a combination of `BigUint` and `Sign`.
  15 //!
  16 //! Common numerical operations are overloaded, so we can treat them
  17 //! the same way we treat other numbers.
  18 //!
  19 //! ## Example
  20 //!
  21 //! ```rust
  22 //! # #![allow(deprecated)]
  23 //! use num::bigint::BigUint;
  24 //! use std::num::{Zero, One};
  25 //! use std::mem::replace;
  26 //!
  27 //! // Calculate large fibonacci numbers.
  28 //! fn fib(n: uint) -> BigUint {
  29 //!     let mut f0: BigUint = Zero::zero();
  30 //!     let mut f1: BigUint = One::one();
  31 //!     for _ in range(0, n) {
  32 //!         let f2 = f0 + f1;
  33 //!         // This is a low cost way of swapping f0 with f1 and f1 with f2.
  34 //!         f0 = replace(&mut f1, f2);
  35 //!     }
  36 //!     f0
  37 //! }
  38 //!
  39 //! // This is a very large number.
  40 //! println!("fib(1000) = {}", fib(1000));
  41 //! ```
  42 //!
  43 //! It's easy to generate large random numbers:
  44 //!
  45 //! ```rust
  46 //! # #![allow(deprecated)]
  47 //! use num::bigint::{ToBigInt, RandBigInt};
  48 //! use std::rand;
  49 //!
  50 //! let mut rng = rand::task_rng();
  51 //! let a = rng.gen_bigint(1000u);
  52 //!
  53 //! let low = -10000i.to_bigint().unwrap();
  54 //! let high = 10000i.to_bigint().unwrap();
  55 //! let b = rng.gen_bigint_range(&low, &high);
  56 //!
  57 //! // Probably an even larger number.
  58 //! println!("{}", a * b);
  59 //! ```
  60
  61 use Integer;
  62 use rand::Rng;
  63
  64 use std::{cmp, fmt, hash};
  65 use std::default::Default;
  66 use std::from_str::FromStr;
  67 use std::num::CheckedDiv;
  68 use std::num::{ToPrimitive, FromPrimitive};
  69 use std::num::{Zero, One, ToStrRadix, FromStrRadix};
  70 use std::string::String;
  71 use std::{uint, i64, u64};
  72
  73 /// A `BigDigit` is a `BigUint`'s composing element.
  74 pub type BigDigit = u32;
  75
  76 /// A `DoubleBigDigit` is the internal type used to do the computations.  Its
  77 /// size is the double of the size of `BigDigit`.
  78 pub type DoubleBigDigit = u64;
  79
  80 pub static ZERO_BIG_DIGIT: BigDigit = 0;
  81 static ZERO_VEC: [BigDigit, ..1] = [ZERO_BIG_DIGIT];
  82
  83 #[allow(non_snake_case)]
  84 pub mod BigDigit {
  85     use super::BigDigit;
  86     use super::DoubleBigDigit;
  87
  88     // `DoubleBigDigit` size dependent
  89     pub static bits: uint = 32;
  90
  91     pub static base: DoubleBigDigit = 1 << bits;
  92     static lo_mask: DoubleBigDigit = (-1 as DoubleBigDigit) >> bits;
  93
  94     #[inline]
  95     fn get_hi(n: DoubleBigDigit) -> BigDigit { (n >> bits) as BigDigit }
  96     #[inline]
  97     fn get_lo(n: DoubleBigDigit) -> BigDigit { (n & lo_mask) as BigDigit }
  98
  99     /// Split one `DoubleBigDigit` into two `BigDigit`s.
 100     #[inline]
 101     pub fn from_doublebigdigit(n: DoubleBigDigit) -> (BigDigit, BigDigit) {
 102         (get_hi(n), get_lo(n))
 103     }
 104
 105     /// Join two `BigDigit`s into one `DoubleBigDigit`
 106     #[inline]
 107     pub fn to_doublebigdigit(hi: BigDigit, lo: BigDigit) -> DoubleBigDigit {
 108         (lo as DoubleBigDigit) | ((hi as DoubleBigDigit) << bits)
 109     }
 110 }
 111
 112 /// A big unsigned integer type.
 113 ///
 114 /// A `BigUint`-typed value `BigUint { data: vec!(a, b, c) }` represents a number
 115 /// `(a + b * BigDigit::base + c * BigDigit::base^2)`.
 116 #[deriving(Clone)]
 117 pub struct BigUint {
 118     data: Vec<BigDigit>
 119 }
 120
 121 impl PartialEq for BigUint {
 122     #[inline]
 123     fn eq(&self, other: &BigUint) -> bool {
 124         match self.cmp(other) { Equal => true, _ => false }
 125     }
 126 }
 127 impl Eq for BigUint {}
 128
 129 impl PartialOrd for BigUint {
 130     #[inline]
 131     fn partial_cmp(&self, other: &BigUint) -> Option<Ordering> {
 132         Some(self.cmp(other))
 133     }
 134 }
 135
 136 impl Ord for BigUint {
 137     #[inline]
 138     fn cmp(&self, other: &BigUint) -> Ordering {
 139         let (s_len, o_len) = (self.data.len(), other.data.len());
 140         if s_len < o_len { return Less; }
 141         if s_len > o_len { return Greater;  }
 142
 143         for (&self_i, &other_i) in self.data.iter().rev().zip(other.data.iter().rev()) {
 144             if self_i < other_i { return Less; }
 145             if self_i > other_i { return Greater; }
 146         }
 147         return Equal;
 148     }
 149 }
 150
 151 impl Default for BigUint {
 152     #[inline]
 153     fn default() -> BigUint { Zero::zero() }
 154 }
 155
 156 impl<S: hash::Writer> hash::Hash<S> for BigUint {
 157     fn hash(&self, state: &mut S) {
 158         // hash 0 in case it's all 0's
 159         0u32.hash(state);
 160
 161         let mut found_first_value = false;
 162         for elem in self.data.iter().rev() {
 163             // don't hash any leading 0's, they shouldn't affect the hash
 164             if found_first_value || *elem != 0 {
 165                 found_first_value = true;
 166                 elem.hash(state);
 167             }
 168         }
 169     }
 170 }
 171
 172 impl fmt::Show for BigUint {
 173     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 174         write!(f, "{}", self.to_str_radix(10))
 175     }
 176 }
 177
 178 impl FromStr for BigUint {
 179     #[inline]
 180     fn from_str(s: &str) -> Option<BigUint> {
 181         FromStrRadix::from_str_radix(s, 10)
 182     }
 183 }
 184
 185 impl Num for BigUint {}
 186
 187 impl BitAnd<BigUint, BigUint> for BigUint {
 188     fn bitand(&self, other: &BigUint) -> BigUint {
 189         BigUint::new(self.data.iter().zip(other.data.iter()).map(|(ai, bi)| *ai & *bi).collect())
 190     }
 191 }
 192
 193 impl BitOr<BigUint, BigUint> for BigUint {
 194     fn bitor(&self, other: &BigUint) -> BigUint {
 195         let zeros = ZERO_VEC.iter().cycle();
 196         let (a, b) = if self.data.len() > other.data.len() { (self, other) } else { (other, self) };
 197         let ored = a.data.iter().zip(b.data.iter().chain(zeros)).map(
 198             |(ai, bi)| *ai | *bi
 199         ).collect();
 200         return BigUint::new(ored);
 201     }
 202 }
 203
 204 impl BitXor<BigUint, BigUint> for BigUint {
 205     fn bitxor(&self, other: &BigUint) -> BigUint {
 206         let zeros = ZERO_VEC.iter().cycle();
 207         let (a, b) = if self.data.len() > other.data.len() { (self, other) } else { (other, self) };
 208         let xored = a.data.iter().zip(b.data.iter().chain(zeros)).map(
 209             |(ai, bi)| *ai ^ *bi
 210         ).collect();
 211         return BigUint::new(xored);
 212     }
 213 }
 214
 215 impl Shl<uint, BigUint> for BigUint {
 216     #[inline]
 217     fn shl(&self, rhs: &uint) -> BigUint {
 218         let n_unit = *rhs / BigDigit::bits;
 219         let n_bits = *rhs % BigDigit::bits;
 220         return self.shl_unit(n_unit).shl_bits(n_bits);
 221     }
 222 }
 223
 224 impl Shr<uint, BigUint> for BigUint {
 225     #[inline]
 226     fn shr(&self, rhs: &uint) -> BigUint {
 227         let n_unit = *rhs / BigDigit::bits;
 228         let n_bits = *rhs % BigDigit::bits;
 229         return self.shr_unit(n_unit).shr_bits(n_bits);
 230     }
 231 }
 232
 233 impl Zero for BigUint {
 234     #[inline]
 235     fn zero() -> BigUint { BigUint::new(Vec::new()) }
 236
 237     #[inline]
 238     fn is_zero(&self) -> bool { self.data.is_empty() }
 239 }
 240
 241 impl One for BigUint {
 242     #[inline]
 243     fn one() -> BigUint { BigUint::new(vec!(1)) }
 244 }
 245
 246 impl Unsigned for BigUint {}
 247
 248 impl Add<BigUint, BigUint> for BigUint {
 249     fn add(&self, other: &BigUint) -> BigUint {
 250         let zeros = ZERO_VEC.iter().cycle();
 251         let (a, b) = if self.data.len() > other.data.len() { (self, other) } else { (other, self) };
 252
 253         let mut carry = 0;
 254         let mut sum: Vec<BigDigit> =  a.data.iter().zip(b.data.iter().chain(zeros)).map(|(ai, bi)| {
 255             let (hi, lo) = BigDigit::from_doublebigdigit(
 256                 (*ai as DoubleBigDigit) + (*bi as DoubleBigDigit) + (carry as DoubleBigDigit));
 257             carry = hi;
 258             lo
 259         }).collect();
 260         if carry != 0 { sum.push(carry); }
 261         return BigUint::new(sum);
 262     }
 263 }
 264
 265 impl Sub<BigUint, BigUint> for BigUint {
 266     fn sub(&self, other: &BigUint) -> BigUint {
 267         let new_len = cmp::max(self.data.len(), other.data.len());
 268         let zeros = ZERO_VEC.iter().cycle();
 269         let (a, b) = (self.data.iter().chain(zeros.clone()), other.data.iter().chain(zeros));
 270
 271         let mut borrow = 0i;
 272         let diff: Vec<BigDigit> =  a.take(new_len).zip(b).map(|(ai, bi)| {
 273             let (hi, lo) = BigDigit::from_doublebigdigit(
 274                 BigDigit::base
 275                     + (*ai as DoubleBigDigit)
 276                     - (*bi as DoubleBigDigit)
 277                     - (borrow as DoubleBigDigit)
 278             );
 279             /*
 280             hi * (base) + lo == 1*(base) + ai - bi - borrow
 281             => ai - bi - borrow < 0 <=> hi == 0
 282             */
 283             borrow = if hi == 0 { 1 } else { 0 };
 284             lo
 285         }).collect();
 286
 287         assert!(borrow == 0,
 288                 "Cannot subtract other from self because other is larger than self.");
 289         return BigUint::new(diff);
 290     }
 291 }
 292
 293 impl Mul<BigUint, BigUint> for BigUint {
 294     fn mul(&self, other: &BigUint) -> BigUint {
 295         if self.is_zero() || other.is_zero() { return Zero::zero(); }
 296
 297         let (s_len, o_len) = (self.data.len(), other.data.len());
 298         if s_len == 1 { return mul_digit(other, self.data.as_slice()[0]);  }
 299         if o_len == 1 { return mul_digit(self,  other.data.as_slice()[0]); }
 300
 301         // Using Karatsuba multiplication
 302         // (a1 * base + a0) * (b1 * base + b0)
 303         // = a1*b1 * base^2 +
 304         //   (a1*b1 + a0*b0 - (a1-b0)*(b1-a0)) * base +
 305         //   a0*b0
 306         let half_len = cmp::max(s_len, o_len) / 2;
 307         let (s_hi, s_lo) = cut_at(self,  half_len);
 308         let (o_hi, o_lo) = cut_at(other, half_len);
 309
 310         let ll = s_lo * o_lo;
 311         let hh = s_hi * o_hi;
 312         let mm = {
 313             let (s1, n1) = sub_sign(s_hi, s_lo);
 314             let (s2, n2) = sub_sign(o_hi, o_lo);
 315             match (s1, s2) {
 316                 (Equal, _) | (_, Equal) => hh + ll,
 317                 (Less, Greater) | (Greater, Less) => hh + ll + (n1 * n2),
 318                 (Less, Less) | (Greater, Greater) => hh + ll - (n1 * n2)
 319             }
 320         };
 321
 322         return ll + mm.shl_unit(half_len) + hh.shl_unit(half_len * 2);
 323
 324
 325         fn mul_digit(a: &BigUint, n: BigDigit) -> BigUint {
 326             if n == 0 { return Zero::zero(); }
 327             if n == 1 { return (*a).clone(); }
 328
 329             let mut carry = 0;
 330             let mut prod: Vec<BigDigit> = a.data.iter().map(|ai| {
 331                 let (hi, lo) = BigDigit::from_doublebigdigit(
 332                     (*ai as DoubleBigDigit) * (n as DoubleBigDigit) + (carry as DoubleBigDigit)
 333                 );
 334                 carry = hi;
 335                 lo
 336             }).collect();
 337             if carry != 0 { prod.push(carry); }
 338             return BigUint::new(prod);
 339         }
 340
 341         #[inline]
 342         fn cut_at(a: &BigUint, n: uint) -> (BigUint, BigUint) {
 343             let mid = cmp::min(a.data.len(), n);
 344             return (BigUint::from_slice(a.data.slice(mid, a.data.len())),
 345                     BigUint::from_slice(a.data.slice(0, mid)));
 346         }
 347
 348         #[inline]
 349         fn sub_sign(a: BigUint, b: BigUint) -> (Ordering, BigUint) {
 350             match a.cmp(&b) {
 351                 Less    => (Less,    b - a),
 352                 Greater => (Greater, a - b),
 353                 _       => (Equal,   Zero::zero())
 354             }
 355         }
 356     }
 357 }
 358
 359 impl Div<BigUint, BigUint> for BigUint {
 360     #[inline]
 361     fn div(&self, other: &BigUint) -> BigUint {
 362         let (q, _) = self.div_rem(other);
 363         return q;
 364     }
 365 }
 366
 367 impl Rem<BigUint, BigUint> for BigUint {
 368     #[inline]
 369     fn rem(&self, other: &BigUint) -> BigUint {
 370         let (_, r) = self.div_rem(other);
 371         return r;
 372     }
 373 }
 374
 375 impl Neg<BigUint> for BigUint {
 376     #[inline]
 377     fn neg(&self) -> BigUint { fail!() }
 378 }
 379
 380 impl CheckedAdd for BigUint {
 381     #[inline]
 382     fn checked_add(&self, v: &BigUint) -> Option<BigUint> {
 383         return Some(self.add(v));
 384     }
 385 }
 386
 387 impl CheckedSub for BigUint {
 388     #[inline]
 389     fn checked_sub(&self, v: &BigUint) -> Option<BigUint> {
 390         if *self < *v {
 391             return None;
 392         }
 393         return Some(self.sub(v));
 394     }
 395 }
 396
 397 impl CheckedMul for BigUint {
 398     #[inline]
 399     fn checked_mul(&self, v: &BigUint) -> Option<BigUint> {
 400         return Some(self.mul(v));
 401     }
 402 }
 403
 404 impl CheckedDiv for BigUint {
 405     #[inline]
 406     fn checked_div(&self, v: &BigUint) -> Option<BigUint> {
 407         if v.is_zero() {
 408             return None;
 409         }
 410         return Some(self.div(v));
 411     }
 412 }
 413
 414 impl Integer for BigUint {
 415     #[inline]
 416     fn div_rem(&self, other: &BigUint) -> (BigUint, BigUint) {
 417         self.div_mod_floor(other)
 418     }
 419
 420     #[inline]
 421     fn div_floor(&self, other: &BigUint) -> BigUint {
 422         let (d, _) = self.div_mod_floor(other);
 423         return d;
 424     }
 425
 426     #[inline]
 427     fn mod_floor(&self, other: &BigUint) -> BigUint {
 428         let (_, m) = self.div_mod_floor(other);
 429         return m;
 430     }
 431
 432     fn div_mod_floor(&self, other: &BigUint) -> (BigUint, BigUint) {
 433         if other.is_zero() { fail!() }
 434         if self.is_zero() { return (Zero::zero(), Zero::zero()); }
 435         if *other == One::one() { return ((*self).clone(), Zero::zero()); }
 436
 437         match self.cmp(other) {
 438             Less    => return (Zero::zero(), (*self).clone()),
 439             Equal   => return (One::one(), Zero::zero()),
 440             Greater => {} // Do nothing
 441         }
 442
 443         let mut shift = 0;
 444         let mut n = *other.data.last().unwrap();
 445         while n < (1 << BigDigit::bits - 2) {
 446             n <<= 1;
 447             shift += 1;
 448         }
 449         assert!(shift < BigDigit::bits);
 450         let (d, m) = div_mod_floor_inner(self << shift, other << shift);
 451         return (d, m >> shift);
 452
 453
 454         fn div_mod_floor_inner(a: BigUint, b: BigUint) -> (BigUint, BigUint) {
 455             let mut m = a;
 456             let mut d: BigUint = Zero::zero();
 457             let mut n = 1;
 458             while m >= b {
 459                 let (d0, d_unit, b_unit) = div_estimate(&m, &b, n);
 460                 let mut d0 = d0;
 461                 let mut prod = b * d0;
 462                 while prod > m {
 463                     // FIXME(#5992): assignment operator overloads
 464                     // d0 -= d_unit
 465                     d0   = d0 - d_unit;
 466                     // FIXME(#5992): assignment operator overloads
 467                     // prod -= b_unit;
 468                     prod = prod - b_unit
 469                 }
 470                 if d0.is_zero() {
 471                     n = 2;
 472                     continue;
 473                 }
 474                 n = 1;
 475                 // FIXME(#5992): assignment operator overloads
 476                 // d += d0;
 477                 d = d + d0;
 478                 // FIXME(#5992): assignment operator overloads
 479                 // m -= prod;
 480                 m = m - prod;
 481             }
 482             return (d, m);
 483         }
 484
 485
 486         fn div_estimate(a: &BigUint, b: &BigUint, n: uint)
 487             -> (BigUint, BigUint, BigUint) {
 488             if a.data.len() < n {
 489                 return (Zero::zero(), Zero::zero(), (*a).clone());
 490             }
 491
 492             let an = a.data.tailn(a.data.len() - n);
 493             let bn = *b.data.last().unwrap();
 494             let mut d = Vec::with_capacity(an.len());
 495             let mut carry = 0;
 496             for elt in an.iter().rev() {
 497                 let ai = BigDigit::to_doublebigdigit(carry, *elt);
 498                 let di = ai / (bn as DoubleBigDigit);
 499                 assert!(di < BigDigit::base);
 500                 carry = (ai % (bn as DoubleBigDigit)) as BigDigit;
 501                 d.push(di as BigDigit)
 502             }
 503             d.reverse();
 504
 505             let shift = (a.data.len() - an.len()) - (b.data.len() - 1);
 506             if shift == 0 {
 507                 return (BigUint::new(d), One::one(), (*b).clone());
 508             }
 509             let one: BigUint = One::one();
 510             return (BigUint::new(d).shl_unit(shift),
 511                     one.shl_unit(shift),
 512                     b.shl_unit(shift));
 513         }
 514     }
 515
 516     /// Calculates the Greatest Common Divisor (GCD) of the number and `other`.
 517     ///
 518     /// The result is always positive.
 519     #[inline]
 520     fn gcd(&self, other: &BigUint) -> BigUint {
 521         // Use Euclid's algorithm
 522         let mut m = (*self).clone();
 523         let mut n = (*other).clone();
 524         while !m.is_zero() {
 525             let temp = m;
 526             m = n % temp;
 527             n = temp;
 528         }
 529         return n;
 530     }
 531
 532     /// Calculates the Lowest Common Multiple (LCM) of the number and `other`.
 533     #[inline]
 534     fn lcm(&self, other: &BigUint) -> BigUint { ((*self * *other) / self.gcd(other)) }
 535
 536     /// Deprecated, use `is_multiple_of` instead.
 537     #[deprecated = "function renamed to `is_multiple_of`"]
 538     #[inline]
 539     fn divides(&self, other: &BigUint) -> bool { return self.is_multiple_of(other); }
 540
 541     /// Returns `true` if the number is a multiple of `other`.
 542     #[inline]
 543     fn is_multiple_of(&self, other: &BigUint) -> bool { (*self % *other).is_zero() }
 544
 545     /// Returns `true` if the number is divisible by `2`.
 546     #[inline]
 547     fn is_even(&self) -> bool {
 548         // Considering only the last digit.
 549         match self.data.as_slice().head() {
 550             Some(x) => x.is_even(),
 551             None => true
 552         }
 553     }
 554
 555     /// Returns `true` if the number is not divisible by `2`.
 556     #[inline]
 557     fn is_odd(&self) -> bool { !self.is_even() }
 558 }
 559
 560 impl ToPrimitive for BigUint {
 561     #[inline]
 562     fn to_i64(&self) -> Option<i64> {
 563         self.to_u64().and_then(|n| {
 564             // If top bit of u64 is set, it's too large to convert to i64.
 565             if n >> 63 == 0 {
 566                 Some(n as i64)
 567             } else {
 568                 None
 569             }
 570         })
 571     }
 572
 573     // `DoubleBigDigit` size dependent
 574     #[inline]
 575     fn to_u64(&self) -> Option<u64> {
 576         match self.data.len() {
 577             0 => Some(0),
 578             1 => Some(self.data.as_slice()[0] as u64),
 579             2 => Some(BigDigit::to_doublebigdigit(self.data.as_slice()[1], self.data.as_slice()[0])
 580                       as u64),
 581             _ => None
 582         }
 583     }
 584 }
 585
 586 impl FromPrimitive for BigUint {
 587     #[inline]
 588     fn from_i64(n: i64) -> Option<BigUint> {
 589         if n > 0 {
 590             FromPrimitive::from_u64(n as u64)
 591         } else if n == 0 {
 592             Some(Zero::zero())
 593         } else {
 594             None
 595         }
 596     }
 597
 598     // `DoubleBigDigit` size dependent
 599     #[inline]
 600     fn from_u64(n: u64) -> Option<BigUint> {
 601         let n = match BigDigit::from_doublebigdigit(n) {
 602             (0,  0)  => Zero::zero(),
 603             (0,  n0) => BigUint::new(vec!(n0)),
 604             (n1, n0) => BigUint::new(vec!(n0, n1))
 605         };
 606         Some(n)
 607     }
 608 }
 609
 610 /// A generic trait for converting a value to a `BigUint`.
 611 pub trait ToBigUint {
 612     /// Converts the value of `self` to a `BigUint`.
 613     fn to_biguint(&self) -> Option<BigUint>;
 614 }
 615
 616 impl ToBigUint for BigInt {
 617     #[inline]
 618     fn to_biguint(&self) -> Option<BigUint> {
 619         if self.sign == Plus {
 620             Some(self.data.clone())
 621         } else if self.sign == Zero {
 622             Some(Zero::zero())
 623         } else {
 624             None
 625         }
 626     }
 627 }
 628
 629 impl ToBigUint for BigUint {
 630     #[inline]
 631     fn to_biguint(&self) -> Option<BigUint> {
 632         Some(self.clone())
 633     }
 634 }
 635
 636 macro_rules! impl_to_biguint(
 637     ($T:ty, $from_ty:path) => {
 638         impl ToBigUint for $T {
 639             #[inline]
 640             fn to_biguint(&self) -> Option<BigUint> {
 641                 $from_ty(*self)
 642             }
 643         }
 644     }
 645 )
 646
 647 impl_to_biguint!(int,  FromPrimitive::from_int)
 648 impl_to_biguint!(i8,   FromPrimitive::from_i8)
 649 impl_to_biguint!(i16,  FromPrimitive::from_i16)
 650 impl_to_biguint!(i32,  FromPrimitive::from_i32)
 651 impl_to_biguint!(i64,  FromPrimitive::from_i64)
 652 impl_to_biguint!(uint, FromPrimitive::from_uint)
 653 impl_to_biguint!(u8,   FromPrimitive::from_u8)
 654 impl_to_biguint!(u16,  FromPrimitive::from_u16)
 655 impl_to_biguint!(u32,  FromPrimitive::from_u32)
 656 impl_to_biguint!(u64,  FromPrimitive::from_u64)
 657
 658 impl ToStrRadix for BigUint {
 659     fn to_str_radix(&self, radix: uint) -> String {
 660         assert!(1 < radix && radix <= 16, "The radix must be within (1, 16]");
 661         let (base, max_len) = get_radix_base(radix);
 662         if base == BigDigit::base {
 663             return fill_concat(self.data.as_slice(), radix, max_len)
 664         }
 665         return fill_concat(convert_base(self, base).as_slice(), radix, max_len);
 666
 667         fn convert_base(n: &BigUint, base: DoubleBigDigit) -> Vec<BigDigit> {
 668             let divider    = base.to_biguint().unwrap();
 669             let mut result = Vec::new();
 670             let mut m      = n.clone();
 671             while m >= divider {
 672                 let (d, m0) = m.div_mod_floor(&divider);
 673                 result.push(m0.to_uint().unwrap() as BigDigit);
 674                 m = d;
 675             }
 676             if !m.is_zero() {
 677                 result.push(m.to_uint().unwrap() as BigDigit);
 678             }
 679             return result;
 680         }
 681
 682         fn fill_concat(v: &[BigDigit], radix: uint, l: uint) -> String {
 683             if v.is_empty() {
 684                 return "0".to_string()
 685             }
 686             let mut s = String::with_capacity(v.len() * l);
 687             for n in v.iter().rev() {
 688                 let ss = (*n as uint).to_str_radix(radix);
 689                 s.push_str("0".repeat(l - ss.len()).as_slice());
 690                 s.push_str(ss.as_slice());
 691             }
 692             s.as_slice().trim_left_chars('0').to_string()
 693         }
 694     }
 695 }
 696
 697 impl FromStrRadix for BigUint {
 698     /// Creates and initializes a `BigUint`.
 699     #[inline]
 700     fn from_str_radix(s: &str, radix: uint) -> Option<BigUint> {
 701         BigUint::parse_bytes(s.as_bytes(), radix)
 702     }
 703 }
 704
 705 impl BigUint {
 706     /// Creates and initializes a `BigUint`.
 707     ///
 708     /// The digits are be in base 2^32.
 709     #[inline]
 710     pub fn new(mut digits: Vec<BigDigit>) -> BigUint {
 711         // omit trailing zeros
 712         let new_len = digits.iter().rposition(|n| *n != 0).map_or(0, |p| p + 1);
 713         digits.truncate(new_len);
 714         BigUint { data: digits }
 715     }
 716
 717     /// Creates and initializes a `BigUint`.
 718     ///
 719     /// The digits are be in base 2^32.
 720     #[inline]
 721     pub fn from_slice(slice: &[BigDigit]) -> BigUint {
 722         BigUint::new(Vec::from_slice(slice))
 723     }
 724
 725     /// Creates and initializes a `BigUint`.
 726     pub fn parse_bytes(buf: &[u8], radix: uint) -> Option<BigUint> {
 727         let (base, unit_len) = get_radix_base(radix);
 728         let base_num = match base.to_biguint() {
 729             Some(base_num) => base_num,
 730             None => { return None; }
 731         };
 732
 733         let mut end             = buf.len();
 734         let mut n: BigUint      = Zero::zero();
 735         let mut power: BigUint  = One::one();
 736         loop {
 737             let start = cmp::max(end, unit_len) - unit_len;
 738             match uint::parse_bytes(buf.slice(start, end), radix) {
 739                 Some(d) => {
 740                     let d: Option<BigUint> = FromPrimitive::from_uint(d);
 741                     match d {
 742                         Some(d) => {
 743                             // FIXME(#5992): assignment operator overloads
 744                             // n += d * power;
 745                             n = n + d * power;
 746                         }
 747                         None => { return None; }
 748                     }
 749                 }
 750                 None => { return None; }
 751             }
 752             if end <= unit_len {
 753                 return Some(n);
 754             }
 755             end -= unit_len;
 756             // FIXME(#5992): assignment operator overloads
 757             // power *= base_num;
 758             power = power * base_num;
 759         }
 760     }
 761
 762     #[inline]
 763     fn shl_unit(&self, n_unit: uint) -> BigUint {
 764         if n_unit == 0 || self.is_zero() { return (*self).clone(); }
 765
 766         BigUint::new(Vec::from_elem(n_unit, ZERO_BIG_DIGIT).append(self.data.as_slice()))
 767     }
 768
 769     #[inline]
 770     fn shl_bits(&self, n_bits: uint) -> BigUint {
 771         if n_bits == 0 || self.is_zero() { return (*self).clone(); }
 772
 773         let mut carry = 0;
 774         let mut shifted: Vec<BigDigit> = self.data.iter().map(|elem| {
 775             let (hi, lo) = BigDigit::from_doublebigdigit(
 776                 (*elem as DoubleBigDigit) << n_bits | (carry as DoubleBigDigit)
 777             );
 778             carry = hi;
 779             lo
 780         }).collect();
 781         if carry != 0 { shifted.push(carry); }
 782         return BigUint::new(shifted);
 783     }
 784
 785     #[inline]
 786     fn shr_unit(&self, n_unit: uint) -> BigUint {
 787         if n_unit == 0 { return (*self).clone(); }
 788         if self.data.len() < n_unit { return Zero::zero(); }
 789         return BigUint::from_slice(
 790             self.data.slice(n_unit, self.data.len())
 791         );
 792     }
 793
 794     #[inline]
 795     fn shr_bits(&self, n_bits: uint) -> BigUint {
 796         if n_bits == 0 || self.data.is_empty() { return (*self).clone(); }
 797
 798         let mut borrow = 0;
 799         let mut shifted_rev = Vec::with_capacity(self.data.len());
 800         for elem in self.data.iter().rev() {
 801             shifted_rev.push((*elem >> n_bits) | borrow);
 802             borrow = *elem << (BigDigit::bits - n_bits);
 803         }
 804         let shifted = { shifted_rev.reverse(); shifted_rev };
 805         return BigUint::new(shifted);
 806     }
 807
 808     /// Determines the fewest bits necessary to express the `BigUint`.
 809     pub fn bits(&self) -> uint {
 810         if self.is_zero() { return 0; }
 811         let zeros = self.data.last().unwrap().leading_zeros();
 812         return self.data.len()*BigDigit::bits - zeros;
 813     }
 814 }
 815
 816 // `DoubleBigDigit` size dependent
 817 #[inline]
 818 fn get_radix_base(radix: uint) -> (DoubleBigDigit, uint) {
 819     match radix {
 820         2  => (4294967296, 32),
 821         3  => (3486784401, 20),
 822         4  => (4294967296, 16),
 823         5  => (1220703125, 13),
 824         6  => (2176782336, 12),
 825         7  => (1977326743, 11),
 826         8  => (1073741824, 10),
 827         9  => (3486784401, 10),
 828         10 => (1000000000, 9),
 829         11 => (2357947691, 9),
 830         12 => (429981696,  8),
 831         13 => (815730721,  8),
 832         14 => (1475789056, 8),
 833         15 => (2562890625, 8),
 834         16 => (4294967296, 8),
 835         _  => fail!("The radix must be within (1, 16]")
 836     }
 837 }
 838
 839 /// A Sign is a `BigInt`'s composing element.
 840 #[deriving(PartialEq, PartialOrd, Eq, Ord, Clone, Show)]
 841 pub enum Sign { Minus, Zero, Plus }
 842
 843 impl Neg<Sign> for Sign {
 844     /// Negate Sign value.
 845     #[inline]
 846     fn neg(&self) -> Sign {
 847         match *self {
 848           Minus => Plus,
 849           Zero  => Zero,
 850           Plus  => Minus
 851         }
 852     }
 853 }
 854
 855 /// A big signed integer type.
 856 #[deriving(Clone)]
 857 pub struct BigInt {
 858     sign: Sign,
 859     data: BigUint
 860 }
 861
 862 impl PartialEq for BigInt {
 863     #[inline]
 864     fn eq(&self, other: &BigInt) -> bool {
 865         self.cmp(other) == Equal
 866     }
 867 }
 868
 869 impl Eq for BigInt {}
 870
 871 impl PartialOrd for BigInt {
 872     #[inline]
 873     fn partial_cmp(&self, other: &BigInt) -> Option<Ordering> {
 874         Some(self.cmp(other))
 875     }
 876 }
 877
 878 impl Ord for BigInt {
 879     #[inline]
 880     fn cmp(&self, other: &BigInt) -> Ordering {
 881         let scmp = self.sign.cmp(&other.sign);
 882         if scmp != Equal { return scmp; }
 883
 884         match self.sign {
 885             Zero  => Equal,
 886             Plus  => self.data.cmp(&other.data),
 887             Minus => other.data.cmp(&self.data),
 888         }
 889     }
 890 }
 891
 892 impl Default for BigInt {
 893     #[inline]
 894     fn default() -> BigInt { Zero::zero() }
 895 }
 896
 897 impl fmt::Show for BigInt {
 898     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 899         write!(f, "{}", self.to_str_radix(10))
 900     }
 901 }
 902
 903 impl<S: hash::Writer> hash::Hash<S> for BigInt {
 904     fn hash(&self, state: &mut S) {
 905         (self.sign == Plus).hash(state);
 906         self.data.hash(state);
 907     }
 908 }
 909
 910 impl FromStr for BigInt {
 911     #[inline]
 912     fn from_str(s: &str) -> Option<BigInt> {
 913         FromStrRadix::from_str_radix(s, 10)
 914     }
 915 }
 916
 917 impl Num for BigInt {}
 918
 919 impl Shl<uint, BigInt> for BigInt {
 920     #[inline]
 921     fn shl(&self, rhs: &uint) -> BigInt {
 922         BigInt::from_biguint(self.sign, self.data << *rhs)
 923     }
 924 }
 925
 926 impl Shr<uint, BigInt> for BigInt {
 927     #[inline]
 928     fn shr(&self, rhs: &uint) -> BigInt {
 929         BigInt::from_biguint(self.sign, self.data >> *rhs)
 930     }
 931 }
 932
 933 impl Zero for BigInt {
 934     #[inline]
 935     fn zero() -> BigInt {
 936         BigInt::from_biguint(Zero, Zero::zero())
 937     }
 938
 939     #[inline]
 940     fn is_zero(&self) -> bool { self.sign == Zero }
 941 }
 942
 943 impl One for BigInt {
 944     #[inline]
 945     fn one() -> BigInt {
 946         BigInt::from_biguint(Plus, One::one())
 947     }
 948 }
 949
 950 impl Signed for BigInt {
 951     #[inline]
 952     fn abs(&self) -> BigInt {
 953         match self.sign {
 954             Plus | Zero => self.clone(),
 955             Minus => BigInt::from_biguint(Plus, self.data.clone())
 956         }
 957     }
 958
 959     #[inline]
 960     fn abs_sub(&self, other: &BigInt) -> BigInt {
 961         if *self <= *other { Zero::zero() } else { *self - *other }
 962     }
 963
 964     #[inline]
 965     fn signum(&self) -> BigInt {
 966         match self.sign {
 967             Plus  => BigInt::from_biguint(Plus, One::one()),
 968             Minus => BigInt::from_biguint(Minus, One::one()),
 969             Zero  => Zero::zero(),
 970         }
 971     }
 972
 973     #[inline]
 974     fn is_positive(&self) -> bool { self.sign == Plus }
 975
 976     #[inline]
 977     fn is_negative(&self) -> bool { self.sign == Minus }
 978 }
 979
 980 impl Add<BigInt, BigInt> for BigInt {
 981     #[inline]
 982     fn add(&self, other: &BigInt) -> BigInt {
 983         match (self.sign, other.sign) {
 984             (Zero, _)      => other.clone(),
 985             (_,    Zero)   => self.clone(),
 986             (Plus, Plus)   => BigInt::from_biguint(Plus, self.data + other.data),
 987             (Plus, Minus)  => self - (-*other),
 988             (Minus, Plus)  => other - (-*self),
 989             (Minus, Minus) => -((-self) + (-*other))
 990         }
 991     }
 992 }
 993
 994 impl Sub<BigInt, BigInt> for BigInt {
 995     #[inline]
 996     fn sub(&self, other: &BigInt) -> BigInt {
 997         match (self.sign, other.sign) {
 998             (Zero, _)    => -other,
 999             (_,    Zero) => self.clone(),
1000             (Plus, Plus) => match self.data.cmp(&other.data) {
1001                 Less    => BigInt::from_biguint(Minus, other.data - self.data),
1002                 Greater => BigInt::from_biguint(Plus, self.data - other.data),
1003                 Equal   => Zero::zero()
1004             },
1005             (Plus, Minus) => self + (-*other),
1006             (Minus, Plus) => -((-self) + *other),
1007             (Minus, Minus) => (-other) - (-*self)
1008         }
1009     }
1010 }
1011
1012 impl Mul<BigInt, BigInt> for BigInt {
1013     #[inline]
1014     fn mul(&self, other: &BigInt) -> BigInt {
1015         match (self.sign, other.sign) {
1016             (Zero, _)     | (_,     Zero)  => Zero::zero(),
1017             (Plus, Plus)  | (Minus, Minus) => {
1018                 BigInt::from_biguint(Plus, self.data * other.data)
1019             },
1020             (Plus, Minus) | (Minus, Plus) => {
1021                 BigInt::from_biguint(Minus, self.data * other.data)
1022             }
1023         }
1024     }
1025 }
1026
1027 impl Div<BigInt, BigInt> for BigInt {
1028     #[inline]
1029     fn div(&self, other: &BigInt) -> BigInt {
1030         let (q, _) = self.div_rem(other);
1031         q
1032     }
1033 }
1034
1035 impl Rem<BigInt, BigInt> for BigInt {
1036     #[inline]
1037     fn rem(&self, other: &BigInt) -> BigInt {
1038         let (_, r) = self.div_rem(other);
1039         r
1040     }
1041 }
1042
1043 impl Neg<BigInt> for BigInt {
1044     #[inline]
1045     fn neg(&self) -> BigInt {
1046         BigInt::from_biguint(self.sign.neg(), self.data.clone())
1047     }
1048 }
1049
1050 impl CheckedAdd for BigInt {
1051     #[inline]
1052     fn checked_add(&self, v: &BigInt) -> Option<BigInt> {
1053         return Some(self.add(v));
1054     }
1055 }
1056
1057 impl CheckedSub for BigInt {
1058     #[inline]
1059     fn checked_sub(&self, v: &BigInt) -> Option<BigInt> {
1060         return Some(self.sub(v));
1061     }
1062 }
1063
1064 impl CheckedMul for BigInt {
1065     #[inline]
1066     fn checked_mul(&self, v: &BigInt) -> Option<BigInt> {
1067         return Some(self.mul(v));
1068     }
1069 }
1070
1071 impl CheckedDiv for BigInt {
1072     #[inline]
1073     fn checked_div(&self, v: &BigInt) -> Option<BigInt> {
1074         if v.is_zero() {
1075             return None;
1076         }
1077         return Some(self.div(v));
1078     }
1079 }
1080
1081
1082 impl Integer for BigInt {
1083     #[inline]
1084     fn div_rem(&self, other: &BigInt) -> (BigInt, BigInt) {
1085         // r.sign == self.sign
1086         let (d_ui, r_ui) = self.data.div_mod_floor(&other.data);
1087         let d = BigInt::from_biguint(Plus, d_ui);
1088         let r = BigInt::from_biguint(Plus, r_ui);
1089         match (self.sign, other.sign) {
1090             (_,    Zero)   => fail!(),
1091             (Plus, Plus)  | (Zero, Plus)  => ( d,  r),
1092             (Plus, Minus) | (Zero, Minus) => (-d,  r),
1093             (Minus, Plus)                 => (-d, -r),
1094             (Minus, Minus)                => ( d, -r)
1095         }
1096     }
1097
1098     #[inline]
1099     fn div_floor(&self, other: &BigInt) -> BigInt {
1100         let (d, _) = self.div_mod_floor(other);
1101         d
1102     }
1103
1104     #[inline]
1105     fn mod_floor(&self, other: &BigInt) -> BigInt {
1106         let (_, m) = self.div_mod_floor(other);
1107         m
1108     }
1109
1110     fn div_mod_floor(&self, other: &BigInt) -> (BigInt, BigInt) {
1111         // m.sign == other.sign
1112         let (d_ui, m_ui) = self.data.div_rem(&other.data);
1113         let d = BigInt::from_biguint(Plus, d_ui);
1114         let m = BigInt::from_biguint(Plus, m_ui);
1115         match (self.sign, other.sign) {
1116             (_,    Zero)   => fail!(),
1117             (Plus, Plus)  | (Zero, Plus)  => (d, m),
1118             (Plus, Minus) | (Zero, Minus) => if m.is_zero() {
1119                 (-d, Zero::zero())
1120             } else {
1121                 (-d - One::one(), m + *other)
1122             },
1123             (Minus, Plus) => if m.is_zero() {
1124                 (-d, Zero::zero())
1125             } else {
1126                 (-d - One::one(), other - m)
1127             },
1128             (Minus, Minus) => (d, -m)
1129         }
1130     }
1131
1132     /// Calculates the Greatest Common Divisor (GCD) of the number and `other`.
1133     ///
1134     /// The result is always positive.
1135     #[inline]
1136     fn gcd(&self, other: &BigInt) -> BigInt {
1137         BigInt::from_biguint(Plus, self.data.gcd(&other.data))
1138     }
1139
1140     /// Calculates the Lowest Common Multiple (LCM) of the number and `other`.
1141     #[inline]
1142     fn lcm(&self, other: &BigInt) -> BigInt {
1143         BigInt::from_biguint(Plus, self.data.lcm(&other.data))
1144     }
1145
1146     /// Deprecated, use `is_multiple_of` instead.
1147     #[deprecated = "function renamed to `is_multiple_of`"]
1148     #[inline]
1149     fn divides(&self, other: &BigInt) -> bool { return self.is_multiple_of(other); }
1150
1151     /// Returns `true` if the number is a multiple of `other`.
1152     #[inline]
1153     fn is_multiple_of(&self, other: &BigInt) -> bool { self.data.is_multiple_of(&other.data) }
1154
1155     /// Returns `true` if the number is divisible by `2`.
1156     #[inline]
1157     fn is_even(&self) -> bool { self.data.is_even() }
1158
1159     /// Returns `true` if the number is not divisible by `2`.
1160     #[inline]
1161     fn is_odd(&self) -> bool { self.data.is_odd() }
1162 }
1163
1164 impl ToPrimitive for BigInt {
1165     #[inline]
1166     fn to_i64(&self) -> Option<i64> {
1167         match self.sign {
1168             Plus  => self.data.to_i64(),
1169             Zero  => Some(0),
1170             Minus => {
1171                 self.data.to_u64().and_then(|n| {
1172                     let m: u64 = 1 << 63;
1173                     if n < m {
1174                         Some(-(n as i64))
1175                     } else if n == m {
1176                         Some(i64::MIN)
1177                     } else {
1178                         None
1179                     }
1180                 })
1181             }
1182         }
1183     }
1184
1185     #[inline]
1186     fn to_u64(&self) -> Option<u64> {
1187         match self.sign {
1188             Plus => self.data.to_u64(),
1189             Zero => Some(0),
1190             Minus => None
1191         }
1192     }
1193 }
1194
1195 impl FromPrimitive for BigInt {
1196     #[inline]
1197     fn from_i64(n: i64) -> Option<BigInt> {
1198         if n > 0 {
1199             FromPrimitive::from_u64(n as u64).and_then(|n| {
1200                 Some(BigInt::from_biguint(Plus, n))
1201             })
1202         } else if n < 0 {
1203             FromPrimitive::from_u64(u64::MAX - (n as u64) + 1).and_then(
1204                 |n| {
1205                     Some(BigInt::from_biguint(Minus, n))
1206                 })
1207         } else {
1208             Some(Zero::zero())
1209         }
1210     }
1211
1212     #[inline]
1213     fn from_u64(n: u64) -> Option<BigInt> {
1214         if n == 0 {
1215             Some(Zero::zero())
1216         } else {
1217             FromPrimitive::from_u64(n).and_then(|n| {
1218                 Some(BigInt::from_biguint(Plus, n))
1219             })
1220         }
1221     }
1222 }
1223
1224 /// A generic trait for converting a value to a `BigInt`.
1225 pub trait ToBigInt {
1226     /// Converts the value of `self` to a `BigInt`.
1227     fn to_bigint(&self) -> Option<BigInt>;
1228 }
1229
1230 impl ToBigInt for BigInt {
1231     #[inline]
1232     fn to_bigint(&self) -> Option<BigInt> {
1233         Some(self.clone())
1234     }
1235 }
1236
1237 impl ToBigInt for BigUint {
1238     #[inline]
1239     fn to_bigint(&self) -> Option<BigInt> {
1240         if self.is_zero() {
1241             Some(Zero::zero())
1242         } else {
1243             Some(BigInt { sign: Plus, data: self.clone() })
1244         }
1245     }
1246 }
1247
1248 macro_rules! impl_to_bigint(
1249     ($T:ty, $from_ty:path) => {
1250         impl ToBigInt for $T {
1251             #[inline]
1252             fn to_bigint(&self) -> Option<BigInt> {
1253                 $from_ty(*self)
1254             }
1255         }
1256     }
1257 )
1258
1259 impl_to_bigint!(int,  FromPrimitive::from_int)
1260 impl_to_bigint!(i8,   FromPrimitive::from_i8)
1261 impl_to_bigint!(i16,  FromPrimitive::from_i16)
1262 impl_to_bigint!(i32,  FromPrimitive::from_i32)
1263 impl_to_bigint!(i64,  FromPrimitive::from_i64)
1264 impl_to_bigint!(uint, FromPrimitive::from_uint)
1265 impl_to_bigint!(u8,   FromPrimitive::from_u8)
1266 impl_to_bigint!(u16,  FromPrimitive::from_u16)
1267 impl_to_bigint!(u32,  FromPrimitive::from_u32)
1268 impl_to_bigint!(u64,  FromPrimitive::from_u64)
1269
1270 impl ToStrRadix for BigInt {
1271     #[inline]
1272     fn to_str_radix(&self, radix: uint) -> String {
1273         match self.sign {
1274             Plus  => self.data.to_str_radix(radix),
1275             Zero  => "0".to_string(),
1276             Minus => format!("-{}", self.data.to_str_radix(radix)),
1277         }
1278     }
1279 }
1280
1281 impl FromStrRadix for BigInt {
1282     /// Creates and initializes a BigInt.
1283     #[inline]
1284     fn from_str_radix(s: &str, radix: uint) -> Option<BigInt> {
1285         BigInt::parse_bytes(s.as_bytes(), radix)
1286     }
1287 }
1288
1289 pub trait RandBigInt {
1290     /// Generate a random `BigUint` of the given bit size.
1291     fn gen_biguint(&mut self, bit_size: uint) -> BigUint;
1292
1293     /// Generate a random BigInt of the given bit size.
1294     fn gen_bigint(&mut self, bit_size: uint) -> BigInt;
1295
1296     /// Generate a random `BigUint` less than the given bound. Fails
1297     /// when the bound is zero.
1298     fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint;
1299
1300     /// Generate a random `BigUint` within the given range. The lower
1301     /// bound is inclusive; the upper bound is exclusive. Fails when
1302     /// the upper bound is not greater than the lower bound.
1303     fn gen_biguint_range(&mut self, lbound: &BigUint, ubound: &BigUint) -> BigUint;
1304
1305     /// Generate a random `BigInt` within the given range. The lower
1306     /// bound is inclusive; the upper bound is exclusive. Fails when
1307     /// the upper bound is not greater than the lower bound.
1308     fn gen_bigint_range(&mut self, lbound: &BigInt, ubound: &BigInt) -> BigInt;
1309 }
1310
1311 impl<R: Rng> RandBigInt for R {
1312     fn gen_biguint(&mut self, bit_size: uint) -> BigUint {
1313         let (digits, rem) = bit_size.div_rem(&BigDigit::bits);
1314         let mut data = Vec::with_capacity(digits+1);
1315         for _ in range(0, digits) {
1316             data.push(self.gen());
1317         }
1318         if rem > 0 {
1319             let final_digit: BigDigit = self.gen();
1320             data.push(final_digit >> (BigDigit::bits - rem));
1321         }
1322         BigUint::new(data)
1323     }
1324
1325     fn gen_bigint(&mut self, bit_size: uint) -> BigInt {
1326         // Generate a random BigUint...
1327         let biguint = self.gen_biguint(bit_size);
1328         // ...and then randomly assign it a Sign...
1329         let sign = if biguint.is_zero() {
1330             // ...except that if the BigUint is zero, we need to try
1331             // again with probability 0.5. This is because otherwise,
1332             // the probability of generating a zero BigInt would be
1333             // double that of any other number.
1334             if self.gen() {
1335                 return self.gen_bigint(bit_size);
1336             } else {
1337                 Zero
1338             }
1339         } else if self.gen() {
1340             Plus
1341         } else {
1342             Minus
1343         };
1344         BigInt::from_biguint(sign, biguint)
1345     }
1346
1347     fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint {
1348         assert!(!bound.is_zero());
1349         let bits = bound.bits();
1350         loop {
1351             let n = self.gen_biguint(bits);
1352             if n < *bound { return n; }
1353         }
1354     }
1355
1356     fn gen_biguint_range(&mut self,
1357                          lbound: &BigUint,
1358                          ubound: &BigUint)
1359                          -> BigUint {
1360         assert!(*lbound < *ubound);
1361         return *lbound + self.gen_biguint_below(&(*ubound - *lbound));
1362     }
1363
1364     fn gen_bigint_range(&mut self,
1365                         lbound: &BigInt,
1366                         ubound: &BigInt)
1367                         -> BigInt {
1368         assert!(*lbound < *ubound);
1369         let delta = (*ubound - *lbound).to_biguint().unwrap();
1370         return *lbound + self.gen_biguint_below(&delta).to_bigint().unwrap();
1371     }
1372 }
1373
1374 impl BigInt {
1375     /// Creates and initializes a BigInt.
1376     ///
1377     /// The digits are be in base 2^32.
1378     #[inline]
1379     pub fn new(sign: Sign, digits: Vec<BigDigit>) -> BigInt {
1380         BigInt::from_biguint(sign, BigUint::new(digits))
1381     }
1382
1383     /// Creates and initializes a `BigInt`.
1384     ///
1385     /// The digits are be in base 2^32.
1386     #[inline]
1387     pub fn from_biguint(sign: Sign, data: BigUint) -> BigInt {
1388         if sign == Zero || data.is_zero() {
1389             return BigInt { sign: Zero, data: Zero::zero() };
1390         }
1391         BigInt { sign: sign, data: data }
1392     }
1393
1394     /// Creates and initializes a `BigInt`.
1395     #[inline]
1396     pub fn from_slice(sign: Sign, slice: &[BigDigit]) -> BigInt {
1397         BigInt::from_biguint(sign, BigUint::from_slice(slice))
1398     }
1399
1400     /// Creates and initializes a `BigInt`.
1401     pub fn parse_bytes(buf: &[u8], radix: uint) -> Option<BigInt> {
1402         if buf.is_empty() { return None; }
1403         let mut sign  = Plus;
1404         let mut start = 0;
1405         if buf[0] == b'-' {
1406             sign  = Minus;
1407             start = 1;
1408         }
1409         return BigUint::parse_bytes(buf.slice(start, buf.len()), radix)
1410             .map(|bu| BigInt::from_biguint(sign, bu));
1411     }
1412
1413     /// Converts this `BigInt` into a `BigUint`, if it's not negative.
1414     #[inline]
1415     pub fn to_biguint(&self) -> Option<BigUint> {
1416         match self.sign {
1417             Plus => Some(self.data.clone()),
1418             Zero => Some(Zero::zero()),
1419             Minus => None
1420         }
1421     }
1422 }
1423
1424 #[cfg(test)]
1425 mod biguint_tests {
1426     use Integer;
1427     use super::{BigDigit, BigUint, ToBigUint};
1428     use super::{Plus, BigInt, RandBigInt, ToBigInt};
1429
1430     use std::cmp::{Less, Equal, Greater};
1431     use std::from_str::FromStr;
1432     use std::i64;
1433     use std::num::{Zero, One, FromStrRadix, ToStrRadix};
1434     use std::num::{ToPrimitive, FromPrimitive};
1435     use std::num::CheckedDiv;
1436     use std::rand::task_rng;
1437     use std::u64;
1438     use std::hash::hash;
1439
1440     #[test]
1441     fn test_from_slice() {
1442         fn check(slice: &[BigDigit], data: &[BigDigit]) {
1443             assert!(data == BigUint::from_slice(slice).data.as_slice());
1444         }
1445         check([1], [1]);
1446         check([0, 0, 0], []);
1447         check([1, 2, 0, 0], [1, 2]);
1448         check([0, 0, 1, 2], [0, 0, 1, 2]);
1449         check([0, 0, 1, 2, 0, 0], [0, 0, 1, 2]);
1450         check([-1], [-1]);
1451     }
1452
1453     #[test]
1454     fn test_cmp() {
1455         let data: [&[_], ..7] = [ &[], &[1], &[2], &[-1], &[0, 1], &[2, 1], &[1, 1, 1]  ];
1456         let data: Vec<BigUint> = data.iter().map(|v| BigUint::from_slice(*v)).collect();
1457         for (i, ni) in data.iter().enumerate() {
1458             for (j0, nj) in data.slice(i, data.len()).iter().enumerate() {
1459                 let j = j0 + i;
1460                 if i == j {
1461                     assert_eq!(ni.cmp(nj), Equal);
1462                     assert_eq!(nj.cmp(ni), Equal);
1463                     assert_eq!(ni, nj);
1464                     assert!(!(ni != nj));
1465                     assert!(ni <= nj);
1466                     assert!(ni >= nj);
1467                     assert!(!(ni < nj));
1468                     assert!(!(ni > nj));
1469                 } else {
1470                     assert_eq!(ni.cmp(nj), Less);
1471                     assert_eq!(nj.cmp(ni), Greater);
1472
1473                     assert!(!(ni == nj));
1474                     assert!(ni != nj);
1475
1476                     assert!(ni <= nj);
1477                     assert!(!(ni >= nj));
1478                     assert!(ni < nj);
1479                     assert!(!(ni > nj));
1480
1481                     assert!(!(nj <= ni));
1482                     assert!(nj >= ni);
1483                     assert!(!(nj < ni));
1484                     assert!(nj > ni);
1485                 }
1486             }
1487         }
1488     }
1489
1490     #[test]
1491     fn test_hash() {
1492         let a = BigUint::new(vec!());
1493         let b = BigUint::new(vec!(0));
1494         let c = BigUint::new(vec!(1));
1495         let d = BigUint::new(vec!(1,0,0,0,0,0));
1496         let e = BigUint::new(vec!(0,0,0,0,0,1));
1497         assert!(hash(&a) == hash(&b));
1498         assert!(hash(&b) != hash(&c));
1499         assert!(hash(&c) == hash(&d));
1500         assert!(hash(&d) != hash(&e));
1501     }
1502
1503     #[test]
1504     fn test_bitand() {
1505         fn check(left: &[BigDigit],
1506                  right: &[BigDigit],
1507                  expected: &[BigDigit]) {
1508             assert_eq!(BigUint::from_slice(left) & BigUint::from_slice(right),
1509                        BigUint::from_slice(expected));
1510         }
1511         check([], [], []);
1512         check([268, 482, 17],
1513               [964, 54],
1514               [260, 34]);
1515     }
1516
1517     #[test]
1518     fn test_bitor() {
1519         fn check(left: &[BigDigit],
1520                  right: &[BigDigit],
1521                  expected: &[BigDigit]) {
1522             assert_eq!(BigUint::from_slice(left) | BigUint::from_slice(right),
1523                        BigUint::from_slice(expected));
1524         }
1525         check([], [], []);
1526         check([268, 482, 17],
1527               [964, 54],
1528               [972, 502, 17]);
1529     }
1530
1531     #[test]
1532     fn test_bitxor() {
1533         fn check(left: &[BigDigit],
1534                  right: &[BigDigit],
1535                  expected: &[BigDigit]) {
1536             assert_eq!(BigUint::from_slice(left) ^ BigUint::from_slice(right),
1537                        BigUint::from_slice(expected));
1538         }
1539         check([], [], []);
1540         check([268, 482, 17],
1541               [964, 54],
1542               [712, 468, 17]);
1543     }
1544
1545     #[test]
1546     fn test_shl() {
1547         fn check(s: &str, shift: uint, ans: &str) {
1548             let opt_biguint: Option<BigUint> = FromStrRadix::from_str_radix(s, 16);
1549             let bu = (opt_biguint.unwrap() << shift).to_str_radix(16);
1550             assert_eq!(bu.as_slice(), ans);
1551         }
1552
1553         check("0", 3, "0");
1554         check("1", 3, "8");
1555
1556         check("1\
1557                0000\
1558                0000\
1559                0000\
1560                0001\
1561                0000\
1562                0000\
1563                0000\
1564                0001",
1565               3,
1566               "8\
1567                0000\
1568                0000\
1569                0000\
1570                0008\
1571                0000\
1572                0000\
1573                0000\
1574                0008");
1575         check("1\
1576                0000\
1577                0001\
1578                0000\
1579                0001",
1580               2,
1581               "4\
1582                0000\
1583                0004\
1584                0000\
1585                0004");
1586         check("1\
1587                0001\
1588                0001",
1589               1,
1590               "2\
1591                0002\
1592                0002");
1593
1594         check("\
1595               4000\
1596               0000\
1597               0000\
1598               0000",
1599               3,
1600               "2\
1601               0000\
1602               0000\
1603               0000\
1604               0000");
1605         check("4000\
1606               0000",
1607               2,
1608               "1\
1609               0000\
1610               0000");
1611         check("4000",
1612               2,
1613               "1\
1614               0000");
1615
1616         check("4000\
1617               0000\
1618               0000\
1619               0000",
1620               67,
1621               "2\
1622               0000\
1623               0000\
1624               0000\
1625               0000\
1626               0000\
1627               0000\
1628               0000\
1629               0000");
1630         check("4000\
1631               0000",
1632               35,
1633               "2\
1634               0000\
1635               0000\
1636               0000\
1637               0000");
1638         check("4000",
1639               19,
1640               "2\
1641               0000\
1642               0000");
1643
1644         check("fedc\
1645               ba98\
1646               7654\
1647               3210\
1648               fedc\
1649               ba98\
1650               7654\
1651               3210",
1652               4,
1653               "f\
1654               edcb\
1655               a987\
1656               6543\
1657               210f\
1658               edcb\
1659               a987\
1660               6543\
1661               2100");
1662         check("88887777666655554444333322221111", 16,
1663               "888877776666555544443333222211110000");
1664     }
1665
1666     #[test]
1667     fn test_shr() {
1668         fn check(s: &str, shift: uint, ans: &str) {
1669             let opt_biguint: Option<BigUint> =
1670                 FromStrRadix::from_str_radix(s, 16);
1671             let bu = (opt_biguint.unwrap() >> shift).to_str_radix(16);
1672             assert_eq!(bu.as_slice(), ans);
1673         }
1674
1675         check("0", 3, "0");
1676         check("f", 3, "1");
1677
1678         check("1\
1679               0000\
1680               0000\
1681               0000\
1682               0001\
1683               0000\
1684               0000\
1685               0000\
1686               0001",
1687               3,
1688               "2000\
1689               0000\
1690               0000\
1691               0000\
1692               2000\
1693               0000\
1694               0000\
1695               0000");
1696         check("1\
1697               0000\
1698               0001\
1699               0000\
1700               0001",
1701               2,
1702               "4000\
1703               0000\
1704               4000\
1705               0000");
1706         check("1\
1707               0001\
1708               0001",
1709               1,
1710               "8000\
1711               8000");
1712
1713         check("2\
1714               0000\
1715               0000\
1716               0000\
1717               0001\
1718               0000\
1719               0000\
1720               0000\
1721               0001",
1722               67,
1723               "4000\
1724               0000\
1725               0000\
1726               0000");
1727         check("2\
1728               0000\
1729               0001\
1730               0000\
1731               0001",
1732               35,
1733               "4000\
1734               0000");
1735         check("2\
1736               0001\
1737               0001",
1738               19,
1739               "4000");
1740
1741         check("1\
1742               0000\
1743               0000\
1744               0000\
1745               0000",
1746               1,
1747               "8000\
1748               0000\
1749               0000\
1750               0000");
1751         check("1\
1752               0000\
1753               0000",
1754               1,
1755               "8000\
1756               0000");
1757         check("1\
1758               0000",
1759               1,
1760               "8000");
1761         check("f\
1762               edcb\
1763               a987\
1764               6543\
1765               210f\
1766               edcb\
1767               a987\
1768               6543\
1769               2100",
1770               4,
1771               "fedc\
1772               ba98\
1773               7654\
1774               3210\
1775               fedc\
1776               ba98\
1777               7654\
1778               3210");
1779
1780         check("888877776666555544443333222211110000", 16,
1781               "88887777666655554444333322221111");
1782     }
1783
1784     // `DoubleBigDigit` size dependent
1785     #[test]
1786     fn test_convert_i64() {
1787         fn check(b1: BigUint, i: i64) {
1788             let b2: BigUint = FromPrimitive::from_i64(i).unwrap();
1789             assert!(b1 == b2);
1790             assert!(b1.to_i64().unwrap() == i);
1791         }
1792
1793         check(Zero::zero(), 0);
1794         check(One::one(), 1);
1795         check(i64::MAX.to_biguint().unwrap(), i64::MAX);
1796
1797         check(BigUint::new(vec!(           )), 0);
1798         check(BigUint::new(vec!( 1         )), (1 << (0*BigDigit::bits)));
1799         check(BigUint::new(vec!(-1         )), (1 << (1*BigDigit::bits)) - 1);
1800         check(BigUint::new(vec!( 0,  1     )), (1 << (1*BigDigit::bits)));
1801         check(BigUint::new(vec!(-1, -1 >> 1)), i64::MAX);
1802
1803         assert_eq!(i64::MIN.to_biguint(), None);
1804         assert_eq!(BigUint::new(vec!(-1, -1    )).to_i64(), None);
1805         assert_eq!(BigUint::new(vec!( 0,  0,  1)).to_i64(), None);
1806         assert_eq!(BigUint::new(vec!(-1, -1, -1)).to_i64(), None);
1807     }
1808
1809     // `DoubleBigDigit` size dependent
1810     #[test]
1811     fn test_convert_u64() {
1812         fn check(b1: BigUint, u: u64) {
1813             let b2: BigUint = FromPrimitive::from_u64(u).unwrap();
1814             assert!(b1 == b2);
1815             assert!(b1.to_u64().unwrap() == u);
1816         }
1817
1818         check(Zero::zero(), 0);
1819         check(One::one(), 1);
1820         check(u64::MIN.to_biguint().unwrap(), u64::MIN);
1821         check(u64::MAX.to_biguint().unwrap(), u64::MAX);
1822
1823         check(BigUint::new(vec!(      )), 0);
1824         check(BigUint::new(vec!( 1    )), (1 << (0*BigDigit::bits)));
1825         check(BigUint::new(vec!(-1    )), (1 << (1*BigDigit::bits)) - 1);
1826         check(BigUint::new(vec!( 0,  1)), (1 << (1*BigDigit::bits)));
1827         check(BigUint::new(vec!(-1, -1)), u64::MAX);
1828
1829         assert_eq!(BigUint::new(vec!( 0,  0,  1)).to_u64(), None);
1830         assert_eq!(BigUint::new(vec!(-1, -1, -1)).to_u64(), None);
1831     }
1832
1833     #[test]
1834     fn test_convert_to_bigint() {
1835         fn check(n: BigUint, ans: BigInt) {
1836             assert_eq!(n.to_bigint().unwrap(), ans);
1837             assert_eq!(n.to_bigint().unwrap().to_biguint().unwrap(), n);
1838         }
1839         check(Zero::zero(), Zero::zero());
1840         check(BigUint::new(vec!(1,2,3)),
1841               BigInt::from_biguint(Plus, BigUint::new(vec!(1,2,3))));
1842     }
1843
1844     static sum_triples: &'static [(&'static [BigDigit],
1845                                    &'static [BigDigit],
1846                                    &'static [BigDigit])] = &[
1847         (&[],          &[],       &[]),
1848         (&[],          &[ 1],     &[ 1]),
1849         (&[ 1],        &[ 1],     &[ 2]),
1850         (&[ 1],        &[ 1,  1], &[ 2,  1]),
1851         (&[ 1],        &[-1],     &[ 0,  1]),
1852         (&[ 1],        &[-1, -1], &[ 0,  0, 1]),
1853         (&[-1, -1],    &[-1, -1], &[-2, -1, 1]),
1854         (&[ 1,  1, 1], &[-1, -1], &[ 0,  1, 2]),
1855         (&[ 2,  2, 1], &[-1, -2], &[ 1,  1, 2])
1856     ];
1857
1858     #[test]
1859     fn test_add() {
1860         for elm in sum_triples.iter() {
1861             let (a_vec, b_vec, c_vec) = *elm;
1862             let a = BigUint::from_slice(a_vec);
1863             let b = BigUint::from_slice(b_vec);
1864             let c = BigUint::from_slice(c_vec);
1865
1866             assert!(a + b == c);
1867             assert!(b + a == c);
1868         }
1869     }
1870
1871     #[test]
1872     fn test_sub() {
1873         for elm in sum_triples.iter() {
1874             let (a_vec, b_vec, c_vec) = *elm;
1875             let a = BigUint::from_slice(a_vec);
1876             let b = BigUint::from_slice(b_vec);
1877             let c = BigUint::from_slice(c_vec);
1878
1879             assert!(c - a == b);
1880             assert!(c - b == a);
1881         }
1882     }
1883
1884     #[test]
1885     #[should_fail]
1886     fn test_sub_fail_on_underflow() {
1887         let (a, b) : (BigUint, BigUint) = (Zero::zero(), One::one());
1888         a - b;
1889     }
1890
1891     static mul_triples: &'static [(&'static [BigDigit],
1892                                    &'static [BigDigit],
1893                                    &'static [BigDigit])] = &[
1894         (&[],               &[],               &[]),
1895         (&[],               &[ 1],             &[]),
1896         (&[ 2],             &[],               &[]),
1897         (&[ 1],             &[ 1],             &[1]),
1898         (&[ 2],             &[ 3],             &[ 6]),
1899         (&[ 1],             &[ 1,  1,  1],     &[1, 1,  1]),
1900         (&[ 1,  2,  3],     &[ 3],             &[ 3,  6,  9]),
1901         (&[ 1,  1,  1],     &[-1],             &[-1, -1, -1]),
1902         (&[ 1,  2,  3],     &[-1],             &[-1, -2, -2, 2]),
1903         (&[ 1,  2,  3,  4], &[-1],             &[-1, -2, -2, -2, 3]),
1904         (&[-1],             &[-1],             &[ 1, -2]),
1905         (&[-1, -1],         &[-1],             &[ 1, -1, -2]),
1906         (&[-1, -1, -1],     &[-1],             &[ 1, -1, -1, -2]),
1907         (&[-1, -1, -1, -1], &[-1],             &[ 1, -1, -1, -1, -2]),
1908         (&[-1/2 + 1],       &[ 2],             &[ 0,  1]),
1909         (&[0, -1/2 + 1],    &[ 2],             &[ 0,  0,  1]),
1910         (&[ 1,  2],         &[ 1,  2,  3],     &[1, 4,  7,  6]),
1911         (&[-1, -1],         &[-1, -1, -1],     &[1, 0, -1, -2, -1]),
1912         (&[-1, -1, -1],     &[-1, -1, -1, -1], &[1, 0,  0, -1, -2, -1, -1]),
1913         (&[ 0,  0,  1],     &[ 1,  2,  3],     &[0, 0,  1,  2,  3]),
1914         (&[ 0,  0,  1],     &[ 0,  0,  0,  1], &[0, 0,  0,  0,  0,  1])
1915     ];
1916
1917     static div_rem_quadruples: &'static [(&'static [BigDigit],
1918                                            &'static [BigDigit],
1919                                            &'static [BigDigit],
1920                                            &'static [BigDigit])]
1921         = &[
1922             (&[ 1],        &[ 2], &[],               &[1]),
1923             (&[ 1,  1],    &[ 2], &[-1/2+1],         &[1]),
1924             (&[ 1,  1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
1925             (&[ 0,  1],    &[-1], &[1],              &[1]),
1926             (&[-1, -1],    &[-2], &[2, 1],           &[3])
1927         ];
1928
1929     #[test]
1930     fn test_mul() {
1931         for elm in mul_triples.iter() {
1932             let (a_vec, b_vec, c_vec) = *elm;
1933             let a = BigUint::from_slice(a_vec);
1934             let b = BigUint::from_slice(b_vec);
1935             let c = BigUint::from_slice(c_vec);
1936
1937             assert!(a * b == c);
1938             assert!(b * a == c);
1939         }
1940
1941         for elm in div_rem_quadruples.iter() {
1942             let (a_vec, b_vec, c_vec, d_vec) = *elm;
1943             let a = BigUint::from_slice(a_vec);
1944             let b = BigUint::from_slice(b_vec);
1945             let c = BigUint::from_slice(c_vec);
1946             let d = BigUint::from_slice(d_vec);
1947
1948             assert!(a == b * c + d);
1949             assert!(a == c * b + d);
1950         }
1951     }
1952
1953     #[test]
1954     fn test_div_rem() {
1955         for elm in mul_triples.iter() {
1956             let (a_vec, b_vec, c_vec) = *elm;
1957             let a = BigUint::from_slice(a_vec);
1958             let b = BigUint::from_slice(b_vec);
1959             let c = BigUint::from_slice(c_vec);
1960
1961             if !a.is_zero() {
1962                 assert_eq!(c.div_rem(&a), (b.clone(), Zero::zero()));
1963             }
1964             if !b.is_zero() {
1965                 assert_eq!(c.div_rem(&b), (a.clone(), Zero::zero()));
1966             }
1967         }
1968
1969         for elm in div_rem_quadruples.iter() {
1970             let (a_vec, b_vec, c_vec, d_vec) = *elm;
1971             let a = BigUint::from_slice(a_vec);
1972             let b = BigUint::from_slice(b_vec);
1973             let c = BigUint::from_slice(c_vec);
1974             let d = BigUint::from_slice(d_vec);
1975
1976             if !b.is_zero() { assert!(a.div_rem(&b) == (c, d)); }
1977         }
1978     }
1979
1980     #[test]
1981     fn test_checked_add() {
1982         for elm in sum_triples.iter() {
1983             let (a_vec, b_vec, c_vec) = *elm;
1984             let a = BigUint::from_slice(a_vec);
1985             let b = BigUint::from_slice(b_vec);
1986             let c = BigUint::from_slice(c_vec);
1987
1988             assert!(a.checked_add(&b).unwrap() == c);
1989             assert!(b.checked_add(&a).unwrap() == c);
1990         }
1991     }
1992
1993     #[test]
1994     fn test_checked_sub() {
1995         for elm in sum_triples.iter() {
1996             let (a_vec, b_vec, c_vec) = *elm;
1997             let a = BigUint::from_slice(a_vec);
1998             let b = BigUint::from_slice(b_vec);
1999             let c = BigUint::from_slice(c_vec);
2000
2001             assert!(c.checked_sub(&a).unwrap() == b);
2002             assert!(c.checked_sub(&b).unwrap() == a);
2003
2004             if a > c {
2005                 assert!(a.checked_sub(&c).is_none());
2006             }
2007             if b > c {
2008                 assert!(b.checked_sub(&c).is_none());
2009             }
2010         }
2011     }
2012
2013     #[test]
2014     fn test_checked_mul() {
2015         for elm in mul_triples.iter() {
2016             let (a_vec, b_vec, c_vec) = *elm;
2017             let a = BigUint::from_slice(a_vec);
2018             let b = BigUint::from_slice(b_vec);
2019             let c = BigUint::from_slice(c_vec);
2020
2021             assert!(a.checked_mul(&b).unwrap() == c);
2022             assert!(b.checked_mul(&a).unwrap() == c);
2023         }
2024
2025         for elm in div_rem_quadruples.iter() {
2026             let (a_vec, b_vec, c_vec, d_vec) = *elm;
2027             let a = BigUint::from_slice(a_vec);
2028             let b = BigUint::from_slice(b_vec);
2029             let c = BigUint::from_slice(c_vec);
2030             let d = BigUint::from_slice(d_vec);
2031
2032             assert!(a == b.checked_mul(&c).unwrap() + d);
2033             assert!(a == c.checked_mul(&b).unwrap() + d);
2034         }
2035     }
2036
2037     #[test]
2038     fn test_checked_div() {
2039         for elm in mul_triples.iter() {
2040             let (a_vec, b_vec, c_vec) = *elm;
2041             let a = BigUint::from_slice(a_vec);
2042             let b = BigUint::from_slice(b_vec);
2043             let c = BigUint::from_slice(c_vec);
2044
2045             if !a.is_zero() {
2046                 assert!(c.checked_div(&a).unwrap() == b);
2047             }
2048             if !b.is_zero() {
2049                 assert!(c.checked_div(&b).unwrap() == a);
2050             }
2051
2052             assert!(c.checked_div(&Zero::zero()).is_none());
2053         }
2054     }
2055
2056     #[test]
2057     fn test_gcd() {
2058         fn check(a: uint, b: uint, c: uint) {
2059             let big_a: BigUint = FromPrimitive::from_uint(a).unwrap();
2060             let big_b: BigUint = FromPrimitive::from_uint(b).unwrap();
2061             let big_c: BigUint = FromPrimitive::from_uint(c).unwrap();
2062
2063             assert_eq!(big_a.gcd(&big_b), big_c);
2064         }
2065
2066         check(10, 2, 2);
2067         check(10, 3, 1);
2068         check(0, 3, 3);
2069         check(3, 3, 3);
2070         check(56, 42, 14);
2071     }
2072
2073     #[test]
2074     fn test_lcm() {
2075         fn check(a: uint, b: uint, c: uint) {
2076             let big_a: BigUint = FromPrimitive::from_uint(a).unwrap();
2077             let big_b: BigUint = FromPrimitive::from_uint(b).unwrap();
2078             let big_c: BigUint = FromPrimitive::from_uint(c).unwrap();
2079
2080             assert_eq!(big_a.lcm(&big_b), big_c);
2081         }
2082
2083         check(1, 0, 0);
2084         check(0, 1, 0);
2085         check(1, 1, 1);
2086         check(8, 9, 72);
2087         check(11, 5, 55);
2088         check(99, 17, 1683);
2089     }
2090
2091     #[test]
2092     fn test_is_even() {
2093         let one: BigUint = FromStr::from_str("1").unwrap();
2094         let two: BigUint = FromStr::from_str("2").unwrap();
2095         let thousand: BigUint = FromStr::from_str("1000").unwrap();
2096         let big: BigUint = FromStr::from_str("1000000000000000000000").unwrap();
2097         let bigger: BigUint = FromStr::from_str("1000000000000000000001").unwrap();
2098         assert!(one.is_odd());
2099         assert!(two.is_even());
2100         assert!(thousand.is_even());
2101         assert!(big.is_even());
2102         assert!(bigger.is_odd());
2103         assert!((one << 64).is_even());
2104         assert!(((one << 64) + one).is_odd());
2105     }
2106
2107     fn to_str_pairs() -> Vec<(BigUint, Vec<(uint, String)>)> {
2108         let bits = BigDigit::bits;
2109         vec!(( Zero::zero(), vec!(
2110             (2, "0".to_string()), (3, "0".to_string())
2111         )), ( BigUint::from_slice([ 0xff ]), vec!(
2112             (2,  "11111111".to_string()),
2113             (3,  "100110".to_string()),
2114             (4,  "3333".to_string()),
2115             (5,  "2010".to_string()),
2116             (6,  "1103".to_string()),
2117             (7,  "513".to_string()),
2118             (8,  "377".to_string()),
2119             (9,  "313".to_string()),
2120             (10, "255".to_string()),
2121             (11, "212".to_string()),
2122             (12, "193".to_string()),
2123             (13, "168".to_string()),
2124             (14, "143".to_string()),
2125             (15, "120".to_string()),
2126             (16, "ff".to_string())
2127         )), ( BigUint::from_slice([ 0xfff ]), vec!(
2128             (2,  "111111111111".to_string()),
2129             (4,  "333333".to_string()),
2130             (16, "fff".to_string())
2131         )), ( BigUint::from_slice([ 1, 2 ]), vec!(
2132             (2,
2133              format!("10{}1", "0".repeat(bits - 1))),
2134             (4,
2135              format!("2{}1", "0".repeat(bits / 2 - 1))),
2136             (10, match bits {
2137                 32 => "8589934593".to_string(),
2138                 16 => "131073".to_string(),
2139                 _ => fail!()
2140             }),
2141             (16,
2142              format!("2{}1", "0".repeat(bits / 4 - 1)))
2143         )), ( BigUint::from_slice([ 1, 2, 3 ]), vec!(
2144             (2,
2145              format!("11{}10{}1",
2146                      "0".repeat(bits - 2),
2147                      "0".repeat(bits - 1))),
2148             (4,
2149              format!("3{}2{}1",
2150                      "0".repeat(bits / 2 - 1),
2151                      "0".repeat(bits / 2 - 1))),
2152             (10, match bits {
2153                 32 => "55340232229718589441".to_string(),
2154                 16 => "12885032961".to_string(),
2155                 _ => fail!()
2156             }),
2157             (16,
2158              format!("3{}2{}1",
2159                      "0".repeat(bits / 4 - 1),
2160                      "0".repeat(bits / 4 - 1)))
2161         )) )
2162     }
2163
2164     #[test]
2165     fn test_to_str_radix() {
2166         let r = to_str_pairs();
2167         for num_pair in r.iter() {
2168             let &(ref n, ref rs) = num_pair;
2169             for str_pair in rs.iter() {
2170                 let &(ref radix, ref str) = str_pair;
2171                 assert_eq!(n.to_str_radix(*radix).as_slice(),
2172                            str.as_slice());
2173             }
2174         }
2175     }
2176
2177     #[test]
2178     fn test_from_str_radix() {
2179         let r = to_str_pairs();
2180         for num_pair in r.iter() {
2181             let &(ref n, ref rs) = num_pair;
2182             for str_pair in rs.iter() {
2183                 let &(ref radix, ref str) = str_pair;
2184                 assert_eq!(n,
2185                            &FromStrRadix::from_str_radix(str.as_slice(),
2186                                                          *radix).unwrap());
2187             }
2188         }
2189
2190         let zed: Option<BigUint> = FromStrRadix::from_str_radix("Z", 10);
2191         assert_eq!(zed, None);
2192         let blank: Option<BigUint> = FromStrRadix::from_str_radix("_", 2);
2193         assert_eq!(blank, None);
2194         let minus_one: Option<BigUint> = FromStrRadix::from_str_radix("-1",
2195                                                                       10);
2196         assert_eq!(minus_one, None);
2197     }
2198
2199     #[test]
2200     fn test_factor() {
2201         fn factor(n: uint) -> BigUint {
2202             let mut f: BigUint = One::one();
2203             for i in range(2, n + 1) {
2204                 // FIXME(#5992): assignment operator overloads
2205                 // f *= FromPrimitive::from_uint(i);
2206                 f = f * FromPrimitive::from_uint(i).unwrap();
2207             }
2208             return f;
2209         }
2210
2211         fn check(n: uint, s: &str) {
2212             let n = factor(n);
2213             let ans = match FromStrRadix::from_str_radix(s, 10) {
2214                 Some(x) => x, None => fail!()
2215             };
2216             assert_eq!(n, ans);
2217         }
2218
2219         check(3, "6");
2220         check(10, "3628800");
2221         check(20, "2432902008176640000");
2222         check(30, "265252859812191058636308480000000");
2223     }
2224
2225     #[test]
2226     fn test_bits() {
2227         assert_eq!(BigUint::new(vec!(0,0,0,0)).bits(), 0);
2228         let n: BigUint = FromPrimitive::from_uint(0).unwrap();
2229         assert_eq!(n.bits(), 0);
2230         let n: BigUint = FromPrimitive::from_uint(1).unwrap();
2231         assert_eq!(n.bits(), 1);
2232         let n: BigUint = FromPrimitive::from_uint(3).unwrap();
2233         assert_eq!(n.bits(), 2);
2234         let n: BigUint = FromStrRadix::from_str_radix("4000000000", 16).unwrap();
2235         assert_eq!(n.bits(), 39);
2236         let one: BigUint = One::one();
2237         assert_eq!((one << 426).bits(), 427);
2238     }
2239
2240     #[test]
2241     fn test_rand() {
2242         let mut rng = task_rng();
2243         let _n: BigUint = rng.gen_biguint(137);
2244         assert!(rng.gen_biguint(0).is_zero());
2245     }
2246
2247     #[test]
2248     fn test_rand_range() {
2249         let mut rng = task_rng();
2250
2251         for _ in range(0u, 10) {
2252             assert_eq!(rng.gen_bigint_range(&FromPrimitive::from_uint(236).unwrap(),
2253                                             &FromPrimitive::from_uint(237).unwrap()),
2254                        FromPrimitive::from_uint(236).unwrap());
2255         }
2256
2257         let l = FromPrimitive::from_uint(403469000 + 2352).unwrap();
2258         let u = FromPrimitive::from_uint(403469000 + 3513).unwrap();
2259         for _ in range(0u, 1000) {
2260             let n: BigUint = rng.gen_biguint_below(&u);
2261             assert!(n < u);
2262
2263             let n: BigUint = rng.gen_biguint_range(&l, &u);
2264             assert!(n >= l);
2265             assert!(n < u);
2266         }
2267     }
2268
2269     #[test]
2270     #[should_fail]
2271     fn test_zero_rand_range() {
2272         task_rng().gen_biguint_range(&FromPrimitive::from_uint(54).unwrap(),
2273                                      &FromPrimitive::from_uint(54).unwrap());
2274     }
2275
2276     #[test]
2277     #[should_fail]
2278     fn test_negative_rand_range() {
2279         let mut rng = task_rng();
2280         let l = FromPrimitive::from_uint(2352).unwrap();
2281         let u = FromPrimitive::from_uint(3513).unwrap();
2282         // Switching u and l should fail:
2283         let _n: BigUint = rng.gen_biguint_range(&u, &l);
2284     }
2285 }
2286
2287 #[cfg(test)]
2288 mod bigint_tests {
2289     use Integer;
2290     use super::{BigDigit, BigUint, ToBigUint};
2291     use super::{Sign, Minus, Zero, Plus, BigInt, RandBigInt, ToBigInt};
2292
2293     use std::cmp::{Less, Equal, Greater};
2294     use std::i64;
2295     use std::num::CheckedDiv;
2296     use std::num::{Zero, One, FromStrRadix, ToStrRadix};
2297     use std::num::{ToPrimitive, FromPrimitive};
2298     use std::rand::task_rng;
2299     use std::u64;
2300     use std::hash::hash;
2301
2302     #[test]
2303     fn test_from_biguint() {
2304         fn check(inp_s: Sign, inp_n: uint, ans_s: Sign, ans_n: uint) {
2305             let inp = BigInt::from_biguint(inp_s, FromPrimitive::from_uint(inp_n).unwrap());
2306             let ans = BigInt { sign: ans_s, data: FromPrimitive::from_uint(ans_n).unwrap()};
2307             assert_eq!(inp, ans);
2308         }
2309         check(Plus, 1, Plus, 1);
2310         check(Plus, 0, Zero, 0);
2311         check(Minus, 1, Minus, 1);
2312         check(Zero, 1, Zero, 0);
2313     }
2314
2315     #[test]
2316     fn test_cmp() {
2317         let vs: [&[BigDigit], ..4] = [ &[2 as BigDigit], &[1, 1], &[2, 1], &[1, 1, 1] ];
2318         let mut nums = Vec::new();
2319         for s in vs.iter().rev() {
2320             nums.push(BigInt::from_slice(Minus, *s));
2321         }
2322         nums.push(Zero::zero());
2323         nums.extend(vs.iter().map(|s| BigInt::from_slice(Plus, *s)));
2324
2325         for (i, ni) in nums.iter().enumerate() {
2326             for (j0, nj) in nums.slice(i, nums.len()).iter().enumerate() {
2327                 let j = i + j0;
2328                 if i == j {
2329                     assert_eq!(ni.cmp(nj), Equal);
2330                     assert_eq!(nj.cmp(ni), Equal);
2331                     assert_eq!(ni, nj);
2332                     assert!(!(ni != nj));
2333                     assert!(ni <= nj);
2334                     assert!(ni >= nj);
2335                     assert!(!(ni < nj));
2336                     assert!(!(ni > nj));
2337                 } else {
2338                     assert_eq!(ni.cmp(nj), Less);
2339                     assert_eq!(nj.cmp(ni), Greater);
2340
2341                     assert!(!(ni == nj));
2342                     assert!(ni != nj);
2343
2344                     assert!(ni <= nj);
2345                     assert!(!(ni >= nj));
2346                     assert!(ni < nj);
2347                     assert!(!(ni > nj));
2348
2349                     assert!(!(nj <= ni));
2350                     assert!(nj >= ni);
2351                     assert!(!(nj < ni));
2352                     assert!(nj > ni);
2353                 }
2354             }
2355         }
2356     }
2357
2358     #[test]
2359     fn test_hash() {
2360         let a = BigInt::new(Zero, vec!());
2361         let b = BigInt::new(Zero, vec!(0));
2362         let c = BigInt::new(Plus, vec!(1));
2363         let d = BigInt::new(Plus, vec!(1,0,0,0,0,0));
2364         let e = BigInt::new(Plus, vec!(0,0,0,0,0,1));
2365         let f = BigInt::new(Minus, vec!(1));
2366         assert!(hash(&a) == hash(&b));
2367         assert!(hash(&b) != hash(&c));
2368         assert!(hash(&c) == hash(&d));
2369         assert!(hash(&d) != hash(&e));
2370         assert!(hash(&c) != hash(&f));
2371     }
2372
2373     #[test]
2374     fn test_convert_i64() {
2375         fn check(b1: BigInt, i: i64) {
2376             let b2: BigInt = FromPrimitive::from_i64(i).unwrap();
2377             assert!(b1 == b2);
2378             assert!(b1.to_i64().unwrap() == i);
2379         }
2380
2381         check(Zero::zero(), 0);
2382         check(One::one(), 1);
2383         check(i64::MIN.to_bigint().unwrap(), i64::MIN);
2384         check(i64::MAX.to_bigint().unwrap(), i64::MAX);
2385
2386         assert_eq!(
2387             (i64::MAX as u64 + 1).to_bigint().unwrap().to_i64(),
2388             None);
2389
2390         assert_eq!(
2391             BigInt::from_biguint(Plus,  BigUint::new(vec!(1, 2, 3, 4, 5))).to_i64(),
2392             None);
2393
2394         assert_eq!(
2395             BigInt::from_biguint(Minus, BigUint::new(vec!(1,0,0,1<<(BigDigit::bits-1)))).to_i64(),
2396             None);
2397
2398         assert_eq!(
2399             BigInt::from_biguint(Minus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_i64(),
2400             None);
2401     }
2402
2403     #[test]
2404     fn test_convert_u64() {
2405         fn check(b1: BigInt, u: u64) {
2406             let b2: BigInt = FromPrimitive::from_u64(u).unwrap();
2407             assert!(b1 == b2);
2408             assert!(b1.to_u64().unwrap() == u);
2409         }
2410
2411         check(Zero::zero(), 0);
2412         check(One::one(), 1);
2413         check(u64::MIN.to_bigint().unwrap(), u64::MIN);
2414         check(u64::MAX.to_bigint().unwrap(), u64::MAX);
2415
2416         assert_eq!(
2417             BigInt::from_biguint(Plus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_u64(),
2418             None);
2419
2420         let max_value: BigUint = FromPrimitive::from_u64(u64::MAX).unwrap();
2421         assert_eq!(BigInt::from_biguint(Minus, max_value).to_u64(), None);
2422         assert_eq!(BigInt::from_biguint(Minus, BigUint::new(vec!(1, 2, 3, 4, 5))).to_u64(), None);
2423     }
2424
2425     #[test]
2426     fn test_convert_to_biguint() {
2427         fn check(n: BigInt, ans_1: BigUint) {
2428             assert_eq!(n.to_biguint().unwrap(), ans_1);
2429             assert_eq!(n.to_biguint().unwrap().to_bigint().unwrap(), n);
2430         }
2431         let zero: BigInt = Zero::zero();
2432         let unsigned_zero: BigUint = Zero::zero();
2433         let positive = BigInt::from_biguint(
2434             Plus, BigUint::new(vec!(1,2,3)));
2435         let negative = -positive;
2436
2437         check(zero, unsigned_zero);
2438         check(positive, BigUint::new(vec!(1,2,3)));
2439
2440         assert_eq!(negative.to_biguint(), None);
2441     }
2442
2443     static sum_triples: &'static [(&'static [BigDigit],
2444                                    &'static [BigDigit],
2445                                    &'static [BigDigit])] = &[
2446         (&[],          &[],       &[]),
2447         (&[],          &[ 1],     &[ 1]),
2448         (&[ 1],        &[ 1],     &[ 2]),
2449         (&[ 1],        &[ 1,  1], &[ 2,  1]),
2450         (&[ 1],        &[-1],     &[ 0,  1]),
2451         (&[ 1],        &[-1, -1], &[ 0,  0, 1]),
2452         (&[-1, -1],    &[-1, -1], &[-2, -1, 1]),
2453         (&[ 1,  1, 1], &[-1, -1], &[ 0,  1, 2]),
2454         (&[ 2,  2, 1], &[-1, -2], &[ 1,  1, 2])
2455     ];
2456
2457     #[test]
2458     fn test_add() {
2459         for elm in sum_triples.iter() {
2460             let (a_vec, b_vec, c_vec) = *elm;
2461             let a = BigInt::from_slice(Plus, a_vec);
2462             let b = BigInt::from_slice(Plus, b_vec);
2463             let c = BigInt::from_slice(Plus, c_vec);
2464
2465             assert!(a + b == c);
2466             assert!(b + a == c);
2467             assert!(c + (-a) == b);
2468             assert!(c + (-b) == a);
2469             assert!(a + (-c) == (-b));
2470             assert!(b + (-c) == (-a));
2471             assert!((-a) + (-b) == (-c))
2472             assert!(a + (-a) == Zero::zero());
2473         }
2474     }
2475
2476     #[test]
2477     fn test_sub() {
2478         for elm in sum_triples.iter() {
2479             let (a_vec, b_vec, c_vec) = *elm;
2480             let a = BigInt::from_slice(Plus, a_vec);
2481             let b = BigInt::from_slice(Plus, b_vec);
2482             let c = BigInt::from_slice(Plus, c_vec);
2483
2484             assert!(c - a == b);
2485             assert!(c - b == a);
2486             assert!((-b) - a == (-c))
2487             assert!((-a) - b == (-c))
2488             assert!(b - (-a) == c);
2489             assert!(a - (-b) == c);
2490             assert!((-c) - (-a) == (-b));
2491             assert!(a - a == Zero::zero());
2492         }
2493     }
2494
2495     static mul_triples: &'static [(&'static [BigDigit],
2496                                    &'static [BigDigit],
2497                                    &'static [BigDigit])] = &[
2498         (&[],               &[],               &[]),
2499         (&[],               &[ 1],             &[]),
2500         (&[ 2],             &[],               &[]),
2501         (&[ 1],             &[ 1],             &[1]),
2502         (&[ 2],             &[ 3],             &[ 6]),
2503         (&[ 1],             &[ 1,  1,  1],     &[1, 1,  1]),
2504         (&[ 1,  2,  3],     &[ 3],             &[ 3,  6,  9]),
2505         (&[ 1,  1,  1],     &[-1],             &[-1, -1, -1]),
2506         (&[ 1,  2,  3],     &[-1],             &[-1, -2, -2, 2]),
2507         (&[ 1,  2,  3,  4], &[-1],             &[-1, -2, -2, -2, 3]),
2508         (&[-1],             &[-1],             &[ 1, -2]),
2509         (&[-1, -1],         &[-1],             &[ 1, -1, -2]),
2510         (&[-1, -1, -1],     &[-1],             &[ 1, -1, -1, -2]),
2511         (&[-1, -1, -1, -1], &[-1],             &[ 1, -1, -1, -1, -2]),
2512         (&[-1/2 + 1],       &[ 2],             &[ 0,  1]),
2513         (&[0, -1/2 + 1],    &[ 2],             &[ 0,  0,  1]),
2514         (&[ 1,  2],         &[ 1,  2,  3],     &[1, 4,  7,  6]),
2515         (&[-1, -1],         &[-1, -1, -1],     &[1, 0, -1, -2, -1]),
2516         (&[-1, -1, -1],     &[-1, -1, -1, -1], &[1, 0,  0, -1, -2, -1, -1]),
2517         (&[ 0,  0,  1],     &[ 1,  2,  3],     &[0, 0,  1,  2,  3]),
2518         (&[ 0,  0,  1],     &[ 0,  0,  0,  1], &[0, 0,  0,  0,  0,  1])
2519     ];
2520
2521     static div_rem_quadruples: &'static [(&'static [BigDigit],
2522                                           &'static [BigDigit],
2523                                           &'static [BigDigit],
2524                                           &'static [BigDigit])]
2525         = &[
2526             (&[ 1],        &[ 2], &[],               &[1]),
2527             (&[ 1,  1],    &[ 2], &[-1/2+1],         &[1]),
2528             (&[ 1,  1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
2529             (&[ 0,  1],    &[-1], &[1],              &[1]),
2530             (&[-1, -1],    &[-2], &[2, 1],           &[3])
2531         ];
2532
2533     #[test]
2534     fn test_mul() {
2535         for elm in mul_triples.iter() {
2536             let (a_vec, b_vec, c_vec) = *elm;
2537             let a = BigInt::from_slice(Plus, a_vec);
2538             let b = BigInt::from_slice(Plus, b_vec);
2539             let c = BigInt::from_slice(Plus, c_vec);
2540
2541             assert!(a * b == c);
2542             assert!(b * a == c);
2543
2544             assert!((-a) * b == -c);
2545             assert!((-b) * a == -c);
2546         }
2547
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);
2554
2555             assert!(a == b * c + d);
2556             assert!(a == c * b + d);
2557         }
2558     }
2559
2560     #[test]
2561     fn test_div_mod_floor() {
2562         fn check_sub(a: &BigInt, b: &BigInt, ans_d: &BigInt, ans_m: &BigInt) {
2563             let (d, m) = a.div_mod_floor(b);
2564             if !m.is_zero() {
2565                 assert_eq!(m.sign, b.sign);
2566             }
2567             assert!(m.abs() <= b.abs());
2568             assert!(*a == b * d + m);
2569             assert!(d == *ans_d);
2570             assert!(m == *ans_m);
2571         }
2572
2573         fn check(a: &BigInt, b: &BigInt, d: &BigInt, m: &BigInt) {
2574             if m.is_zero() {
2575                 check_sub(a, b, d, m);
2576                 check_sub(a, &b.neg(), &d.neg(), m);
2577                 check_sub(&a.neg(), b, &d.neg(), m);
2578                 check_sub(&a.neg(), &b.neg(), d, m);
2579             } else {
2580                 check_sub(a, b, d, m);
2581                 check_sub(a, &b.neg(), &(d.neg() - One::one()), &(m - *b));
2582                 check_sub(&a.neg(), b, &(d.neg() - One::one()), &(b - *m));
2583                 check_sub(&a.neg(), &b.neg(), d, &m.neg());
2584             }
2585         }
2586
2587         for elm in mul_triples.iter() {
2588             let (a_vec, b_vec, c_vec) = *elm;
2589             let a = BigInt::from_slice(Plus, a_vec);
2590             let b = BigInt::from_slice(Plus, b_vec);
2591             let c = BigInt::from_slice(Plus, c_vec);
2592
2593             if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
2594             if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
2595         }
2596
2597         for elm in div_rem_quadruples.iter() {
2598             let (a_vec, b_vec, c_vec, d_vec) = *elm;
2599             let a = BigInt::from_slice(Plus, a_vec);
2600             let b = BigInt::from_slice(Plus, b_vec);
2601             let c = BigInt::from_slice(Plus, c_vec);
2602             let d = BigInt::from_slice(Plus, d_vec);
2603
2604             if !b.is_zero() {
2605                 check(&a, &b, &c, &d);
2606             }
2607         }
2608     }
2609
2610
2611     #[test]
2612     fn test_div_rem() {
2613         fn check_sub(a: &BigInt, b: &BigInt, ans_q: &BigInt, ans_r: &BigInt) {
2614             let (q, r) = a.div_rem(b);
2615             if !r.is_zero() {
2616                 assert_eq!(r.sign, a.sign);
2617             }
2618             assert!(r.abs() <= b.abs());
2619             assert!(*a == b * q + r);
2620             assert!(q == *ans_q);
2621             assert!(r == *ans_r);
2622         }
2623
2624         fn check(a: &BigInt, b: &BigInt, q: &BigInt, r: &BigInt) {
2625             check_sub(a, b, q, r);
2626             check_sub(a, &b.neg(), &q.neg(), r);
2627             check_sub(&a.neg(), b, &q.neg(), &r.neg());
2628             check_sub(&a.neg(), &b.neg(), q, &r.neg());
2629         }
2630         for elm in mul_triples.iter() {
2631             let (a_vec, b_vec, c_vec) = *elm;
2632             let a = BigInt::from_slice(Plus, a_vec);
2633             let b = BigInt::from_slice(Plus, b_vec);
2634             let c = BigInt::from_slice(Plus, c_vec);
2635
2636             if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
2637             if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
2638         }
2639
2640         for elm in div_rem_quadruples.iter() {
2641             let (a_vec, b_vec, c_vec, d_vec) = *elm;
2642             let a = BigInt::from_slice(Plus, a_vec);
2643             let b = BigInt::from_slice(Plus, b_vec);
2644             let c = BigInt::from_slice(Plus, c_vec);
2645             let d = BigInt::from_slice(Plus, d_vec);
2646
2647             if !b.is_zero() {
2648                 check(&a, &b, &c, &d);
2649             }
2650         }
2651     }
2652
2653     #[test]
2654     fn test_checked_add() {
2655         for elm in sum_triples.iter() {
2656             let (a_vec, b_vec, c_vec) = *elm;
2657             let a = BigInt::from_slice(Plus, a_vec);
2658             let b = BigInt::from_slice(Plus, b_vec);
2659             let c = BigInt::from_slice(Plus, c_vec);
2660
2661             assert!(a.checked_add(&b).unwrap() == c);
2662             assert!(b.checked_add(&a).unwrap() == c);
2663             assert!(c.checked_add(&(-a)).unwrap() == b);
2664             assert!(c.checked_add(&(-b)).unwrap() == a);
2665             assert!(a.checked_add(&(-c)).unwrap() == (-b));
2666             assert!(b.checked_add(&(-c)).unwrap() == (-a));
2667             assert!((-a).checked_add(&(-b)).unwrap() == (-c))
2668             assert!(a.checked_add(&(-a)).unwrap() == Zero::zero());
2669         }
2670     }
2671
2672     #[test]
2673     fn test_checked_sub() {
2674         for elm in sum_triples.iter() {
2675             let (a_vec, b_vec, c_vec) = *elm;
2676             let a = BigInt::from_slice(Plus, a_vec);
2677             let b = BigInt::from_slice(Plus, b_vec);
2678             let c = BigInt::from_slice(Plus, c_vec);
2679
2680             assert!(c.checked_sub(&a).unwrap() == b);
2681             assert!(c.checked_sub(&b).unwrap() == a);
2682             assert!((-b).checked_sub(&a).unwrap() == (-c))
2683             assert!((-a).checked_sub(&b).unwrap() == (-c))
2684             assert!(b.checked_sub(&(-a)).unwrap() == c);
2685             assert!(a.checked_sub(&(-b)).unwrap() == c);
2686             assert!((-c).checked_sub(&(-a)).unwrap() == (-b));
2687             assert!(a.checked_sub(&a).unwrap() == Zero::zero());
2688         }
2689     }
2690
2691     #[test]
2692     fn test_checked_mul() {
2693         for elm in mul_triples.iter() {
2694             let (a_vec, b_vec, c_vec) = *elm;
2695             let a = BigInt::from_slice(Plus, a_vec);
2696             let b = BigInt::from_slice(Plus, b_vec);
2697             let c = BigInt::from_slice(Plus, c_vec);
2698
2699             assert!(a.checked_mul(&b).unwrap() == c);
2700             assert!(b.checked_mul(&a).unwrap() == c);
2701
2702             assert!((-a).checked_mul(&b).unwrap() == -c);
2703             assert!((-b).checked_mul(&a).unwrap() == -c);
2704         }
2705
2706         for elm in div_rem_quadruples.iter() {
2707             let (a_vec, b_vec, c_vec, d_vec) = *elm;
2708             let a = BigInt::from_slice(Plus, a_vec);
2709             let b = BigInt::from_slice(Plus, b_vec);
2710             let c = BigInt::from_slice(Plus, c_vec);
2711             let d = BigInt::from_slice(Plus, d_vec);
2712
2713             assert!(a == b.checked_mul(&c).unwrap() + d);
2714             assert!(a == c.checked_mul(&b).unwrap() + d);
2715         }
2716     }
2717     #[test]
2718     fn test_checked_div() {
2719         for elm in mul_triples.iter() {
2720             let (a_vec, b_vec, c_vec) = *elm;
2721             let a = BigInt::from_slice(Plus, a_vec);
2722             let b = BigInt::from_slice(Plus, b_vec);
2723             let c = BigInt::from_slice(Plus, c_vec);
2724
2725             if !a.is_zero() {
2726                 assert!(c.checked_div(&a).unwrap() == b);
2727                 assert!((-c).checked_div(&(-a)).unwrap() == b);
2728                 assert!((-c).checked_div(&a).unwrap() == -b);
2729             }
2730             if !b.is_zero() {
2731                 assert!(c.checked_div(&b).unwrap() == a);
2732                 assert!((-c).checked_div(&(-b)).unwrap() == a);
2733                 assert!((-c).checked_div(&b).unwrap() == -a);
2734             }
2735
2736             assert!(c.checked_div(&Zero::zero()).is_none());
2737             assert!((-c).checked_div(&Zero::zero()).is_none());
2738         }
2739     }
2740
2741     #[test]
2742     fn test_gcd() {
2743         fn check(a: int, b: int, c: int) {
2744             let big_a: BigInt = FromPrimitive::from_int(a).unwrap();
2745             let big_b: BigInt = FromPrimitive::from_int(b).unwrap();
2746             let big_c: BigInt = FromPrimitive::from_int(c).unwrap();
2747
2748             assert_eq!(big_a.gcd(&big_b), big_c);
2749         }
2750
2751         check(10, 2, 2);
2752         check(10, 3, 1);
2753         check(0, 3, 3);
2754         check(3, 3, 3);
2755         check(56, 42, 14);
2756         check(3, -3, 3);
2757         check(-6, 3, 3);
2758         check(-4, -2, 2);
2759     }
2760
2761     #[test]
2762     fn test_lcm() {
2763         fn check(a: int, b: int, c: int) {
2764             let big_a: BigInt = FromPrimitive::from_int(a).unwrap();
2765             let big_b: BigInt = FromPrimitive::from_int(b).unwrap();
2766             let big_c: BigInt = FromPrimitive::from_int(c).unwrap();
2767
2768             assert_eq!(big_a.lcm(&big_b), big_c);
2769         }
2770
2771         check(1, 0, 0);
2772         check(0, 1, 0);
2773         check(1, 1, 1);
2774         check(-1, 1, 1);
2775         check(1, -1, 1);
2776         check(-1, -1, 1);
2777         check(8, 9, 72);
2778         check(11, 5, 55);
2779     }
2780
2781     #[test]
2782     fn test_abs_sub() {
2783         let zero: BigInt = Zero::zero();
2784         let one: BigInt = One::one();
2785         assert_eq!((-one).abs_sub(&one), zero);
2786         let one: BigInt = One::one();
2787         let zero: BigInt = Zero::zero();
2788         assert_eq!(one.abs_sub(&one), zero);
2789         let one: BigInt = One::one();
2790         let zero: BigInt = Zero::zero();
2791         assert_eq!(one.abs_sub(&zero), one);
2792         let one: BigInt = One::one();
2793         let two: BigInt = FromPrimitive::from_int(2).unwrap();
2794         assert_eq!(one.abs_sub(&-one), two);
2795     }
2796
2797     #[test]
2798     fn test_to_str_radix() {
2799         fn check(n: int, ans: &str) {
2800             let n: BigInt = FromPrimitive::from_int(n).unwrap();
2801             assert!(ans == n.to_str_radix(10).as_slice());
2802         }
2803         check(10, "10");
2804         check(1, "1");
2805         check(0, "0");
2806         check(-1, "-1");
2807         check(-10, "-10");
2808     }
2809
2810
2811     #[test]
2812     fn test_from_str_radix() {
2813         fn check(s: &str, ans: Option<int>) {
2814             let ans = ans.map(|n| {
2815                 let x: BigInt = FromPrimitive::from_int(n).unwrap();
2816                 x
2817             });
2818             assert_eq!(FromStrRadix::from_str_radix(s, 10), ans);
2819         }
2820         check("10", Some(10));
2821         check("1", Some(1));
2822         check("0", Some(0));
2823         check("-1", Some(-1));
2824         check("-10", Some(-10));
2825         check("Z", None);
2826         check("_", None);
2827
2828         // issue 10522, this hit an edge case that caused it to
2829         // attempt to allocate a vector of size (-1u) == huge.
2830         let x: BigInt =
2831             from_str(format!("1{}", "0".repeat(36)).as_slice()).unwrap();
2832         let _y = x.to_string();
2833     }
2834
2835     #[test]
2836     fn test_neg() {
2837         assert!(-BigInt::new(Plus,  vec!(1, 1, 1)) ==
2838             BigInt::new(Minus, vec!(1, 1, 1)));
2839         assert!(-BigInt::new(Minus, vec!(1, 1, 1)) ==
2840             BigInt::new(Plus,  vec!(1, 1, 1)));
2841         let zero: BigInt = Zero::zero();
2842         assert_eq!(-zero, zero);
2843     }
2844
2845     #[test]
2846     fn test_rand() {
2847         let mut rng = task_rng();
2848         let _n: BigInt = rng.gen_bigint(137);
2849         assert!(rng.gen_bigint(0).is_zero());
2850     }
2851
2852     #[test]
2853     fn test_rand_range() {
2854         let mut rng = task_rng();
2855
2856         for _ in range(0u, 10) {
2857             assert_eq!(rng.gen_bigint_range(&FromPrimitive::from_uint(236).unwrap(),
2858                                             &FromPrimitive::from_uint(237).unwrap()),
2859                        FromPrimitive::from_uint(236).unwrap());
2860         }
2861
2862         fn check(l: BigInt, u: BigInt) {
2863             let mut rng = task_rng();
2864             for _ in range(0u, 1000) {
2865                 let n: BigInt = rng.gen_bigint_range(&l, &u);
2866                 assert!(n >= l);
2867                 assert!(n < u);
2868             }
2869         }
2870         let l: BigInt = FromPrimitive::from_uint(403469000 + 2352).unwrap();
2871         let u: BigInt = FromPrimitive::from_uint(403469000 + 3513).unwrap();
2872         check( l.clone(),  u.clone());
2873         check(-l.clone(),  u.clone());
2874         check(-u.clone(), -l.clone());
2875     }
2876
2877     #[test]
2878     #[should_fail]
2879     fn test_zero_rand_range() {
2880         task_rng().gen_bigint_range(&FromPrimitive::from_int(54).unwrap(),
2881                                     &FromPrimitive::from_int(54).unwrap());
2882     }
2883
2884     #[test]
2885     #[should_fail]
2886     fn test_negative_rand_range() {
2887         let mut rng = task_rng();
2888         let l = FromPrimitive::from_uint(2352).unwrap();
2889         let u = FromPrimitive::from_uint(3513).unwrap();
2890         // Switching u and l should fail:
2891         let _n: BigInt = rng.gen_bigint_range(&u, &l);
2892     }
2893 }
2894
2895 #[cfg(test)]
2896 mod bench {
2897     extern crate test;
2898     use self::test::Bencher;
2899     use super::BigUint;
2900     use std::iter;
2901     use std::mem::replace;
2902     use std::num::{FromPrimitive, Zero, One};
2903
2904     fn factorial(n: uint) -> BigUint {
2905         let mut f: BigUint = One::one();
2906         for i in iter::range_inclusive(1, n) {
2907             f = f * FromPrimitive::from_uint(i).unwrap();
2908         }
2909         f
2910     }
2911
2912     fn fib(n: uint) -> BigUint {
2913         let mut f0: BigUint = Zero::zero();
2914         let mut f1: BigUint = One::one();
2915         for _ in range(0, n) {
2916             let f2 = f0 + f1;
2917             f0 = replace(&mut f1, f2);
2918         }
2919         f0
2920     }
2921
2922     #[bench]
2923     fn factorial_100(b: &mut Bencher) {
2924         b.iter(|| {
2925             factorial(100);
2926         });
2927     }
2928
2929     #[bench]
2930     fn fib_100(b: &mut Bencher) {
2931         b.iter(|| {
2932             fib(100);
2933         });
2934     }
2935
2936     #[bench]
2937     fn to_string(b: &mut Bencher) {
2938         let fac = factorial(100);
2939         let fib = fib(100);
2940         b.iter(|| {
2941             fac.to_string();
2942         });
2943         b.iter(|| {
2944             fib.to_string();
2945         });
2946     }
2947
2948     #[bench]
2949     fn shr(b: &mut Bencher) {
2950         let n = { let one : BigUint = One::one(); one << 1000 };
2951         b.iter(|| {
2952             let mut m = n.clone();
2953             for _ in range(0u, 10) {
2954                 m = m >> 1;
2955             }
2956         })
2957     }
2958 }