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