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