src/libstd/num/bigint.rs

   1 // Copyright 2013 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 BigDigits.
  16 A BigInt is a combination of BigUint and Sign.
  17 */
  18
  19 #[deny(vecs_implicitly_copyable)];
  20 #[deny(deprecated_mutable_fields)];
  21
  22 use core::cmp::{Eq, Ord, TotalEq, TotalOrd, Ordering, Less, Equal, Greater};
  23 use core::num::{IntConvertible, Zero, One, ToStrRadix, FromStrRadix};
  24 use core::*;
  25
  26 /**
  27 A BigDigit is a BigUint's composing element.
  28
  29 A BigDigit is half the size of machine word size.
  30 */
  31 #[cfg(target_arch = "x86")]
  32 #[cfg(target_arch = "arm")]
  33 #[cfg(target_arch = "mips")]
  34 pub type BigDigit = u16;
  35
  36 /**
  37 A BigDigit is a BigUint's composing element.
  38
  39 A BigDigit is half the size of machine word size.
  40 */
  41 #[cfg(target_arch = "x86_64")]
  42 pub type BigDigit = u32;
  43
  44 pub mod BigDigit {
  45     use bigint::BigDigit;
  46
  47     #[cfg(target_arch = "x86")]
  48     #[cfg(target_arch = "arm")]
  49     #[cfg(target_arch = "mips")]
  50     pub static bits: uint = 16;
  51
  52     #[cfg(target_arch = "x86_64")]
  53     pub static bits: uint = 32;
  54
  55     pub static base: uint = 1 << bits;
  56     priv static hi_mask: uint = (-1 as uint) << bits;
  57     priv static lo_mask: uint = (-1 as uint) >> bits;
  58
  59     #[inline(always)]
  60     priv fn get_hi(n: uint) -> BigDigit { (n >> bits) as BigDigit }
  61     #[inline(always)]
  62     priv fn get_lo(n: uint) -> BigDigit { (n & lo_mask) as BigDigit }
  63
  64     /// Split one machine sized unsigned integer into two BigDigits.
  65     #[inline(always)]
  66     pub fn from_uint(n: uint) -> (BigDigit, BigDigit) {
  67         (get_hi(n), get_lo(n))
  68     }
  69
  70     /// Join two BigDigits into one machine sized unsigned integer
  71     #[inline(always)]
  72     pub fn to_uint(hi: BigDigit, lo: BigDigit) -> uint {
  73         (lo as uint) | ((hi as uint) << bits)
  74     }
  75 }
  76
  77 /**
  78 A big unsigned integer type.
  79
  80 A BigUint-typed value BigUint { data: @[a, b, c] } represents a number
  81 (a + b * BigDigit::base + c * BigDigit::base^2).
  82 */
  83 pub struct BigUint {
  84     priv data: ~[BigDigit]
  85 }
  86
  87 impl Eq for BigUint {
  88     #[inline(always)]
  89     fn eq(&self, other: &BigUint) -> bool { self.equals(other) }
  90     #[inline(always)]
  91     fn ne(&self, other: &BigUint) -> bool { !self.equals(other) }
  92 }
  93
  94 impl TotalEq for BigUint {
  95     #[inline(always)]
  96     fn equals(&self, other: &BigUint) -> bool {
  97         match self.cmp(other) { Equal => true, _ => false }
  98     }
  99 }
 100
 101 impl Ord for BigUint {
 102     #[inline(always)]
 103     fn lt(&self, other: &BigUint) -> bool {
 104         match self.cmp(other) { Less => true, _ => false}
 105     }
 106     #[inline(always)]
 107     fn le(&self, other: &BigUint) -> bool {
 108         match self.cmp(other) { Less | Equal => true, _ => false }
 109     }
 110     #[inline(always)]
 111     fn ge(&self, other: &BigUint) -> bool {
 112         match self.cmp(other) { Greater | Equal => true, _ => false }
 113     }
 114     #[inline(always)]
 115     fn gt(&self, other: &BigUint) -> bool {
 116         match self.cmp(other) { Greater => true, _ => false }
 117     }
 118 }
 119
 120 impl TotalOrd for BigUint {
 121     #[inline(always)]
 122     fn cmp(&self, other: &BigUint) -> Ordering {
 123         let s_len = self.data.len(), o_len = other.data.len();
 124         if s_len < o_len { return Less; }
 125         if s_len > o_len { return Greater;  }
 126
 127         for self.data.eachi_reverse |i, elm| {
 128             match (*elm, other.data[i]) {
 129                 (l, r) if l < r => return Less,
 130                 (l, r) if l > r => return Greater,
 131                 _               => loop
 132             };
 133         }
 134         return Equal;
 135     }
 136 }
 137
 138 impl ToStr for BigUint {
 139     #[inline(always)]
 140     fn to_str(&self) -> ~str { self.to_str_radix(10) }
 141 }
 142
 143 impl from_str::FromStr for BigUint {
 144     #[inline(always)]
 145     fn from_str(s: &str) -> Option<BigUint> {
 146         FromStrRadix::from_str_radix(s, 10)
 147     }
 148 }
 149
 150 impl Shl<uint, BigUint> for BigUint {
 151     #[inline(always)]
 152     fn shl(&self, rhs: &uint) -> BigUint {
 153         let n_unit = *rhs / BigDigit::bits;
 154         let n_bits = *rhs % BigDigit::bits;
 155         return self.shl_unit(n_unit).shl_bits(n_bits);
 156     }
 157 }
 158
 159 impl Shr<uint, BigUint> for BigUint {
 160     #[inline(always)]
 161     fn shr(&self, rhs: &uint) -> BigUint {
 162         let n_unit = *rhs / BigDigit::bits;
 163         let n_bits = *rhs % BigDigit::bits;
 164         return self.shr_unit(n_unit).shr_bits(n_bits);
 165     }
 166 }
 167
 168 impl Zero for BigUint {
 169     #[inline(always)]
 170     fn zero() -> BigUint { BigUint::new(~[]) }
 171
 172     #[inline(always)]
 173     fn is_zero(&self) -> bool { self.data.is_empty() }
 174 }
 175
 176 impl One for BigUint {
 177     #[inline(always)]
 178     fn one() -> BigUint { BigUint::new(~[1]) }
 179 }
 180
 181 impl Unsigned for BigUint {}
 182
 183 impl Add<BigUint, BigUint> for BigUint {
 184     #[inline(always)]
 185     fn add(&self, other: &BigUint) -> BigUint {
 186         let new_len = uint::max(self.data.len(), other.data.len());
 187
 188         let mut carry = 0;
 189         let sum = do vec::from_fn(new_len) |i| {
 190             let ai = if i < self.data.len()  { self.data[i]  } else { 0 };
 191             let bi = if i < other.data.len() { other.data[i] } else { 0 };
 192             let (hi, lo) = BigDigit::from_uint(
 193                 (ai as uint) + (bi as uint) + (carry as uint)
 194             );
 195             carry = hi;
 196             lo
 197         };
 198         if carry == 0 { return BigUint::new(sum) };
 199         return BigUint::new(sum + [carry]);
 200     }
 201 }
 202
 203 impl Sub<BigUint, BigUint> for BigUint {
 204     #[inline(always)]
 205     fn sub(&self, other: &BigUint) -> BigUint {
 206         let new_len = uint::max(self.data.len(), other.data.len());
 207
 208         let mut borrow = 0;
 209         let diff = do vec::from_fn(new_len) |i| {
 210             let ai = if i < self.data.len()  { self.data[i]  } else { 0 };
 211             let bi = if i < other.data.len() { other.data[i] } else { 0 };
 212             let (hi, lo) = BigDigit::from_uint(
 213                 (BigDigit::base) +
 214                 (ai as uint) - (bi as uint) - (borrow as uint)
 215             );
 216             /*
 217             hi * (base) + lo == 1*(base) + ai - bi - borrow
 218             => ai - bi - borrow < 0 <=> hi == 0
 219             */
 220             borrow = if hi == 0 { 1 } else { 0 };
 221             lo
 222         };
 223
 224         assert!(borrow == 0);     // <=> assert!((self >= other));
 225         return BigUint::new(diff);
 226     }
 227 }
 228
 229 impl Mul<BigUint, BigUint> for BigUint {
 230     fn mul(&self, other: &BigUint) -> BigUint {
 231         if self.is_zero() || other.is_zero() { return Zero::zero(); }
 232
 233         let s_len = self.data.len(), o_len = other.data.len();
 234         if s_len == 1 { return mul_digit(other, self.data[0]);  }
 235         if o_len == 1 { return mul_digit(self,  other.data[0]); }
 236
 237         // Using Karatsuba multiplication
 238         // (a1 * base + a0) * (b1 * base + b0)
 239         // = a1*b1 * base^2 +
 240         //   (a1*b1 + a0*b0 - (a1-b0)*(b1-a0)) * base +
 241         //   a0*b0
 242         let half_len = uint::max(s_len, o_len) / 2;
 243         let (sHi, sLo) = cut_at(self,  half_len);
 244         let (oHi, oLo) = cut_at(other, half_len);
 245
 246         let ll = sLo * oLo;
 247         let hh = sHi * oHi;
 248         let mm = {
 249             let (s1, n1) = sub_sign(sHi, sLo);
 250             let (s2, n2) = sub_sign(oHi, oLo);
 251             match (s1, s2) {
 252                 (Equal, _) | (_, Equal) => hh + ll,
 253                 (Less, Greater) | (Greater, Less) => hh + ll + (n1 * n2),
 254                 (Less, Less) | (Greater, Greater) => hh + ll - (n1 * n2)
 255             }
 256         };
 257
 258         return ll + mm.shl_unit(half_len) + hh.shl_unit(half_len * 2);
 259
 260         #[inline(always)]
 261         fn mul_digit(a: &BigUint, n: BigDigit) -> BigUint {
 262             if n == 0 { return Zero::zero(); }
 263             if n == 1 { return copy *a; }
 264
 265             let mut carry = 0;
 266             let prod = do vec::map(a.data) |ai| {
 267                 let (hi, lo) = BigDigit::from_uint(
 268                     (*ai as uint) * (n as uint) + (carry as uint)
 269                 );
 270                 carry = hi;
 271                 lo
 272             };
 273             if carry == 0 { return BigUint::new(prod) };
 274             return BigUint::new(prod + [carry]);
 275         }
 276
 277         #[inline(always)]
 278         fn cut_at(a: &BigUint, n: uint) -> (BigUint, BigUint) {
 279             let mid = uint::min(a.data.len(), n);
 280             return (BigUint::from_slice(vec::slice(a.data, mid,
 281                                                    a.data.len())),
 282                     BigUint::from_slice(vec::slice(a.data, 0, mid)));
 283         }
 284
 285         #[inline(always)]
 286         fn sub_sign(a: BigUint, b: BigUint) -> (Ordering, BigUint) {
 287             match a.cmp(&b) {
 288                 Less    => (Less,    b - a),
 289                 Greater => (Greater, a - b),
 290                 _       => (Equal,   Zero::zero())
 291             }
 292         }
 293     }
 294 }
 295
 296 impl Quot<BigUint, BigUint> for BigUint {
 297     #[inline(always)]
 298     fn quot(&self, other: &BigUint) -> BigUint {
 299         let (q, _) = self.quot_rem(other);
 300         return q;
 301     }
 302 }
 303
 304 impl Rem<BigUint, BigUint> for BigUint {
 305     #[inline(always)]
 306     fn rem(&self, other: &BigUint) -> BigUint {
 307         let (_, r) = self.quot_rem(other);
 308         return r;
 309     }
 310 }
 311
 312 impl Neg<BigUint> for BigUint {
 313     #[inline(always)]
 314     fn neg(&self) -> BigUint { fail!() }
 315 }
 316
 317 impl Integer for BigUint {
 318     #[inline(always)]
 319     fn div(&self, other: &BigUint) -> BigUint {
 320         let (d, _) = self.div_mod(other);
 321         return d;
 322     }
 323
 324     #[inline(always)]
 325     fn modulo(&self, other: &BigUint) -> BigUint {
 326         let (_, m) = self.div_mod(other);
 327         return m;
 328     }
 329
 330     #[inline(always)]
 331     fn div_mod(&self, other: &BigUint) -> (BigUint, BigUint) {
 332         if other.is_zero() { fail!() }
 333         if self.is_zero() { return (Zero::zero(), Zero::zero()); }
 334         if *other == One::one() { return (copy *self, Zero::zero()); }
 335
 336         match self.cmp(other) {
 337             Less    => return (Zero::zero(), copy *self),
 338             Equal   => return (One::one(), Zero::zero()),
 339             Greater => {} // Do nothing
 340         }
 341
 342         let mut shift = 0;
 343         let mut n = *other.data.last();
 344         while n < (1 << BigDigit::bits - 2) {
 345             n <<= 1;
 346             shift += 1;
 347         }
 348         assert!(shift < BigDigit::bits);
 349         let (d, m) = div_mod_inner(self << shift, other << shift);
 350         return (d, m >> shift);
 351
 352         #[inline(always)]
 353         fn div_mod_inner(a: BigUint, b: BigUint) -> (BigUint, BigUint) {
 354             let mut m = a;
 355             let mut d = Zero::zero::<BigUint>();
 356             let mut n = 1;
 357             while m >= b {
 358                 let mut (d0, d_unit, b_unit) = div_estimate(&m, &b, n);
 359                 let mut prod = b * d0;
 360                 while prod > m {
 361                     // FIXME(#6050): overloaded operators force moves with generic types
 362                     // d0 -= d_unit
 363                     d0   = d0 - d_unit;
 364                     // FIXME(#6050): overloaded operators force moves with generic types
 365                     // prod = prod - b_unit;
 366                     prod = prod - b_unit
 367                 }
 368                 if d0.is_zero() {
 369                     n = 2;
 370                     loop;
 371                 }
 372                 n = 1;
 373                 // FIXME(#6102): Assignment operator for BigInt causes ICE
 374                 // d += d0;
 375                 d = d + d0;
 376                 // FIXME(#6102): Assignment operator for BigInt causes ICE
 377                 // m -= prod;
 378                 m = m - prod;
 379             }
 380             return (d, m);
 381         }
 382
 383         #[inline(always)]
 384         fn div_estimate(a: &BigUint, b: &BigUint, n: uint)
 385             -> (BigUint, BigUint, BigUint) {
 386             if a.data.len() < n {
 387                 return (Zero::zero(), Zero::zero(), copy *a);
 388             }
 389
 390             let an = vec::slice(a.data, a.data.len() - n, a.data.len());
 391             let bn = *b.data.last();
 392             let mut d = ~[];
 393             let mut carry = 0;
 394             for an.each_reverse |elt| {
 395                 let ai = BigDigit::to_uint(carry, *elt);
 396                 let di = ai / (bn as uint);
 397                 assert!(di < BigDigit::base);
 398                 carry = (ai % (bn as uint)) as BigDigit;
 399                 d = ~[di as BigDigit] + d;
 400             }
 401
 402             let shift = (a.data.len() - an.len()) - (b.data.len() - 1);
 403             if shift == 0 {
 404                 return (BigUint::new(d), One::one(), copy *b);
 405             }
 406             return (BigUint::from_slice(d).shl_unit(shift),
 407                     One::one::<BigUint>().shl_unit(shift),
 408                     b.shl_unit(shift));
 409         }
 410     }
 411
 412     #[inline(always)]
 413     fn quot_rem(&self, other: &BigUint) -> (BigUint, BigUint) {
 414         self.div_mod(other)
 415     }
 416
 417     /**
 418      * Calculates the Greatest Common Divisor (GCD) of the number and `other`
 419      *
 420      * The result is always positive
 421      */
 422     #[inline(always)]
 423     fn gcd(&self, other: &BigUint) -> BigUint {
 424         // Use Euclid's algorithm
 425         let mut m = copy *self, n = copy *other;
 426         while !m.is_zero() {
 427             let temp = m;
 428             m = n % temp;
 429             n = temp;
 430         }
 431         return n;
 432     }
 433
 434     /**
 435      * Calculates the Lowest Common Multiple (LCM) of the number and `other`
 436      */
 437     #[inline(always)]
 438     fn lcm(&self, other: &BigUint) -> BigUint { ((*self * *other) / self.gcd(other)) }
 439
 440     /// Returns `true` if the number can be divided by `other` without leaving a remainder
 441     #[inline(always)]
 442     fn is_multiple_of(&self, other: &BigUint) -> bool { (*self % *other).is_zero() }
 443
 444     /// Returns `true` if the number is divisible by `2`
 445     #[inline(always)]
 446     fn is_even(&self) -> bool {
 447         // Considering only the last digit.
 448         if self.data.is_empty() {
 449             true
 450         } else {
 451             self.data.last().is_even()
 452         }
 453     }
 454
 455     /// Returns `true` if the number is not divisible by `2`
 456     #[inline(always)]
 457     fn is_odd(&self) -> bool { !self.is_even() }
 458 }
 459
 460 impl IntConvertible for BigUint {
 461     #[inline(always)]
 462     fn to_int(&self) -> int {
 463         uint::min(self.to_uint(), int::max_value as uint) as int
 464     }
 465
 466     #[inline(always)]
 467     fn from_int(n: int) -> BigUint {
 468         if (n < 0) { Zero::zero() } else { BigUint::from_uint(n as uint) }
 469     }
 470 }
 471
 472 impl ToStrRadix for BigUint {
 473     #[inline(always)]
 474     fn to_str_radix(&self, radix: uint) -> ~str {
 475         assert!(1 < radix && radix <= 16);
 476         let (base, max_len) = get_radix_base(radix);
 477         if base == BigDigit::base {
 478             return fill_concat(self.data, radix, max_len)
 479         }
 480         return fill_concat(convert_base(copy *self, base), radix, max_len);
 481
 482         #[inline(always)]
 483         fn convert_base(n: BigUint, base: uint) -> ~[BigDigit] {
 484             let divider    = BigUint::from_uint(base);
 485             let mut result = ~[];
 486             let mut m      = n;
 487             while m > divider {
 488                 let (d, m0) = m.div_mod(&divider);
 489                 result += [m0.to_uint() as BigDigit];
 490                 m = d;
 491             }
 492             if !m.is_zero() {
 493                 result += [m.to_uint() as BigDigit];
 494             }
 495             return result;
 496         }
 497
 498         #[inline(always)]
 499         fn fill_concat(v: &[BigDigit], radix: uint, l: uint) -> ~str {
 500             if v.is_empty() { return ~"0" }
 501             let s = str::concat(vec::reversed(v).map(|n| {
 502                 let s = uint::to_str_radix(*n as uint, radix);
 503                 str::from_chars(vec::from_elem(l - s.len(), '0')) + s
 504             }));
 505             str::trim_left_chars(s, ['0']).to_owned()
 506         }
 507     }
 508 }
 509
 510 impl FromStrRadix for BigUint {
 511     /// Creates and initializes an BigUint.
 512     #[inline(always)]
 513     pub fn from_str_radix(s: &str, radix: uint)
 514         -> Option<BigUint> {
 515         BigUint::parse_bytes(str::to_bytes(s), radix)
 516     }
 517 }
 518
 519 impl BigUint {
 520     /// Creates and initializes an BigUint.
 521     #[inline(always)]
 522     pub fn new(v: ~[BigDigit]) -> BigUint {
 523         // omit trailing zeros
 524         let new_len = v.rposition(|n| *n != 0).map_default(0, |p| *p + 1);
 525
 526         if new_len == v.len() { return BigUint { data: v }; }
 527         let mut v = v;
 528         v.truncate(new_len);
 529         return BigUint { data: v };
 530     }
 531
 532     /// Creates and initializes an BigUint.
 533     #[inline(always)]
 534     pub fn from_uint(n: uint) -> BigUint {
 535         match BigDigit::from_uint(n) {
 536             (0,  0)  => Zero::zero(),
 537             (0,  n0) => BigUint::new(~[n0]),
 538             (n1, n0) => BigUint::new(~[n0, n1])
 539         }
 540     }
 541
 542     /// Creates and initializes an BigUint.
 543     #[inline(always)]
 544     pub fn from_slice(slice: &[BigDigit]) -> BigUint {
 545         return BigUint::new(vec::from_slice(slice));
 546     }
 547
 548     /// Creates and initializes an BigUint.
 549     #[inline(always)]
 550     pub fn parse_bytes(buf: &[u8], radix: uint)
 551         -> Option<BigUint> {
 552         let (base, unit_len) = get_radix_base(radix);
 553         let base_num: BigUint = BigUint::from_uint(base);
 554
 555         let mut end             = buf.len();
 556         let mut n: BigUint      = Zero::zero();
 557         let mut power: BigUint  = One::one();
 558         loop {
 559             let start = uint::max(end, unit_len) - unit_len;
 560             match uint::parse_bytes(vec::slice(buf, start, end), radix) {
 561                 // FIXME(#6102): Assignment operator for BigInt causes ICE
 562                 // Some(d) => n += BigUint::from_uint(d) * power,
 563                 Some(d) => n = n + BigUint::from_uint(d) * power,
 564                 None    => return None
 565             }
 566             if end <= unit_len {
 567                 return Some(n);
 568             }
 569             end -= unit_len;
 570             // FIXME(#6050): overloaded operators force moves with generic types
 571             // power *= base_num;
 572             power = power * base_num;
 573         }
 574     }
 575
 576     #[inline(always)]
 577     pub fn to_uint(&self) -> uint {
 578         match self.data.len() {
 579             0 => 0,
 580             1 => self.data[0] as uint,
 581             2 => BigDigit::to_uint(self.data[1], self.data[0]),
 582             _ => uint::max_value
 583         }
 584     }
 585
 586     #[inline(always)]
 587     priv fn shl_unit(&self, n_unit: uint) -> BigUint {
 588         if n_unit == 0 || self.is_zero() { return copy *self; }
 589
 590         return BigUint::new(vec::from_elem(n_unit, 0) + self.data);
 591     }
 592
 593     #[inline(always)]
 594     priv fn shl_bits(&self, n_bits: uint) -> BigUint {
 595         if n_bits == 0 || self.is_zero() { return copy *self; }
 596
 597         let mut carry = 0;
 598         let shifted = do vec::map(self.data) |elem| {
 599             let (hi, lo) = BigDigit::from_uint(
 600                 (*elem as uint) << n_bits | (carry as uint)
 601             );
 602             carry = hi;
 603             lo
 604         };
 605         if carry == 0 { return BigUint::new(shifted); }
 606         return BigUint::new(shifted + [carry]);
 607     }
 608
 609     #[inline(always)]
 610     priv fn shr_unit(&self, n_unit: uint) -> BigUint {
 611         if n_unit == 0 { return copy *self; }
 612         if self.data.len() < n_unit { return Zero::zero(); }
 613         return BigUint::from_slice(
 614             vec::slice(self.data, n_unit, self.data.len())
 615         );
 616     }
 617
 618     #[inline(always)]
 619     priv fn shr_bits(&self, n_bits: uint) -> BigUint {
 620         if n_bits == 0 || self.data.is_empty() { return copy *self; }
 621
 622         let mut borrow = 0;
 623         let mut shifted = ~[];
 624         for self.data.each_reverse |elem| {
 625             shifted = ~[(*elem >> n_bits) | borrow] + shifted;
 626             borrow = *elem << (BigDigit::bits - n_bits);
 627         }
 628         return BigUint::new(shifted);
 629     }
 630 }
 631
 632 #[cfg(target_arch = "x86_64")]
 633 #[inline(always)]
 634 priv fn get_radix_base(radix: uint) -> (uint, uint) {
 635     assert!(1 < radix && radix <= 16);
 636     match radix {
 637         2  => (4294967296, 32),
 638         3  => (3486784401, 20),
 639         4  => (4294967296, 16),
 640         5  => (1220703125, 13),
 641         6  => (2176782336, 12),
 642         7  => (1977326743, 11),
 643         8  => (1073741824, 10),
 644         9  => (3486784401, 10),
 645         10 => (1000000000, 9),
 646         11 => (2357947691, 9),
 647         12 => (429981696,  8),
 648         13 => (815730721,  8),
 649         14 => (1475789056, 8),
 650         15 => (2562890625, 8),
 651         16 => (4294967296, 8),
 652         _  => fail!()
 653     }
 654 }
 655
 656 #[cfg(target_arch = "arm")]
 657 #[cfg(target_arch = "x86")]
 658 #[cfg(target_arch = "mips")]
 659 #[inline(always)]
 660 priv fn get_radix_base(radix: uint) -> (uint, uint) {
 661     assert!(1 < radix && radix <= 16);
 662     match radix {
 663         2  => (65536, 16),
 664         3  => (59049, 10),
 665         4  => (65536, 8),
 666         5  => (15625, 6),
 667         6  => (46656, 6),
 668         7  => (16807, 5),
 669         8  => (32768, 5),
 670         9  => (59049, 5),
 671         10 => (10000, 4),
 672         11 => (14641, 4),
 673         12 => (20736, 4),
 674         13 => (28561, 4),
 675         14 => (38416, 4),
 676         15 => (50625, 4),
 677         16 => (65536, 4),
 678         _  => fail!()
 679     }
 680 }
 681
 682 /// A Sign is a BigInt's composing element.
 683 #[deriving(Eq)]
 684 pub enum Sign { Minus, Zero, Plus }
 685
 686 impl Ord for Sign {
 687     #[inline(always)]
 688     fn lt(&self, other: &Sign) -> bool {
 689         match self.cmp(other) { Less => true, _ => false}
 690     }
 691     #[inline(always)]
 692     fn le(&self, other: &Sign) -> bool {
 693         match self.cmp(other) { Less | Equal => true, _ => false }
 694     }
 695     #[inline(always)]
 696     fn ge(&self, other: &Sign) -> bool {
 697         match self.cmp(other) { Greater | Equal => true, _ => false }
 698     }
 699     #[inline(always)]
 700     fn gt(&self, other: &Sign) -> bool {
 701         match self.cmp(other) { Greater => true, _ => false }
 702     }
 703 }
 704
 705 impl TotalOrd for Sign {
 706     #[inline(always)]
 707     fn cmp(&self, other: &Sign) -> Ordering {
 708         match (*self, *other) {
 709           (Minus, Minus) | (Zero,  Zero) | (Plus, Plus) => Equal,
 710           (Minus, Zero)  | (Minus, Plus) | (Zero, Plus) => Less,
 711           _                                             => Greater
 712         }
 713     }
 714 }
 715
 716 impl Neg<Sign> for Sign {
 717     /// Negate Sign value.
 718     #[inline(always)]
 719     fn neg(&self) -> Sign {
 720         match *self {
 721           Minus => Plus,
 722           Zero  => Zero,
 723           Plus  => Minus
 724         }
 725     }
 726 }
 727
 728 /// A big signed integer type.
 729 pub struct BigInt {
 730     priv sign: Sign,
 731     priv data: BigUint
 732 }
 733
 734 impl Eq for BigInt {
 735     #[inline(always)]
 736     fn eq(&self, other: &BigInt) -> bool { self.equals(other) }
 737     #[inline(always)]
 738     fn ne(&self, other: &BigInt) -> bool { !self.equals(other) }
 739 }
 740
 741 impl TotalEq for BigInt {
 742     #[inline(always)]
 743     fn equals(&self, other: &BigInt) -> bool {
 744         match self.cmp(other) { Equal => true, _ => false }
 745     }
 746 }
 747
 748 impl Ord for BigInt {
 749     #[inline(always)]
 750     fn lt(&self, other: &BigInt) -> bool {
 751         match self.cmp(other) { Less => true, _ => false}
 752     }
 753     #[inline(always)]
 754     fn le(&self, other: &BigInt) -> bool {
 755         match self.cmp(other) { Less | Equal => true, _ => false }
 756     }
 757     #[inline(always)]
 758     fn ge(&self, other: &BigInt) -> bool {
 759         match self.cmp(other) { Greater | Equal => true, _ => false }
 760     }
 761     #[inline(always)]
 762     fn gt(&self, other: &BigInt) -> bool {
 763         match self.cmp(other) { Greater => true, _ => false }
 764     }
 765 }
 766
 767 impl TotalOrd for BigInt {
 768     #[inline(always)]
 769     fn cmp(&self, other: &BigInt) -> Ordering {
 770         let scmp = self.sign.cmp(&other.sign);
 771         if scmp != Equal { return scmp; }
 772
 773         match self.sign {
 774             Zero  => Equal,
 775             Plus  => self.data.cmp(&other.data),
 776             Minus => other.data.cmp(&self.data),
 777         }
 778     }
 779 }
 780
 781 impl ToStr for BigInt {
 782     #[inline(always)]
 783     fn to_str(&self) -> ~str { self.to_str_radix(10) }
 784 }
 785
 786 impl from_str::FromStr for BigInt {
 787     #[inline(always)]
 788     fn from_str(s: &str) -> Option<BigInt> {
 789         FromStrRadix::from_str_radix(s, 10)
 790     }
 791 }
 792
 793 impl Shl<uint, BigInt> for BigInt {
 794     #[inline(always)]
 795     fn shl(&self, rhs: &uint) -> BigInt {
 796         BigInt::from_biguint(self.sign, self.data << *rhs)
 797     }
 798 }
 799
 800 impl Shr<uint, BigInt> for BigInt {
 801     #[inline(always)]
 802     fn shr(&self, rhs: &uint) -> BigInt {
 803         BigInt::from_biguint(self.sign, self.data >> *rhs)
 804     }
 805 }
 806
 807 impl Zero for BigInt {
 808     #[inline(always)]
 809     fn zero() -> BigInt {
 810         BigInt::from_biguint(Zero, Zero::zero())
 811     }
 812
 813     #[inline(always)]
 814     fn is_zero(&self) -> bool { self.sign == Zero }
 815 }
 816
 817 impl One for BigInt {
 818     #[inline(always)]
 819     fn one() -> BigInt {
 820         BigInt::from_biguint(Plus, One::one())
 821     }
 822 }
 823
 824 impl Signed for BigInt {
 825     #[inline(always)]
 826     fn abs(&self) -> BigInt {
 827         match self.sign {
 828             Plus | Zero => copy *self,
 829             Minus => BigInt::from_biguint(Plus, copy self.data)
 830         }
 831     }
 832
 833     #[inline(always)]
 834     fn signum(&self) -> BigInt {
 835         match self.sign {
 836             Plus  => BigInt::from_biguint(Plus, One::one()),
 837             Minus => BigInt::from_biguint(Minus, One::one()),
 838             Zero  => Zero::zero(),
 839         }
 840     }
 841
 842     #[inline(always)]
 843     fn is_positive(&self) -> bool { self.sign == Plus }
 844
 845     #[inline(always)]
 846     fn is_negative(&self) -> bool { self.sign == Minus }
 847 }
 848
 849 impl Add<BigInt, BigInt> for BigInt {
 850     #[inline(always)]
 851     fn add(&self, other: &BigInt) -> BigInt {
 852         match (self.sign, other.sign) {
 853             (Zero, _)      => copy *other,
 854             (_,    Zero)   => copy *self,
 855             (Plus, Plus)   => BigInt::from_biguint(Plus,
 856                                                    self.data + other.data),
 857             (Plus, Minus)  => self - (-*other),
 858             (Minus, Plus)  => other - (-*self),
 859             (Minus, Minus) => -((-self) + (-*other))
 860         }
 861     }
 862 }
 863
 864 impl Sub<BigInt, BigInt> for BigInt {
 865     #[inline(always)]
 866     fn sub(&self, other: &BigInt) -> BigInt {
 867         match (self.sign, other.sign) {
 868             (Zero, _)    => -other,
 869             (_,    Zero) => copy *self,
 870             (Plus, Plus) => match self.data.cmp(&other.data) {
 871                 Less    => BigInt::from_biguint(Minus, other.data - self.data),
 872                 Greater => BigInt::from_biguint(Plus, self.data - other.data),
 873                 Equal   => Zero::zero()
 874             },
 875             (Plus, Minus) => self + (-*other),
 876             (Minus, Plus) => -((-self) + *other),
 877             (Minus, Minus) => (-other) - (-*self)
 878         }
 879     }
 880 }
 881
 882 impl Mul<BigInt, BigInt> for BigInt {
 883     #[inline(always)]
 884     fn mul(&self, other: &BigInt) -> BigInt {
 885         match (self.sign, other.sign) {
 886             (Zero, _)     | (_,     Zero)  => Zero::zero(),
 887             (Plus, Plus)  | (Minus, Minus) => {
 888                 BigInt::from_biguint(Plus, self.data * other.data)
 889             },
 890             (Plus, Minus) | (Minus, Plus) => {
 891                 BigInt::from_biguint(Minus, self.data * other.data)
 892             }
 893         }
 894     }
 895 }
 896
 897 impl Quot<BigInt, BigInt> for BigInt {
 898     #[inline(always)]
 899     fn quot(&self, other: &BigInt) -> BigInt {
 900         let (q, _) = self.quot_rem(other);
 901         return q;
 902     }
 903 }
 904
 905 impl Rem<BigInt, BigInt> for BigInt {
 906     #[inline(always)]
 907     fn rem(&self, other: &BigInt) -> BigInt {
 908         let (_, r) = self.quot_rem(other);
 909         return r;
 910     }
 911 }
 912
 913 impl Neg<BigInt> for BigInt {
 914     #[inline(always)]
 915     fn neg(&self) -> BigInt {
 916         BigInt::from_biguint(self.sign.neg(), copy self.data)
 917     }
 918 }
 919
 920 impl Integer for BigInt {
 921     #[inline(always)]
 922     fn div(&self, other: &BigInt) -> BigInt {
 923         let (d, _) = self.div_mod(other);
 924         return d;
 925     }
 926
 927     #[inline(always)]
 928     fn modulo(&self, other: &BigInt) -> BigInt {
 929         let (_, m) = self.div_mod(other);
 930         return m;
 931     }
 932
 933     #[inline(always)]
 934     fn div_mod(&self, other: &BigInt) -> (BigInt, BigInt) {
 935         // m.sign == other.sign
 936         let (d_ui, m_ui) = self.data.quot_rem(&other.data);
 937         let d = BigInt::from_biguint(Plus, d_ui),
 938             m = BigInt::from_biguint(Plus, m_ui);
 939         match (self.sign, other.sign) {
 940             (_,    Zero)   => fail!(),
 941             (Plus, Plus)  | (Zero, Plus)  => (d, m),
 942             (Plus, Minus) | (Zero, Minus) => if m.is_zero() {
 943                 (-d, Zero::zero())
 944             } else {
 945                 (-d - One::one(), m + *other)
 946             },
 947             (Minus, Plus) => if m.is_zero() {
 948                 (-d, Zero::zero())
 949             } else {
 950                 (-d - One::one(), other - m)
 951             },
 952             (Minus, Minus) => (d, -m)
 953         }
 954     }
 955
 956     #[inline(always)]
 957     fn quot_rem(&self, other: &BigInt) -> (BigInt, BigInt) {
 958         // r.sign == self.sign
 959         let (q_ui, r_ui) = self.data.div_mod(&other.data);
 960         let q = BigInt::from_biguint(Plus, q_ui);
 961         let r = BigInt::from_biguint(Plus, r_ui);
 962         match (self.sign, other.sign) {
 963             (_,    Zero)   => fail!(),
 964             (Plus, Plus)  | (Zero, Plus)  => ( q,  r),
 965             (Plus, Minus) | (Zero, Minus) => (-q,  r),
 966             (Minus, Plus)                 => (-q, -r),
 967             (Minus, Minus)                => ( q, -r)
 968         }
 969     }
 970
 971     /**
 972      * Calculates the Greatest Common Divisor (GCD) of the number and `other`
 973      *
 974      * The result is always positive
 975      */
 976     #[inline(always)]
 977     fn gcd(&self, other: &BigInt) -> BigInt {
 978         BigInt::from_biguint(Plus, self.data.gcd(&other.data))
 979     }
 980
 981     /**
 982      * Calculates the Lowest Common Multiple (LCM) of the number and `other`
 983      */
 984     #[inline(always)]
 985     fn lcm(&self, other: &BigInt) -> BigInt {
 986         BigInt::from_biguint(Plus, self.data.lcm(&other.data))
 987     }
 988
 989     /// Returns `true` if the number can be divided by `other` without leaving a remainder
 990     #[inline(always)]
 991     fn is_multiple_of(&self, other: &BigInt) -> bool { self.data.is_multiple_of(&other.data) }
 992
 993     /// Returns `true` if the number is divisible by `2`
 994     #[inline(always)]
 995     fn is_even(&self) -> bool { self.data.is_even() }
 996
 997     /// Returns `true` if the number is not divisible by `2`
 998     #[inline(always)]
 999     fn is_odd(&self) -> bool { self.data.is_odd() }
1000 }
1001
1002 impl IntConvertible for BigInt {
1003     #[inline(always)]
1004     fn to_int(&self) -> int {
1005         match self.sign {
1006             Plus  => uint::min(self.to_uint(), int::max_value as uint) as int,
1007             Zero  => 0,
1008             Minus => uint::min((-self).to_uint(),
1009                                (int::max_value as uint) + 1) as int
1010         }
1011     }
1012
1013     #[inline(always)]
1014     fn from_int(n: int) -> BigInt {
1015         if n > 0 {
1016            return BigInt::from_biguint(Plus,  BigUint::from_uint(n as uint));
1017         }
1018         if n < 0 {
1019             return BigInt::from_biguint(
1020                 Minus, BigUint::from_uint(uint::max_value - (n as uint) + 1)
1021             );
1022         }
1023         return Zero::zero();
1024     }
1025 }
1026
1027 impl ToStrRadix for BigInt {
1028     #[inline(always)]
1029     fn to_str_radix(&self, radix: uint) -> ~str {
1030         match self.sign {
1031             Plus  => self.data.to_str_radix(radix),
1032             Zero  => ~"0",
1033             Minus => ~"-" + self.data.to_str_radix(radix)
1034         }
1035     }
1036 }
1037
1038 impl FromStrRadix for BigInt {
1039     /// Creates and initializes an BigInt.
1040     #[inline(always)]
1041     fn from_str_radix(s: &str, radix: uint)
1042         -> Option<BigInt> {
1043         BigInt::parse_bytes(str::to_bytes(s), radix)
1044     }
1045 }
1046
1047 pub impl BigInt {
1048     /// Creates and initializes an BigInt.
1049     #[inline(always)]
1050     pub fn new(sign: Sign, v: ~[BigDigit]) -> BigInt {
1051         BigInt::from_biguint(sign, BigUint::new(v))
1052     }
1053
1054     /// Creates and initializes an BigInt.
1055     #[inline(always)]
1056     pub fn from_biguint(sign: Sign, data: BigUint) -> BigInt {
1057         if sign == Zero || data.is_zero() {
1058             return BigInt { sign: Zero, data: Zero::zero() };
1059         }
1060         return BigInt { sign: sign, data: data };
1061     }
1062
1063     /// Creates and initializes an BigInt.
1064     #[inline(always)]
1065     pub fn from_uint(n: uint) -> BigInt {
1066         if n == 0 { return Zero::zero(); }
1067         return BigInt::from_biguint(Plus, BigUint::from_uint(n));
1068     }
1069
1070     /// Creates and initializes an BigInt.
1071     #[inline(always)]
1072     pub fn from_slice(sign: Sign, slice: &[BigDigit]) -> BigInt {
1073         BigInt::from_biguint(sign, BigUint::from_slice(slice))
1074     }
1075
1076     /// Creates and initializes an BigInt.
1077     #[inline(always)]
1078     pub fn parse_bytes(buf: &[u8], radix: uint)
1079         -> Option<BigInt> {
1080         if buf.is_empty() { return None; }
1081         let mut sign  = Plus;
1082         let mut start = 0;
1083         if buf[0] == ('-' as u8) {
1084             sign  = Minus;
1085             start = 1;
1086         }
1087         return BigUint::parse_bytes(vec::slice(buf, start, buf.len()), radix)
1088             .map_consume(|bu| BigInt::from_biguint(sign, bu));
1089     }
1090
1091     #[inline(always)]
1092     fn to_uint(&self) -> uint {
1093         match self.sign {
1094             Plus  => self.data.to_uint(),
1095             Zero  => 0,
1096             Minus => 0
1097         }
1098     }
1099 }
1100
1101 #[cfg(test)]
1102 mod biguint_tests {
1103
1104     use core::*;
1105     use core::num::{IntConvertible, Zero, One, FromStrRadix};
1106     use core::cmp::{Less, Equal, Greater};
1107     use super::{BigUint, BigDigit};
1108
1109     #[test]
1110     fn test_from_slice() {
1111         fn check(slice: &[BigDigit], data: &[BigDigit]) {
1112             assert!(data == BigUint::from_slice(slice).data);
1113         }
1114         check(~[1], ~[1]);
1115         check(~[0, 0, 0], ~[]);
1116         check(~[1, 2, 0, 0], ~[1, 2]);
1117         check(~[0, 0, 1, 2], ~[0, 0, 1, 2]);
1118         check(~[0, 0, 1, 2, 0, 0], ~[0, 0, 1, 2]);
1119         check(~[-1], ~[-1]);
1120     }
1121
1122     #[test]
1123     fn test_cmp() {
1124         let data = [ &[], &[1], &[2], &[-1], &[0, 1], &[2, 1], &[1, 1, 1]  ]
1125             .map(|v| BigUint::from_slice(*v));
1126         for data.eachi |i, ni| {
1127             for vec::slice(data, i, data.len()).eachi |j0, nj| {
1128                 let j = j0 + i;
1129                 if i == j {
1130                     assert_eq!(ni.cmp(nj), Equal);
1131                     assert_eq!(nj.cmp(ni), Equal);
1132                     assert!(ni == nj);
1133                     assert!(!(ni != nj));
1134                     assert!(ni <= nj);
1135                     assert!(ni >= nj);
1136                     assert!(!(ni < nj));
1137                     assert!(!(ni > nj));
1138                 } else {
1139                     assert_eq!(ni.cmp(nj), Less);
1140                     assert_eq!(nj.cmp(ni), Greater);
1141
1142                     assert!(!(ni == nj));
1143                     assert!(ni != nj);
1144
1145                     assert!(ni <= nj);
1146                     assert!(!(ni >= nj));
1147                     assert!(ni < nj);
1148                     assert!(!(ni > nj));
1149
1150                     assert!(!(nj <= ni));
1151                     assert!(nj >= ni);
1152                     assert!(!(nj < ni));
1153                     assert!(nj > ni);
1154                 }
1155             }
1156         }
1157     }
1158
1159     #[test]
1160     fn test_shl() {
1161         fn check(v: ~[BigDigit], shift: uint, ans: ~[BigDigit]) {
1162             assert!(BigUint::new(v) << shift == BigUint::new(ans));
1163         }
1164
1165         check(~[], 3, ~[]);
1166         check(~[1, 1, 1], 3, ~[1 << 3, 1 << 3, 1 << 3]);
1167         check(~[1 << (BigDigit::bits - 2)], 2, ~[0, 1]);
1168         check(~[1 << (BigDigit::bits - 2)], 3, ~[0, 2]);
1169         check(~[1 << (BigDigit::bits - 2)], 3 + BigDigit::bits, ~[0, 0, 2]);
1170
1171         test_shl_bits();
1172
1173         #[cfg(target_arch = "x86_64")]
1174         fn test_shl_bits() {
1175             check(~[0x7654_3210, 0xfedc_ba98,
1176                     0x7654_3210, 0xfedc_ba98], 4,
1177                   ~[0x6543_2100, 0xedcb_a987,
1178                     0x6543_210f, 0xedcb_a987, 0xf]);
1179             check(~[0x2222_1111, 0x4444_3333,
1180                     0x6666_5555, 0x8888_7777], 16,
1181                   ~[0x1111_0000, 0x3333_2222,
1182                     0x5555_4444, 0x7777_6666, 0x8888]);
1183         }
1184
1185         #[cfg(target_arch = "arm")]
1186         #[cfg(target_arch = "x86")]
1187         #[cfg(target_arch = "mips")]
1188         fn test_shl_bits() {
1189             check(~[0x3210, 0x7654, 0xba98, 0xfedc,
1190                     0x3210, 0x7654, 0xba98, 0xfedc], 4,
1191                   ~[0x2100, 0x6543, 0xa987, 0xedcb,
1192                     0x210f, 0x6543, 0xa987, 0xedcb, 0xf]);
1193             check(~[0x1111, 0x2222, 0x3333, 0x4444,
1194                     0x5555, 0x6666, 0x7777, 0x8888], 16,
1195                   ~[0x0000, 0x1111, 0x2222, 0x3333,
1196                     0x4444, 0x5555, 0x6666, 0x7777, 0x8888]);
1197         }
1198
1199     }
1200
1201     #[test]
1202     #[ignore(cfg(target_arch = "x86"))]
1203     #[ignore(cfg(target_arch = "arm"))]
1204     #[ignore(cfg(target_arch = "mips"))]
1205     fn test_shr() {
1206         fn check(v: ~[BigDigit], shift: uint, ans: ~[BigDigit]) {
1207             assert!(BigUint::new(v) >> shift == BigUint::new(ans));
1208         }
1209
1210         check(~[], 3, ~[]);
1211         check(~[1, 1, 1], 3,
1212               ~[1 << (BigDigit::bits - 3), 1 << (BigDigit::bits - 3)]);
1213         check(~[1 << 2], 2, ~[1]);
1214         check(~[1, 2], 3, ~[1 << (BigDigit::bits - 2)]);
1215         check(~[1, 1, 2], 3 + BigDigit::bits, ~[1 << (BigDigit::bits - 2)]);
1216         check(~[0, 1], 1, ~[0x80000000]);
1217         test_shr_bits();
1218
1219         #[cfg(target_arch = "x86_64")]
1220         fn test_shr_bits() {
1221             check(~[0x6543_2100, 0xedcb_a987,
1222                     0x6543_210f, 0xedcb_a987, 0xf], 4,
1223                   ~[0x7654_3210, 0xfedc_ba98,
1224                     0x7654_3210, 0xfedc_ba98]);
1225             check(~[0x1111_0000, 0x3333_2222,
1226                     0x5555_4444, 0x7777_6666, 0x8888], 16,
1227                   ~[0x2222_1111, 0x4444_3333,
1228                     0x6666_5555, 0x8888_7777]);
1229         }
1230
1231         #[cfg(target_arch = "arm")]
1232         #[cfg(target_arch = "x86")]
1233         #[cfg(target_arch = "mips")]
1234         fn test_shr_bits() {
1235             check(~[0x2100, 0x6543, 0xa987, 0xedcb,
1236                     0x210f, 0x6543, 0xa987, 0xedcb, 0xf], 4,
1237                   ~[0x3210, 0x7654, 0xba98, 0xfedc,
1238                     0x3210, 0x7654, 0xba98, 0xfedc]);
1239             check(~[0x0000, 0x1111, 0x2222, 0x3333,
1240                     0x4444, 0x5555, 0x6666, 0x7777, 0x8888], 16,
1241                   ~[0x1111, 0x2222, 0x3333, 0x4444,
1242                     0x5555, 0x6666, 0x7777, 0x8888]);
1243         }
1244     }
1245
1246     #[test]
1247     fn test_convert_int() {
1248         fn check(v: ~[BigDigit], i: int) {
1249             let b = BigUint::new(v);
1250             assert!(b == IntConvertible::from_int(i));
1251             assert!(b.to_int() == i);
1252         }
1253
1254         check(~[], 0);
1255         check(~[1], 1);
1256         check(~[-1], (uint::max_value >> BigDigit::bits) as int);
1257         check(~[ 0,  1], ((uint::max_value >> BigDigit::bits) + 1) as int);
1258         check(~[-1, -1 >> 1], int::max_value);
1259
1260         assert!(BigUint::new(~[0, -1]).to_int() == int::max_value);
1261         assert!(BigUint::new(~[0, 0, 1]).to_int() == int::max_value);
1262         assert!(BigUint::new(~[0, 0, -1]).to_int() == int::max_value);
1263     }
1264
1265     #[test]
1266     fn test_convert_uint() {
1267         fn check(v: ~[BigDigit], u: uint) {
1268             let b = BigUint::new(v);
1269             assert!(b == BigUint::from_uint(u));
1270             assert!(b.to_uint() == u);
1271         }
1272
1273         check(~[], 0);
1274         check(~[ 1], 1);
1275         check(~[-1], uint::max_value >> BigDigit::bits);
1276         check(~[ 0,  1], (uint::max_value >> BigDigit::bits) + 1);
1277         check(~[ 0, -1], uint::max_value << BigDigit::bits);
1278         check(~[-1, -1], uint::max_value);
1279
1280         assert!(BigUint::new(~[0, 0, 1]).to_uint()  == uint::max_value);
1281         assert!(BigUint::new(~[0, 0, -1]).to_uint() == uint::max_value);
1282     }
1283
1284     static sum_triples: &'static [(&'static [BigDigit],
1285                                    &'static [BigDigit],
1286                                    &'static [BigDigit])] = &[
1287         (&[],          &[],       &[]),
1288         (&[],          &[ 1],     &[ 1]),
1289         (&[ 1],        &[ 1],     &[ 2]),
1290         (&[ 1],        &[ 1,  1], &[ 2,  1]),
1291         (&[ 1],        &[-1],     &[ 0,  1]),
1292         (&[ 1],        &[-1, -1], &[ 0,  0, 1]),
1293         (&[-1, -1],    &[-1, -1], &[-2, -1, 1]),
1294         (&[ 1,  1, 1], &[-1, -1], &[ 0,  1, 2]),
1295         (&[ 2,  2, 1], &[-1, -2], &[ 1,  1, 2])
1296     ];
1297
1298     #[test]
1299     fn test_add() {
1300         for sum_triples.each |elm| {
1301             let (aVec, bVec, cVec) = *elm;
1302             let a = BigUint::from_slice(aVec);
1303             let b = BigUint::from_slice(bVec);
1304             let c = BigUint::from_slice(cVec);
1305
1306             assert!(a + b == c);
1307             assert!(b + a == c);
1308         }
1309     }
1310
1311     #[test]
1312     fn test_sub() {
1313         for sum_triples.each |elm| {
1314             let (aVec, bVec, cVec) = *elm;
1315             let a = BigUint::from_slice(aVec);
1316             let b = BigUint::from_slice(bVec);
1317             let c = BigUint::from_slice(cVec);
1318
1319             assert!(c - a == b);
1320             assert!(c - b == a);
1321         }
1322     }
1323
1324     static mul_triples: &'static [(&'static [BigDigit],
1325                                    &'static [BigDigit],
1326                                    &'static [BigDigit])] = &[
1327         (&[],               &[],               &[]),
1328         (&[],               &[ 1],             &[]),
1329         (&[ 2],             &[],               &[]),
1330         (&[ 1],             &[ 1],             &[1]),
1331         (&[ 2],             &[ 3],             &[ 6]),
1332         (&[ 1],             &[ 1,  1,  1],     &[1, 1,  1]),
1333         (&[ 1,  2,  3],     &[ 3],             &[ 3,  6,  9]),
1334         (&[ 1,  1,  1],     &[-1],             &[-1, -1, -1]),
1335         (&[ 1,  2,  3],     &[-1],             &[-1, -2, -2, 2]),
1336         (&[ 1,  2,  3,  4], &[-1],             &[-1, -2, -2, -2, 3]),
1337         (&[-1],             &[-1],             &[ 1, -2]),
1338         (&[-1, -1],         &[-1],             &[ 1, -1, -2]),
1339         (&[-1, -1, -1],     &[-1],             &[ 1, -1, -1, -2]),
1340         (&[-1, -1, -1, -1], &[-1],             &[ 1, -1, -1, -1, -2]),
1341         (&[-1/2 + 1],       &[ 2],             &[ 0,  1]),
1342         (&[0, -1/2 + 1],    &[ 2],             &[ 0,  0,  1]),
1343         (&[ 1,  2],         &[ 1,  2,  3],     &[1, 4,  7,  6]),
1344         (&[-1, -1],         &[-1, -1, -1],     &[1, 0, -1, -2, -1]),
1345         (&[-1, -1, -1],     &[-1, -1, -1, -1], &[1, 0,  0, -1, -2, -1, -1]),
1346         (&[ 0,  0,  1],     &[ 1,  2,  3],     &[0, 0,  1,  2,  3]),
1347         (&[ 0,  0,  1],     &[ 0,  0,  0,  1], &[0, 0,  0,  0,  0,  1])
1348     ];
1349
1350     static quot_rem_quadruples: &'static [(&'static [BigDigit],
1351                                            &'static [BigDigit],
1352                                            &'static [BigDigit],
1353                                            &'static [BigDigit])]
1354         = &[
1355             (&[ 1],        &[ 2], &[],               &[1]),
1356             (&[ 1,  1],    &[ 2], &[-1/2+1],         &[1]),
1357             (&[ 1,  1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
1358             (&[ 0,  1],    &[-1], &[1],              &[1]),
1359             (&[-1, -1],    &[-2], &[2, 1],           &[3])
1360         ];
1361
1362     #[test]
1363     fn test_mul() {
1364         for mul_triples.each |elm| {
1365             let (aVec, bVec, cVec) = *elm;
1366             let a = BigUint::from_slice(aVec);
1367             let b = BigUint::from_slice(bVec);
1368             let c = BigUint::from_slice(cVec);
1369
1370             assert!(a * b == c);
1371             assert!(b * a == c);
1372         }
1373
1374         for quot_rem_quadruples.each |elm| {
1375             let (aVec, bVec, cVec, dVec) = *elm;
1376             let a = BigUint::from_slice(aVec);
1377             let b = BigUint::from_slice(bVec);
1378             let c = BigUint::from_slice(cVec);
1379             let d = BigUint::from_slice(dVec);
1380
1381             assert!(a == b * c + d);
1382             assert!(a == c * b + d);
1383         }
1384     }
1385
1386     #[test]
1387     fn test_quot_rem() {
1388         for mul_triples.each |elm| {
1389             let (aVec, bVec, cVec) = *elm;
1390             let a = BigUint::from_slice(aVec);
1391             let b = BigUint::from_slice(bVec);
1392             let c = BigUint::from_slice(cVec);
1393
1394             if !a.is_zero() {
1395                 assert!(c.quot_rem(&a) == (copy b, Zero::zero()));
1396             }
1397             if !b.is_zero() {
1398                 assert!(c.quot_rem(&b) == (copy a, Zero::zero()));
1399             }
1400         }
1401
1402         for quot_rem_quadruples.each |elm| {
1403             let (aVec, bVec, cVec, dVec) = *elm;
1404             let a = BigUint::from_slice(aVec);
1405             let b = BigUint::from_slice(bVec);
1406             let c = BigUint::from_slice(cVec);
1407             let d = BigUint::from_slice(dVec);
1408
1409             if !b.is_zero() { assert!(a.quot_rem(&b) == (c, d)); }
1410         }
1411     }
1412
1413     #[test]
1414     fn test_gcd() {
1415         fn check(a: uint, b: uint, c: uint) {
1416             let big_a = BigUint::from_uint(a);
1417             let big_b = BigUint::from_uint(b);
1418             let big_c = BigUint::from_uint(c);
1419
1420             assert_eq!(big_a.gcd(&big_b), big_c);
1421         }
1422
1423         check(10, 2, 2);
1424         check(10, 3, 1);
1425         check(0, 3, 3);
1426         check(3, 3, 3);
1427         check(56, 42, 14);
1428     }
1429
1430     #[test]
1431     fn test_lcm() {
1432         fn check(a: uint, b: uint, c: uint) {
1433             let big_a = BigUint::from_uint(a);
1434             let big_b = BigUint::from_uint(b);
1435             let big_c = BigUint::from_uint(c);
1436
1437             assert_eq!(big_a.lcm(&big_b), big_c);
1438         }
1439
1440         check(1, 0, 0);
1441         check(0, 1, 0);
1442         check(1, 1, 1);
1443         check(8, 9, 72);
1444         check(11, 5, 55);
1445         check(99, 17, 1683);
1446     }
1447
1448     fn to_str_pairs() -> ~[ (BigUint, ~[(uint, ~str)]) ] {
1449         let bits = BigDigit::bits;
1450         ~[( Zero::zero(), ~[
1451             (2, ~"0"), (3, ~"0")
1452         ]), ( BigUint::from_slice([ 0xff ]), ~[
1453             (2,  ~"11111111"),
1454             (3,  ~"100110"),
1455             (4,  ~"3333"),
1456             (5,  ~"2010"),
1457             (6,  ~"1103"),
1458             (7,  ~"513"),
1459             (8,  ~"377"),
1460             (9,  ~"313"),
1461             (10, ~"255"),
1462             (11, ~"212"),
1463             (12, ~"193"),
1464             (13, ~"168"),
1465             (14, ~"143"),
1466             (15, ~"120"),
1467             (16, ~"ff")
1468         ]), ( BigUint::from_slice([ 0xfff ]), ~[
1469             (2,  ~"111111111111"),
1470             (4,  ~"333333"),
1471             (16, ~"fff")
1472         ]), ( BigUint::from_slice([ 1, 2 ]), ~[
1473             (2,
1474              ~"10" +
1475              str::from_chars(vec::from_elem(bits - 1, '0')) + "1"),
1476             (4,
1477              ~"2" +
1478              str::from_chars(vec::from_elem(bits / 2 - 1, '0')) + "1"),
1479             (10, match bits {
1480                 32 => ~"8589934593", 16 => ~"131073", _ => fail!()
1481             }),
1482             (16,
1483              ~"2" +
1484              str::from_chars(vec::from_elem(bits / 4 - 1, '0')) + "1")
1485         ]), ( BigUint::from_slice([ 1, 2, 3 ]), ~[
1486             (2,
1487              ~"11" +
1488              str::from_chars(vec::from_elem(bits - 2, '0')) + "10" +
1489              str::from_chars(vec::from_elem(bits - 1, '0')) + "1"),
1490             (4,
1491              ~"3" +
1492              str::from_chars(vec::from_elem(bits / 2 - 1, '0')) + "2" +
1493              str::from_chars(vec::from_elem(bits / 2 - 1, '0')) + "1"),
1494             (10, match bits {
1495                 32 => ~"55340232229718589441",
1496                 16 => ~"12885032961",
1497                 _ => fail!()
1498             }),
1499             (16, ~"3" +
1500              str::from_chars(vec::from_elem(bits / 4 - 1, '0')) + "2" +
1501              str::from_chars(vec::from_elem(bits / 4 - 1, '0')) + "1")
1502         ]) ]
1503     }
1504
1505     #[test]
1506     fn test_to_str_radix() {
1507         for to_str_pairs().each |num_pair| {
1508             let &(n, rs) = num_pair;
1509             for rs.each |str_pair| {
1510                 let &(radix, str) = str_pair;
1511                 assert!(n.to_str_radix(radix) == str);
1512             }
1513         }
1514     }
1515
1516     #[test]
1517     fn test_from_str_radix() {
1518         for to_str_pairs().each |num_pair| {
1519             let &(n, rs) = num_pair;
1520             for rs.each |str_pair| {
1521                 let &(radix, str) = str_pair;
1522                 assert_eq!(&n, &FromStrRadix::from_str_radix(str, radix).get());
1523             }
1524         }
1525
1526         assert_eq!(FromStrRadix::from_str_radix::<BigUint>(~"Z", 10), None);
1527         assert_eq!(FromStrRadix::from_str_radix::<BigUint>(~"_", 2), None);
1528         assert_eq!(FromStrRadix::from_str_radix::<BigUint>(~"-1", 10), None);
1529     }
1530
1531     #[test]
1532     fn test_factor() {
1533         fn factor(n: uint) -> BigUint {
1534             let mut f= One::one::<BigUint>();
1535             for uint::range(2, n + 1) |i| {
1536                 // FIXME(#6102): Assignment operator for BigInt causes ICE
1537                 // f *= BigUint::from_uint(i);
1538                 f = f * BigUint::from_uint(i);
1539             }
1540             return f;
1541         }
1542
1543         fn check(n: uint, s: &str) {
1544             let n = factor(n);
1545             let ans = match FromStrRadix::from_str_radix(s, 10) {
1546                 Some(x) => x, None => fail!()
1547             };
1548             assert!(n == ans);
1549         }
1550
1551         check(3, "6");
1552         check(10, "3628800");
1553         check(20, "2432902008176640000");
1554         check(30, "265252859812191058636308480000000");
1555     }
1556 }
1557
1558 #[cfg(test)]
1559 mod bigint_tests {
1560     use super::{BigInt, BigUint, BigDigit, Sign, Minus, Zero, Plus};
1561     use core::*;
1562     use core::cmp::{Less, Equal, Greater};
1563     use core::num::{IntConvertible, Zero, One, FromStrRadix};
1564
1565     #[test]
1566     fn test_from_biguint() {
1567         fn check(inp_s: Sign, inp_n: uint, ans_s: Sign, ans_n: uint) {
1568             let inp = BigInt::from_biguint(inp_s, BigUint::from_uint(inp_n));
1569             let ans = BigInt { sign: ans_s, data: BigUint::from_uint(ans_n)};
1570             assert!(inp == ans);
1571         }
1572         check(Plus, 1, Plus, 1);
1573         check(Plus, 0, Zero, 0);
1574         check(Minus, 1, Minus, 1);
1575         check(Zero, 1, Zero, 0);
1576     }
1577
1578     #[test]
1579     fn test_cmp() {
1580         let vs = [ &[2], &[1, 1], &[2, 1], &[1, 1, 1] ];
1581         let mut nums = vec::reversed(vs)
1582             .map(|s| BigInt::from_slice(Minus, *s));
1583         nums.push(Zero::zero());
1584         nums.push_all_move(vs.map(|s| BigInt::from_slice(Plus, *s)));
1585
1586         for nums.eachi |i, ni| {
1587             for vec::slice(nums, i, nums.len()).eachi |j0, nj| {
1588                 let j = i + j0;
1589                 if i == j {
1590                     assert_eq!(ni.cmp(nj), Equal);
1591                     assert_eq!(nj.cmp(ni), Equal);
1592                     assert!(ni == nj);
1593                     assert!(!(ni != nj));
1594                     assert!(ni <= nj);
1595                     assert!(ni >= nj);
1596                     assert!(!(ni < nj));
1597                     assert!(!(ni > nj));
1598                 } else {
1599                     assert_eq!(ni.cmp(nj), Less);
1600                     assert_eq!(nj.cmp(ni), Greater);
1601
1602                     assert!(!(ni == nj));
1603                     assert!(ni != nj);
1604
1605                     assert!(ni <= nj);
1606                     assert!(!(ni >= nj));
1607                     assert!(ni < nj);
1608                     assert!(!(ni > nj));
1609
1610                     assert!(!(nj <= ni));
1611                     assert!(nj >= ni);
1612                     assert!(!(nj < ni));
1613                     assert!(nj > ni);
1614                 }
1615             }
1616         }
1617     }
1618
1619     #[test]
1620     fn test_convert_int() {
1621         fn check(b: BigInt, i: int) {
1622             assert!(b == IntConvertible::from_int(i));
1623             assert!(b.to_int() == i);
1624         }
1625
1626         check(Zero::zero(), 0);
1627         check(One::one(), 1);
1628         check(BigInt::from_biguint(
1629             Plus, BigUint::from_uint(int::max_value as uint)
1630         ), int::max_value);
1631
1632         assert!(BigInt::from_biguint(
1633             Plus, BigUint::from_uint(int::max_value as uint + 1)
1634         ).to_int() == int::max_value);
1635         assert!(BigInt::from_biguint(
1636             Plus, BigUint::new(~[1, 2, 3])
1637         ).to_int() == int::max_value);
1638
1639         check(BigInt::from_biguint(
1640             Minus, BigUint::from_uint(-int::min_value as uint)
1641         ), int::min_value);
1642         assert!(BigInt::from_biguint(
1643             Minus, BigUint::from_uint(-int::min_value as uint + 1)
1644         ).to_int() == int::min_value);
1645         assert!(BigInt::from_biguint(
1646             Minus, BigUint::new(~[1, 2, 3])
1647         ).to_int() == int::min_value);
1648     }
1649
1650     #[test]
1651     fn test_convert_uint() {
1652         fn check(b: BigInt, u: uint) {
1653             assert!(b == BigInt::from_uint(u));
1654             assert!(b.to_uint() == u);
1655         }
1656
1657         check(Zero::zero(), 0);
1658         check(One::one(), 1);
1659
1660         check(
1661             BigInt::from_biguint(Plus, BigUint::from_uint(uint::max_value)),
1662             uint::max_value);
1663         assert!(BigInt::from_biguint(
1664             Plus, BigUint::new(~[1, 2, 3])
1665         ).to_uint() == uint::max_value);
1666
1667         assert!(BigInt::from_biguint(
1668             Minus, BigUint::from_uint(uint::max_value)
1669         ).to_uint() == 0);
1670         assert!(BigInt::from_biguint(
1671             Minus, BigUint::new(~[1, 2, 3])
1672         ).to_uint() == 0);
1673     }
1674
1675     static sum_triples: &'static [(&'static [BigDigit],
1676                                    &'static [BigDigit],
1677                                    &'static [BigDigit])] = &[
1678         (&[],          &[],       &[]),
1679         (&[],          &[ 1],     &[ 1]),
1680         (&[ 1],        &[ 1],     &[ 2]),
1681         (&[ 1],        &[ 1,  1], &[ 2,  1]),
1682         (&[ 1],        &[-1],     &[ 0,  1]),
1683         (&[ 1],        &[-1, -1], &[ 0,  0, 1]),
1684         (&[-1, -1],    &[-1, -1], &[-2, -1, 1]),
1685         (&[ 1,  1, 1], &[-1, -1], &[ 0,  1, 2]),
1686         (&[ 2,  2, 1], &[-1, -2], &[ 1,  1, 2])
1687     ];
1688
1689     #[test]
1690     fn test_add() {
1691         for sum_triples.each |elm| {
1692             let (aVec, bVec, cVec) = *elm;
1693             let a = BigInt::from_slice(Plus, aVec);
1694             let b = BigInt::from_slice(Plus, bVec);
1695             let c = BigInt::from_slice(Plus, cVec);
1696
1697             assert!(a + b == c);
1698             assert!(b + a == c);
1699             assert!(c + (-a) == b);
1700             assert!(c + (-b) == a);
1701             assert!(a + (-c) == (-b));
1702             assert!(b + (-c) == (-a));
1703             assert!((-a) + (-b) == (-c));
1704             assert!(a + (-a) == Zero::zero());
1705         }
1706     }
1707
1708     #[test]
1709     fn test_sub() {
1710         for sum_triples.each |elm| {
1711             let (aVec, bVec, cVec) = *elm;
1712             let a = BigInt::from_slice(Plus, aVec);
1713             let b = BigInt::from_slice(Plus, bVec);
1714             let c = BigInt::from_slice(Plus, cVec);
1715
1716             assert!(c - a == b);
1717             assert!(c - b == a);
1718             assert!((-b) - a == (-c));
1719             assert!((-a) - b == (-c));
1720             assert!(b - (-a) == c);
1721             assert!(a - (-b) == c);
1722             assert!((-c) - (-a) == (-b));
1723             assert!(a - a == Zero::zero());
1724         }
1725     }
1726
1727     static mul_triples: &'static [(&'static [BigDigit],
1728                                    &'static [BigDigit],
1729                                    &'static [BigDigit])] = &[
1730         (&[],               &[],               &[]),
1731         (&[],               &[ 1],             &[]),
1732         (&[ 2],             &[],               &[]),
1733         (&[ 1],             &[ 1],             &[1]),
1734         (&[ 2],             &[ 3],             &[ 6]),
1735         (&[ 1],             &[ 1,  1,  1],     &[1, 1,  1]),
1736         (&[ 1,  2,  3],     &[ 3],             &[ 3,  6,  9]),
1737         (&[ 1,  1,  1],     &[-1],             &[-1, -1, -1]),
1738         (&[ 1,  2,  3],     &[-1],             &[-1, -2, -2, 2]),
1739         (&[ 1,  2,  3,  4], &[-1],             &[-1, -2, -2, -2, 3]),
1740         (&[-1],             &[-1],             &[ 1, -2]),
1741         (&[-1, -1],         &[-1],             &[ 1, -1, -2]),
1742         (&[-1, -1, -1],     &[-1],             &[ 1, -1, -1, -2]),
1743         (&[-1, -1, -1, -1], &[-1],             &[ 1, -1, -1, -1, -2]),
1744         (&[-1/2 + 1],       &[ 2],             &[ 0,  1]),
1745         (&[0, -1/2 + 1],    &[ 2],             &[ 0,  0,  1]),
1746         (&[ 1,  2],         &[ 1,  2,  3],     &[1, 4,  7,  6]),
1747         (&[-1, -1],         &[-1, -1, -1],     &[1, 0, -1, -2, -1]),
1748         (&[-1, -1, -1],     &[-1, -1, -1, -1], &[1, 0,  0, -1, -2, -1, -1]),
1749         (&[ 0,  0,  1],     &[ 1,  2,  3],     &[0, 0,  1,  2,  3]),
1750         (&[ 0,  0,  1],     &[ 0,  0,  0,  1], &[0, 0,  0,  0,  0,  1])
1751     ];
1752
1753     static quot_rem_quadruples: &'static [(&'static [BigDigit],
1754                                            &'static [BigDigit],
1755                                            &'static [BigDigit],
1756                                            &'static [BigDigit])]
1757         = &[
1758             (&[ 1],        &[ 2], &[],               &[1]),
1759             (&[ 1,  1],    &[ 2], &[-1/2+1],         &[1]),
1760             (&[ 1,  1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
1761             (&[ 0,  1],    &[-1], &[1],              &[1]),
1762             (&[-1, -1],    &[-2], &[2, 1],           &[3])
1763         ];
1764
1765     #[test]
1766     fn test_mul() {
1767         for mul_triples.each |elm| {
1768             let (aVec, bVec, cVec) = *elm;
1769             let a = BigInt::from_slice(Plus, aVec);
1770             let b = BigInt::from_slice(Plus, bVec);
1771             let c = BigInt::from_slice(Plus, cVec);
1772
1773             assert!(a * b == c);
1774             assert!(b * a == c);
1775
1776             assert!((-a) * b == -c);
1777             assert!((-b) * a == -c);
1778         }
1779
1780         for quot_rem_quadruples.each |elm| {
1781             let (aVec, bVec, cVec, dVec) = *elm;
1782             let a = BigInt::from_slice(Plus, aVec);
1783             let b = BigInt::from_slice(Plus, bVec);
1784             let c = BigInt::from_slice(Plus, cVec);
1785             let d = BigInt::from_slice(Plus, dVec);
1786
1787             assert!(a == b * c + d);
1788             assert!(a == c * b + d);
1789         }
1790     }
1791
1792     #[test]
1793     fn test_div_mod() {
1794         fn check_sub(a: &BigInt, b: &BigInt, ans_d: &BigInt, ans_m: &BigInt) {
1795             let (d, m) = a.div_mod(b);
1796             if !m.is_zero() {
1797                 assert!(m.sign == b.sign);
1798             }
1799             assert!(m.abs() <= b.abs());
1800             assert!(*a == b * d + m);
1801             assert!(d == *ans_d);
1802             assert!(m == *ans_m);
1803         }
1804
1805         fn check(a: &BigInt, b: &BigInt, d: &BigInt, m: &BigInt) {
1806             if m.is_zero() {
1807                 check_sub(a, b, d, m);
1808                 check_sub(a, &b.neg(), &d.neg(), m);
1809                 check_sub(&a.neg(), b, &d.neg(), m);
1810                 check_sub(&a.neg(), &b.neg(), d, m);
1811             } else {
1812                 check_sub(a, b, d, m);
1813                 check_sub(a, &b.neg(), &(d.neg() - One::one()), &(m - *b));
1814                 check_sub(&a.neg(), b, &(d.neg() - One::one()), &(b - *m));
1815                 check_sub(&a.neg(), &b.neg(), d, &m.neg());
1816             }
1817         }
1818
1819         for mul_triples.each |elm| {
1820             let (aVec, bVec, cVec) = *elm;
1821             let a = BigInt::from_slice(Plus, aVec);
1822             let b = BigInt::from_slice(Plus, bVec);
1823             let c = BigInt::from_slice(Plus, cVec);
1824
1825             if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
1826             if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
1827         }
1828
1829         for quot_rem_quadruples.each |elm| {
1830             let (aVec, bVec, cVec, dVec) = *elm;
1831             let a = BigInt::from_slice(Plus, aVec);
1832             let b = BigInt::from_slice(Plus, bVec);
1833             let c = BigInt::from_slice(Plus, cVec);
1834             let d = BigInt::from_slice(Plus, dVec);
1835
1836             if !b.is_zero() {
1837                 check(&a, &b, &c, &d);
1838             }
1839         }
1840     }
1841
1842
1843     #[test]
1844     fn test_quot_rem() {
1845         fn check_sub(a: &BigInt, b: &BigInt, ans_q: &BigInt, ans_r: &BigInt) {
1846             let (q, r) = a.quot_rem(b);
1847             if !r.is_zero() {
1848                 assert!(r.sign == a.sign);
1849             }
1850             assert!(r.abs() <= b.abs());
1851             assert!(*a == b * q + r);
1852             assert!(q == *ans_q);
1853             assert!(r == *ans_r);
1854         }
1855
1856         fn check(a: &BigInt, b: &BigInt, q: &BigInt, r: &BigInt) {
1857             check_sub(a, b, q, r);
1858             check_sub(a, &b.neg(), &q.neg(), r);
1859             check_sub(&a.neg(), b, &q.neg(), &r.neg());
1860             check_sub(&a.neg(), &b.neg(), q, &r.neg());
1861         }
1862         for mul_triples.each |elm| {
1863             let (aVec, bVec, cVec) = *elm;
1864             let a = BigInt::from_slice(Plus, aVec);
1865             let b = BigInt::from_slice(Plus, bVec);
1866             let c = BigInt::from_slice(Plus, cVec);
1867
1868             if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
1869             if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
1870         }
1871
1872         for quot_rem_quadruples.each |elm| {
1873             let (aVec, bVec, cVec, dVec) = *elm;
1874             let a = BigInt::from_slice(Plus, aVec);
1875             let b = BigInt::from_slice(Plus, bVec);
1876             let c = BigInt::from_slice(Plus, cVec);
1877             let d = BigInt::from_slice(Plus, dVec);
1878
1879             if !b.is_zero() {
1880                 check(&a, &b, &c, &d);
1881             }
1882         }
1883     }
1884
1885     #[test]
1886     fn test_gcd() {
1887         fn check(a: int, b: int, c: int) {
1888             let big_a: BigInt = IntConvertible::from_int(a);
1889             let big_b: BigInt = IntConvertible::from_int(b);
1890             let big_c: BigInt = IntConvertible::from_int(c);
1891
1892             assert_eq!(big_a.gcd(&big_b), big_c);
1893         }
1894
1895         check(10, 2, 2);
1896         check(10, 3, 1);
1897         check(0, 3, 3);
1898         check(3, 3, 3);
1899         check(56, 42, 14);
1900         check(3, -3, 3);
1901         check(-6, 3, 3);
1902         check(-4, -2, 2);
1903     }
1904
1905     #[test]
1906     fn test_lcm() {
1907         fn check(a: int, b: int, c: int) {
1908             let big_a: BigInt = IntConvertible::from_int(a);
1909             let big_b: BigInt = IntConvertible::from_int(b);
1910             let big_c: BigInt = IntConvertible::from_int(c);
1911
1912             assert_eq!(big_a.lcm(&big_b), big_c);
1913         }
1914
1915         check(1, 0, 0);
1916         check(0, 1, 0);
1917         check(1, 1, 1);
1918         check(-1, 1, 1);
1919         check(1, -1, 1);
1920         check(-1, -1, 1);
1921         check(8, 9, 72);
1922         check(11, 5, 55);
1923     }
1924
1925     #[test]
1926     fn test_to_str_radix() {
1927         fn check(n: int, ans: &str) {
1928             assert!(ans == IntConvertible::from_int::<BigInt>(n).to_str_radix(10));
1929         }
1930         check(10, "10");
1931         check(1, "1");
1932         check(0, "0");
1933         check(-1, "-1");
1934         check(-10, "-10");
1935     }
1936
1937
1938     #[test]
1939     fn test_from_str_radix() {
1940         fn check(s: &str, ans: Option<int>) {
1941             let ans = ans.map(|&n| IntConvertible::from_int::<BigInt>(n));
1942             assert!(FromStrRadix::from_str_radix(s, 10) == ans);
1943         }
1944         check("10", Some(10));
1945         check("1", Some(1));
1946         check("0", Some(0));
1947         check("-1", Some(-1));
1948         check("-10", Some(-10));
1949         check("Z", None);
1950         check("_", None);
1951     }
1952
1953     #[test]
1954     fn test_neg() {
1955         assert!(-BigInt::new(Plus,  ~[1, 1, 1]) ==
1956             BigInt::new(Minus, ~[1, 1, 1]));
1957         assert!(-BigInt::new(Minus, ~[1, 1, 1]) ==
1958             BigInt::new(Plus,  ~[1, 1, 1]));
1959         assert!(-Zero::zero::<BigInt>() == Zero::zero::<BigInt>());
1960     }
1961 }
1962