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