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