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