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