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