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