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
  25 /**
  26 A BigDigit is a BigUint's composing element.
  27
  28 A BigDigit is half the size of machine word size.
  29 */
  30 #[cfg(target_arch = "x86")]
  31 #[cfg(target_arch = "arm")]
  32 #[cfg(target_arch = "mips")]
  33 pub type BigDigit = u16;
  34
  35 /**
  36 A BigDigit is a BigUint's composing element.
  37
  38 A BigDigit is half the size of machine word size.
  39 */
  40 #[cfg(target_arch = "x86_64")]
  41 pub type BigDigit = u32;
  42
  43 pub mod BigDigit {
  44     use bigint::BigDigit;
  45
  46     #[cfg(target_arch = "x86")]
  47     #[cfg(target_arch = "arm")]
  48     #[cfg(target_arch = "mips")]
  49     pub static bits: uint = 16;
  50
  51     #[cfg(target_arch = "x86_64")]
  52     pub static bits: uint = 32;
  53
  54     pub static base: uint = 1 << bits;
  55     priv static hi_mask: uint = (-1 as uint) << bits;
  56     priv static lo_mask: uint = (-1 as uint) >> bits;
  57
  58     #[inline(always)]
  59     priv fn get_hi(n: uint) -> BigDigit { (n >> bits) as BigDigit }
  60     #[inline(always)]
  61     priv fn get_lo(n: uint) -> BigDigit { (n & lo_mask) as BigDigit }
  62
  63     /// Split one machine sized unsigned integer into two BigDigits.
  64     #[inline(always)]
  65     pub fn from_uint(n: uint) -> (BigDigit, BigDigit) {
  66         (get_hi(n), get_lo(n))
  67     }
  68
  69     /// Join two BigDigits into one machine sized unsigned integer
  70     #[inline(always)]
  71     pub fn to_uint(hi: BigDigit, lo: BigDigit) -> uint {
  72         (lo as uint) | ((hi as uint) << bits)
  73     }
  74 }
  75
  76 /**
  77 A big unsigned integer type.
  78
  79 A BigUint-typed value BigUint { data: @[a, b, c] } represents a number
  80 (a + b * BigDigit::base + c * BigDigit::base^2).
  81 */
  82 #[deriving(Clone)]
  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 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 Div<BigUint, BigUint> for BigUint {
 297     #[inline(always)]
 298     fn div(&self, other: &BigUint) -> BigUint {
 299         let (q, _) = self.div_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.div_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_rem(&self, other: &BigUint) -> (BigUint, BigUint) {
 320         self.div_mod_floor(other)
 321     }
 322
 323     #[inline(always)]
 324     fn div_floor(&self, other: &BigUint) -> BigUint {
 325         let (d, _) = self.div_mod_floor(other);
 326         return d;
 327     }
 328
 329     #[inline(always)]
 330     fn mod_floor(&self, other: &BigUint) -> BigUint {
 331         let (_, m) = self.div_mod_floor(other);
 332         return m;
 333     }
 334
 335     #[inline(always)]
 336     fn div_mod_floor(&self, other: &BigUint) -> (BigUint, BigUint) {
 337         if other.is_zero() { fail!() }
 338         if self.is_zero() { return (Zero::zero(), Zero::zero()); }
 339         if *other == One::one() { return (copy *self, Zero::zero()); }
 340
 341         match self.cmp(other) {
 342             Less    => return (Zero::zero(), copy *self),
 343             Equal   => return (One::one(), Zero::zero()),
 344             Greater => {} // Do nothing
 345         }
 346
 347         let mut shift = 0;
 348         let mut n = *other.data.last();
 349         while n < (1 << BigDigit::bits - 2) {
 350             n <<= 1;
 351             shift += 1;
 352         }
 353         assert!(shift < BigDigit::bits);
 354         let (d, m) = div_mod_floor_inner(self << shift, other << shift);
 355         return (d, m >> shift);
 356
 357         #[inline(always)]
 358         fn div_mod_floor_inner(a: BigUint, b: BigUint) -> (BigUint, BigUint) {
 359             let mut m = a;
 360             let mut d = Zero::zero::<BigUint>();
 361             let mut n = 1;
 362             while m >= b {
 363                 let mut (d0, d_unit, b_unit) = div_estimate(&m, &b, n);
 364                 let mut prod = b * d0;
 365                 while prod > m {
 366                     // FIXME(#6050): overloaded operators force moves with generic types
 367                     // d0 -= d_unit
 368                     d0   = d0 - d_unit;
 369                     // FIXME(#6050): overloaded operators force moves with generic types
 370                     // prod = prod - b_unit;
 371                     prod = prod - b_unit
 372                 }
 373                 if d0.is_zero() {
 374                     n = 2;
 375                     loop;
 376                 }
 377                 n = 1;
 378                 // FIXME(#6102): Assignment operator for BigInt causes ICE
 379                 // d += d0;
 380                 d = d + d0;
 381                 // FIXME(#6102): Assignment operator for BigInt causes ICE
 382                 // m -= prod;
 383                 m = m - prod;
 384             }
 385             return (d, m);
 386         }
 387
 388         #[inline(always)]
 389         fn div_estimate(a: &BigUint, b: &BigUint, n: uint)
 390             -> (BigUint, BigUint, BigUint) {
 391             if a.data.len() < n {
 392                 return (Zero::zero(), Zero::zero(), copy *a);
 393             }
 394
 395             let an = vec::slice(a.data, a.data.len() - n, a.data.len());
 396             let bn = *b.data.last();
 397             let mut d = ~[];
 398             let mut carry = 0;
 399             for an.each_reverse |elt| {
 400                 let ai = BigDigit::to_uint(carry, *elt);
 401                 let di = ai / (bn as uint);
 402                 assert!(di < BigDigit::base);
 403                 carry = (ai % (bn as uint)) as BigDigit;
 404                 d = ~[di as BigDigit] + d;
 405             }
 406
 407             let shift = (a.data.len() - an.len()) - (b.data.len() - 1);
 408             if shift == 0 {
 409                 return (BigUint::new(d), One::one(), copy *b);
 410             }
 411             return (BigUint::from_slice(d).shl_unit(shift),
 412                     One::one::<BigUint>().shl_unit(shift),
 413                     b.shl_unit(shift));
 414         }
 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_floor(&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, Clone)]
 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 #[deriving(Clone)]
 730 pub struct BigInt {
 731     priv sign: Sign,
 732     priv data: BigUint
 733 }
 734
 735 impl Eq for BigInt {
 736     #[inline(always)]
 737     fn eq(&self, other: &BigInt) -> bool { self.equals(other) }
 738     #[inline(always)]
 739     fn ne(&self, other: &BigInt) -> bool { !self.equals(other) }
 740 }
 741
 742 impl TotalEq for BigInt {
 743     #[inline(always)]
 744     fn equals(&self, other: &BigInt) -> bool {
 745         match self.cmp(other) { Equal => true, _ => false }
 746     }
 747 }
 748
 749 impl Ord for BigInt {
 750     #[inline(always)]
 751     fn lt(&self, other: &BigInt) -> bool {
 752         match self.cmp(other) { Less => true, _ => false}
 753     }
 754     #[inline(always)]
 755     fn le(&self, other: &BigInt) -> bool {
 756         match self.cmp(other) { Less | Equal => true, _ => false }
 757     }
 758     #[inline(always)]
 759     fn ge(&self, other: &BigInt) -> bool {
 760         match self.cmp(other) { Greater | Equal => true, _ => false }
 761     }
 762     #[inline(always)]
 763     fn gt(&self, other: &BigInt) -> bool {
 764         match self.cmp(other) { Greater => true, _ => false }
 765     }
 766 }
 767
 768 impl TotalOrd for BigInt {
 769     #[inline(always)]
 770     fn cmp(&self, other: &BigInt) -> Ordering {
 771         let scmp = self.sign.cmp(&other.sign);
 772         if scmp != Equal { return scmp; }
 773
 774         match self.sign {
 775             Zero  => Equal,
 776             Plus  => self.data.cmp(&other.data),
 777             Minus => other.data.cmp(&self.data),
 778         }
 779     }
 780 }
 781
 782 impl ToStr for BigInt {
 783     #[inline(always)]
 784     fn to_str(&self) -> ~str { self.to_str_radix(10) }
 785 }
 786
 787 impl FromStr for BigInt {
 788     #[inline(always)]
 789     fn from_str(s: &str) -> Option<BigInt> {
 790         FromStrRadix::from_str_radix(s, 10)
 791     }
 792 }
 793
 794 impl Shl<uint, BigInt> for BigInt {
 795     #[inline(always)]
 796     fn shl(&self, rhs: &uint) -> BigInt {
 797         BigInt::from_biguint(self.sign, self.data << *rhs)
 798     }
 799 }
 800
 801 impl Shr<uint, BigInt> for BigInt {
 802     #[inline(always)]
 803     fn shr(&self, rhs: &uint) -> BigInt {
 804         BigInt::from_biguint(self.sign, self.data >> *rhs)
 805     }
 806 }
 807
 808 impl Zero for BigInt {
 809     #[inline(always)]
 810     fn zero() -> BigInt {
 811         BigInt::from_biguint(Zero, Zero::zero())
 812     }
 813
 814     #[inline(always)]
 815     fn is_zero(&self) -> bool { self.sign == Zero }
 816 }
 817
 818 impl One for BigInt {
 819     #[inline(always)]
 820     fn one() -> BigInt {
 821         BigInt::from_biguint(Plus, One::one())
 822     }
 823 }
 824
 825 impl Signed for BigInt {
 826     #[inline(always)]
 827     fn abs(&self) -> BigInt {
 828         match self.sign {
 829             Plus | Zero => self.clone(),
 830             Minus => BigInt::from_biguint(Plus, self.data.clone())
 831         }
 832     }
 833
 834     #[inline(always)]
 835     fn signum(&self) -> BigInt {
 836         match self.sign {
 837             Plus  => BigInt::from_biguint(Plus, One::one()),
 838             Minus => BigInt::from_biguint(Minus, One::one()),
 839             Zero  => Zero::zero(),
 840         }
 841     }
 842
 843     #[inline(always)]
 844     fn is_positive(&self) -> bool { self.sign == Plus }
 845
 846     #[inline(always)]
 847     fn is_negative(&self) -> bool { self.sign == Minus }
 848 }
 849
 850 impl Add<BigInt, BigInt> for BigInt {
 851     #[inline(always)]
 852     fn add(&self, other: &BigInt) -> BigInt {
 853         match (self.sign, other.sign) {
 854             (Zero, _)      => other.clone(),
 855             (_,    Zero)   => self.clone(),
 856             (Plus, Plus)   => BigInt::from_biguint(Plus,
 857                                                    self.data + other.data),
 858             (Plus, Minus)  => self - (-*other),
 859             (Minus, Plus)  => other - (-*self),
 860             (Minus, Minus) => -((-self) + (-*other))
 861         }
 862     }
 863 }
 864
 865 impl Sub<BigInt, BigInt> for BigInt {
 866     #[inline(always)]
 867     fn sub(&self, other: &BigInt) -> BigInt {
 868         match (self.sign, other.sign) {
 869             (Zero, _)    => -other,
 870             (_,    Zero) => self.clone(),
 871             (Plus, Plus) => match self.data.cmp(&other.data) {
 872                 Less    => BigInt::from_biguint(Minus, other.data - self.data),
 873                 Greater => BigInt::from_biguint(Plus, self.data - other.data),
 874                 Equal   => Zero::zero()
 875             },
 876             (Plus, Minus) => self + (-*other),
 877             (Minus, Plus) => -((-self) + *other),
 878             (Minus, Minus) => (-other) - (-*self)
 879         }
 880     }
 881 }
 882
 883 impl Mul<BigInt, BigInt> for BigInt {
 884     #[inline(always)]
 885     fn mul(&self, other: &BigInt) -> BigInt {
 886         match (self.sign, other.sign) {
 887             (Zero, _)     | (_,     Zero)  => Zero::zero(),
 888             (Plus, Plus)  | (Minus, Minus) => {
 889                 BigInt::from_biguint(Plus, self.data * other.data)
 890             },
 891             (Plus, Minus) | (Minus, Plus) => {
 892                 BigInt::from_biguint(Minus, self.data * other.data)
 893             }
 894         }
 895     }
 896 }
 897
 898 impl Div<BigInt, BigInt> for BigInt {
 899     #[inline(always)]
 900     fn div(&self, other: &BigInt) -> BigInt {
 901         let (q, _) = self.div_rem(other);
 902         return q;
 903     }
 904 }
 905
 906 impl Rem<BigInt, BigInt> for BigInt {
 907     #[inline(always)]
 908     fn rem(&self, other: &BigInt) -> BigInt {
 909         let (_, r) = self.div_rem(other);
 910         return r;
 911     }
 912 }
 913
 914 impl Neg<BigInt> for BigInt {
 915     #[inline(always)]
 916     fn neg(&self) -> BigInt {
 917         BigInt::from_biguint(self.sign.neg(), self.data.clone())
 918     }
 919 }
 920
 921 impl Integer for BigInt {
 922     #[inline(always)]
 923     fn div_rem(&self, other: &BigInt) -> (BigInt, BigInt) {
 924         // r.sign == self.sign
 925         let (d_ui, r_ui) = self.data.div_mod_floor(&other.data);
 926         let d = BigInt::from_biguint(Plus, d_ui);
 927         let r = BigInt::from_biguint(Plus, r_ui);
 928         match (self.sign, other.sign) {
 929             (_,    Zero)   => fail!(),
 930             (Plus, Plus)  | (Zero, Plus)  => ( d,  r),
 931             (Plus, Minus) | (Zero, Minus) => (-d,  r),
 932             (Minus, Plus)                 => (-d, -r),
 933             (Minus, Minus)                => ( d, -r)
 934         }
 935     }
 936
 937     #[inline(always)]
 938     fn div_floor(&self, other: &BigInt) -> BigInt {
 939         let (d, _) = self.div_mod_floor(other);
 940         return d;
 941     }
 942
 943     #[inline(always)]
 944     fn mod_floor(&self, other: &BigInt) -> BigInt {
 945         let (_, m) = self.div_mod_floor(other);
 946         return m;
 947     }
 948
 949     #[inline(always)]
 950     fn div_mod_floor(&self, other: &BigInt) -> (BigInt, BigInt) {
 951         // m.sign == other.sign
 952         let (d_ui, m_ui) = self.data.div_rem(&other.data);
 953         let d = BigInt::from_biguint(Plus, d_ui),
 954             m = BigInt::from_biguint(Plus, m_ui);
 955         match (self.sign, other.sign) {
 956             (_,    Zero)   => fail!(),
 957             (Plus, Plus)  | (Zero, Plus)  => (d, m),
 958             (Plus, Minus) | (Zero, Minus) => if m.is_zero() {
 959                 (-d, Zero::zero())
 960             } else {
 961                 (-d - One::one(), m + *other)
 962             },
 963             (Minus, Plus) => if m.is_zero() {
 964                 (-d, Zero::zero())
 965             } else {
 966                 (-d - One::one(), other - m)
 967             },
 968             (Minus, Minus) => (d, -m)
 969         }
 970     }
 971
 972     /**
 973      * Calculates the Greatest Common Divisor (GCD) of the number and `other`
 974      *
 975      * The result is always positive
 976      */
 977     #[inline(always)]
 978     fn gcd(&self, other: &BigInt) -> BigInt {
 979         BigInt::from_biguint(Plus, self.data.gcd(&other.data))
 980     }
 981
 982     /**
 983      * Calculates the Lowest Common Multiple (LCM) of the number and `other`
 984      */
 985     #[inline(always)]
 986     fn lcm(&self, other: &BigInt) -> BigInt {
 987         BigInt::from_biguint(Plus, self.data.lcm(&other.data))
 988     }
 989
 990     /// Returns `true` if the number can be divided by `other` without leaving a remainder
 991     #[inline(always)]
 992     fn is_multiple_of(&self, other: &BigInt) -> bool { self.data.is_multiple_of(&other.data) }
 993
 994     /// Returns `true` if the number is divisible by `2`
 995     #[inline(always)]
 996     fn is_even(&self) -> bool { self.data.is_even() }
 997
 998     /// Returns `true` if the number is not divisible by `2`
 999     #[inline(always)]
1000     fn is_odd(&self) -> bool { self.data.is_odd() }
1001 }
1002
1003 impl IntConvertible for BigInt {
1004     #[inline(always)]
1005     fn to_int(&self) -> int {
1006         match self.sign {
1007             Plus  => uint::min(self.to_uint(), int::max_value as uint) as int,
1008             Zero  => 0,
1009             Minus => uint::min((-self).to_uint(),
1010                                (int::max_value as uint) + 1) as int
1011         }
1012     }
1013
1014     #[inline(always)]
1015     fn from_int(n: int) -> BigInt {
1016         if n > 0 {
1017            return BigInt::from_biguint(Plus,  BigUint::from_uint(n as uint));
1018         }
1019         if n < 0 {
1020             return BigInt::from_biguint(
1021                 Minus, BigUint::from_uint(uint::max_value - (n as uint) + 1)
1022             );
1023         }
1024         return Zero::zero();
1025     }
1026 }
1027
1028 impl ToStrRadix for BigInt {
1029     #[inline(always)]
1030     fn to_str_radix(&self, radix: uint) -> ~str {
1031         match self.sign {
1032             Plus  => self.data.to_str_radix(radix),
1033             Zero  => ~"0",
1034             Minus => ~"-" + self.data.to_str_radix(radix)
1035         }
1036     }
1037 }
1038
1039 impl FromStrRadix for BigInt {
1040     /// Creates and initializes an BigInt.
1041     #[inline(always)]
1042     fn from_str_radix(s: &str, radix: uint)
1043         -> Option<BigInt> {
1044         BigInt::parse_bytes(str::to_bytes(s), radix)
1045     }
1046 }
1047
1048 pub impl BigInt {
1049     /// Creates and initializes an BigInt.
1050     #[inline(always)]
1051     pub fn new(sign: Sign, v: ~[BigDigit]) -> BigInt {
1052         BigInt::from_biguint(sign, BigUint::new(v))
1053     }
1054
1055     /// Creates and initializes an BigInt.
1056     #[inline(always)]
1057     pub fn from_biguint(sign: Sign, data: BigUint) -> BigInt {
1058         if sign == Zero || data.is_zero() {
1059             return BigInt { sign: Zero, data: Zero::zero() };
1060         }
1061         return BigInt { sign: sign, data: data };
1062     }
1063
1064     /// Creates and initializes an BigInt.
1065     #[inline(always)]
1066     pub fn from_uint(n: uint) -> BigInt {
1067         if n == 0 { return Zero::zero(); }
1068         return BigInt::from_biguint(Plus, BigUint::from_uint(n));
1069     }
1070
1071     /// Creates and initializes an BigInt.
1072     #[inline(always)]
1073     pub fn from_slice(sign: Sign, slice: &[BigDigit]) -> BigInt {
1074         BigInt::from_biguint(sign, BigUint::from_slice(slice))
1075     }
1076
1077     /// Creates and initializes an BigInt.
1078     #[inline(always)]
1079     pub fn parse_bytes(buf: &[u8], radix: uint)
1080         -> Option<BigInt> {
1081         if buf.is_empty() { return None; }
1082         let mut sign  = Plus;
1083         let mut start = 0;
1084         if buf[0] == ('-' as u8) {
1085             sign  = Minus;
1086             start = 1;
1087         }
1088         return BigUint::parse_bytes(vec::slice(buf, start, buf.len()), radix)
1089             .map_consume(|bu| BigInt::from_biguint(sign, bu));
1090     }
1091
1092     #[inline(always)]
1093     fn to_uint(&self) -> uint {
1094         match self.sign {
1095             Plus  => self.data.to_uint(),
1096             Zero  => 0,
1097             Minus => 0
1098         }
1099     }
1100 }
1101
1102 #[cfg(test)]
1103 mod biguint_tests {
1104     use super::*;
1105     use core::num::{IntConvertible, Zero, One, FromStrRadix};
1106     use core::cmp::{Less, Equal, Greater};
1107
1108     #[test]
1109     fn test_from_slice() {
1110         fn check(slice: &[BigDigit], data: &[BigDigit]) {
1111             assert!(data == BigUint::from_slice(slice).data);
1112         }
1113         check(~[1], ~[1]);
1114         check(~[0, 0, 0], ~[]);
1115         check(~[1, 2, 0, 0], ~[1, 2]);
1116         check(~[0, 0, 1, 2], ~[0, 0, 1, 2]);
1117         check(~[0, 0, 1, 2, 0, 0], ~[0, 0, 1, 2]);
1118         check(~[-1], ~[-1]);
1119     }
1120
1121     #[test]
1122     fn test_cmp() {
1123         let data = [ &[], &[1], &[2], &[-1], &[0, 1], &[2, 1], &[1, 1, 1]  ]
1124             .map(|v| BigUint::from_slice(*v));
1125         for data.eachi |i, ni| {
1126             for vec::slice(data, i, data.len()).eachi |j0, nj| {
1127                 let j = j0 + i;
1128                 if i == j {
1129                     assert_eq!(ni.cmp(nj), Equal);
1130                     assert_eq!(nj.cmp(ni), Equal);
1131                     assert!(ni == nj);
1132                     assert!(!(ni != nj));
1133                     assert!(ni <= nj);
1134                     assert!(ni >= nj);
1135                     assert!(!(ni < nj));
1136                     assert!(!(ni > nj));
1137                 } else {
1138                     assert_eq!(ni.cmp(nj), Less);
1139                     assert_eq!(nj.cmp(ni), Greater);
1140
1141                     assert!(!(ni == nj));
1142                     assert!(ni != nj);
1143
1144                     assert!(ni <= nj);
1145                     assert!(!(ni >= nj));
1146                     assert!(ni < nj);
1147                     assert!(!(ni > nj));
1148
1149                     assert!(!(nj <= ni));
1150                     assert!(nj >= ni);
1151                     assert!(!(nj < ni));
1152                     assert!(nj > ni);
1153                 }
1154             }
1155         }
1156     }
1157
1158     #[test]
1159     fn test_shl() {
1160         fn check(v: ~[BigDigit], shift: uint, ans: ~[BigDigit]) {
1161             assert!(BigUint::new(v) << shift == BigUint::new(ans));
1162         }
1163
1164         check(~[], 3, ~[]);
1165         check(~[1, 1, 1], 3, ~[1 << 3, 1 << 3, 1 << 3]);
1166         check(~[1 << (BigDigit::bits - 2)], 2, ~[0, 1]);
1167         check(~[1 << (BigDigit::bits - 2)], 3, ~[0, 2]);
1168         check(~[1 << (BigDigit::bits - 2)], 3 + BigDigit::bits, ~[0, 0, 2]);
1169
1170         test_shl_bits();
1171
1172         #[cfg(target_arch = "x86_64")]
1173         fn test_shl_bits() {
1174             check(~[0x7654_3210, 0xfedc_ba98,
1175                     0x7654_3210, 0xfedc_ba98], 4,
1176                   ~[0x6543_2100, 0xedcb_a987,
1177                     0x6543_210f, 0xedcb_a987, 0xf]);
1178             check(~[0x2222_1111, 0x4444_3333,
1179                     0x6666_5555, 0x8888_7777], 16,
1180                   ~[0x1111_0000, 0x3333_2222,
1181                     0x5555_4444, 0x7777_6666, 0x8888]);
1182         }
1183
1184         #[cfg(target_arch = "arm")]
1185         #[cfg(target_arch = "x86")]
1186         #[cfg(target_arch = "mips")]
1187         fn test_shl_bits() {
1188             check(~[0x3210, 0x7654, 0xba98, 0xfedc,
1189                     0x3210, 0x7654, 0xba98, 0xfedc], 4,
1190                   ~[0x2100, 0x6543, 0xa987, 0xedcb,
1191                     0x210f, 0x6543, 0xa987, 0xedcb, 0xf]);
1192             check(~[0x1111, 0x2222, 0x3333, 0x4444,
1193                     0x5555, 0x6666, 0x7777, 0x8888], 16,
1194                   ~[0x0000, 0x1111, 0x2222, 0x3333,
1195                     0x4444, 0x5555, 0x6666, 0x7777, 0x8888]);
1196         }
1197
1198     }
1199
1200     #[test]
1201     #[ignore(cfg(target_arch = "x86"))]
1202     #[ignore(cfg(target_arch = "arm"))]
1203     #[ignore(cfg(target_arch = "mips"))]
1204     fn test_shr() {
1205         fn check(v: ~[BigDigit], shift: uint, ans: ~[BigDigit]) {
1206             assert!(BigUint::new(v) >> shift == BigUint::new(ans));
1207         }
1208
1209         check(~[], 3, ~[]);
1210         check(~[1, 1, 1], 3,
1211               ~[1 << (BigDigit::bits - 3), 1 << (BigDigit::bits - 3)]);
1212         check(~[1 << 2], 2, ~[1]);
1213         check(~[1, 2], 3, ~[1 << (BigDigit::bits - 2)]);
1214         check(~[1, 1, 2], 3 + BigDigit::bits, ~[1 << (BigDigit::bits - 2)]);
1215         check(~[0, 1], 1, ~[0x80000000]);
1216         test_shr_bits();
1217
1218         #[cfg(target_arch = "x86_64")]
1219         fn test_shr_bits() {
1220             check(~[0x6543_2100, 0xedcb_a987,
1221                     0x6543_210f, 0xedcb_a987, 0xf], 4,
1222                   ~[0x7654_3210, 0xfedc_ba98,
1223                     0x7654_3210, 0xfedc_ba98]);
1224             check(~[0x1111_0000, 0x3333_2222,
1225                     0x5555_4444, 0x7777_6666, 0x8888], 16,
1226                   ~[0x2222_1111, 0x4444_3333,
1227                     0x6666_5555, 0x8888_7777]);
1228         }
1229
1230         #[cfg(target_arch = "arm")]
1231         #[cfg(target_arch = "x86")]
1232         #[cfg(target_arch = "mips")]
1233         fn test_shr_bits() {
1234             check(~[0x2100, 0x6543, 0xa987, 0xedcb,
1235                     0x210f, 0x6543, 0xa987, 0xedcb, 0xf], 4,
1236                   ~[0x3210, 0x7654, 0xba98, 0xfedc,
1237                     0x3210, 0x7654, 0xba98, 0xfedc]);
1238             check(~[0x0000, 0x1111, 0x2222, 0x3333,
1239                     0x4444, 0x5555, 0x6666, 0x7777, 0x8888], 16,
1240                   ~[0x1111, 0x2222, 0x3333, 0x4444,
1241                     0x5555, 0x6666, 0x7777, 0x8888]);
1242         }
1243     }
1244
1245     #[test]
1246     fn test_convert_int() {
1247         fn check(v: ~[BigDigit], i: int) {
1248             let b = BigUint::new(v);
1249             assert!(b == IntConvertible::from_int(i));
1250             assert!(b.to_int() == i);
1251         }
1252
1253         check(~[], 0);
1254         check(~[1], 1);
1255         check(~[-1], (uint::max_value >> BigDigit::bits) as int);
1256         check(~[ 0,  1], ((uint::max_value >> BigDigit::bits) + 1) as int);
1257         check(~[-1, -1 >> 1], int::max_value);
1258
1259         assert!(BigUint::new(~[0, -1]).to_int() == int::max_value);
1260         assert!(BigUint::new(~[0, 0, 1]).to_int() == int::max_value);
1261         assert!(BigUint::new(~[0, 0, -1]).to_int() == int::max_value);
1262     }
1263
1264     #[test]
1265     fn test_convert_uint() {
1266         fn check(v: ~[BigDigit], u: uint) {
1267             let b = BigUint::new(v);
1268             assert!(b == BigUint::from_uint(u));
1269             assert!(b.to_uint() == u);
1270         }
1271
1272         check(~[], 0);
1273         check(~[ 1], 1);
1274         check(~[-1], uint::max_value >> BigDigit::bits);
1275         check(~[ 0,  1], (uint::max_value >> BigDigit::bits) + 1);
1276         check(~[ 0, -1], uint::max_value << BigDigit::bits);
1277         check(~[-1, -1], uint::max_value);
1278
1279         assert!(BigUint::new(~[0, 0, 1]).to_uint()  == uint::max_value);
1280         assert!(BigUint::new(~[0, 0, -1]).to_uint() == uint::max_value);
1281     }
1282
1283     static sum_triples: &'static [(&'static [BigDigit],
1284                                    &'static [BigDigit],
1285                                    &'static [BigDigit])] = &[
1286         (&[],          &[],       &[]),
1287         (&[],          &[ 1],     &[ 1]),
1288         (&[ 1],        &[ 1],     &[ 2]),
1289         (&[ 1],        &[ 1,  1], &[ 2,  1]),
1290         (&[ 1],        &[-1],     &[ 0,  1]),
1291         (&[ 1],        &[-1, -1], &[ 0,  0, 1]),
1292         (&[-1, -1],    &[-1, -1], &[-2, -1, 1]),
1293         (&[ 1,  1, 1], &[-1, -1], &[ 0,  1, 2]),
1294         (&[ 2,  2, 1], &[-1, -2], &[ 1,  1, 2])
1295     ];
1296
1297     #[test]
1298     fn test_add() {
1299         for sum_triples.each |elm| {
1300             let (aVec, bVec, cVec) = *elm;
1301             let a = BigUint::from_slice(aVec);
1302             let b = BigUint::from_slice(bVec);
1303             let c = BigUint::from_slice(cVec);
1304
1305             assert!(a + b == c);
1306             assert!(b + a == c);
1307         }
1308     }
1309
1310     #[test]
1311     fn test_sub() {
1312         for sum_triples.each |elm| {
1313             let (aVec, bVec, cVec) = *elm;
1314             let a = BigUint::from_slice(aVec);
1315             let b = BigUint::from_slice(bVec);
1316             let c = BigUint::from_slice(cVec);
1317
1318             assert!(c - a == b);
1319             assert!(c - b == a);
1320         }
1321     }
1322
1323     static mul_triples: &'static [(&'static [BigDigit],
1324                                    &'static [BigDigit],
1325                                    &'static [BigDigit])] = &[
1326         (&[],               &[],               &[]),
1327         (&[],               &[ 1],             &[]),
1328         (&[ 2],             &[],               &[]),
1329         (&[ 1],             &[ 1],             &[1]),
1330         (&[ 2],             &[ 3],             &[ 6]),
1331         (&[ 1],             &[ 1,  1,  1],     &[1, 1,  1]),
1332         (&[ 1,  2,  3],     &[ 3],             &[ 3,  6,  9]),
1333         (&[ 1,  1,  1],     &[-1],             &[-1, -1, -1]),
1334         (&[ 1,  2,  3],     &[-1],             &[-1, -2, -2, 2]),
1335         (&[ 1,  2,  3,  4], &[-1],             &[-1, -2, -2, -2, 3]),
1336         (&[-1],             &[-1],             &[ 1, -2]),
1337         (&[-1, -1],         &[-1],             &[ 1, -1, -2]),
1338         (&[-1, -1, -1],     &[-1],             &[ 1, -1, -1, -2]),
1339         (&[-1, -1, -1, -1], &[-1],             &[ 1, -1, -1, -1, -2]),
1340         (&[-1/2 + 1],       &[ 2],             &[ 0,  1]),
1341         (&[0, -1/2 + 1],    &[ 2],             &[ 0,  0,  1]),
1342         (&[ 1,  2],         &[ 1,  2,  3],     &[1, 4,  7,  6]),
1343         (&[-1, -1],         &[-1, -1, -1],     &[1, 0, -1, -2, -1]),
1344         (&[-1, -1, -1],     &[-1, -1, -1, -1], &[1, 0,  0, -1, -2, -1, -1]),
1345         (&[ 0,  0,  1],     &[ 1,  2,  3],     &[0, 0,  1,  2,  3]),
1346         (&[ 0,  0,  1],     &[ 0,  0,  0,  1], &[0, 0,  0,  0,  0,  1])
1347     ];
1348
1349     static div_rem_quadruples: &'static [(&'static [BigDigit],
1350                                            &'static [BigDigit],
1351                                            &'static [BigDigit],
1352                                            &'static [BigDigit])]
1353         = &[
1354             (&[ 1],        &[ 2], &[],               &[1]),
1355             (&[ 1,  1],    &[ 2], &[-1/2+1],         &[1]),
1356             (&[ 1,  1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
1357             (&[ 0,  1],    &[-1], &[1],              &[1]),
1358             (&[-1, -1],    &[-2], &[2, 1],           &[3])
1359         ];
1360
1361     #[test]
1362     fn test_mul() {
1363         for mul_triples.each |elm| {
1364             let (aVec, bVec, cVec) = *elm;
1365             let a = BigUint::from_slice(aVec);
1366             let b = BigUint::from_slice(bVec);
1367             let c = BigUint::from_slice(cVec);
1368
1369             assert!(a * b == c);
1370             assert!(b * a == c);
1371         }
1372
1373         for div_rem_quadruples.each |elm| {
1374             let (aVec, bVec, cVec, dVec) = *elm;
1375             let a = BigUint::from_slice(aVec);
1376             let b = BigUint::from_slice(bVec);
1377             let c = BigUint::from_slice(cVec);
1378             let d = BigUint::from_slice(dVec);
1379
1380             assert!(a == b * c + d);
1381             assert!(a == c * b + d);
1382         }
1383     }
1384
1385     #[test]
1386     fn test_div_rem() {
1387         for mul_triples.each |elm| {
1388             let (aVec, bVec, cVec) = *elm;
1389             let a = BigUint::from_slice(aVec);
1390             let b = BigUint::from_slice(bVec);
1391             let c = BigUint::from_slice(cVec);
1392
1393             if !a.is_zero() {
1394                 assert!(c.div_rem(&a) == (b.clone(), Zero::zero()));
1395             }
1396             if !b.is_zero() {
1397                 assert!(c.div_rem(&b) == (a.clone(), Zero::zero()));
1398             }
1399         }
1400
1401         for div_rem_quadruples.each |elm| {
1402             let (aVec, bVec, cVec, dVec) = *elm;
1403             let a = BigUint::from_slice(aVec);
1404             let b = BigUint::from_slice(bVec);
1405             let c = BigUint::from_slice(cVec);
1406             let d = BigUint::from_slice(dVec);
1407
1408             if !b.is_zero() { assert!(a.div_rem(&b) == (c, d)); }
1409         }
1410     }
1411
1412     #[test]
1413     fn test_gcd() {
1414         fn check(a: uint, b: uint, c: uint) {
1415             let big_a = BigUint::from_uint(a);
1416             let big_b = BigUint::from_uint(b);
1417             let big_c = BigUint::from_uint(c);
1418
1419             assert_eq!(big_a.gcd(&big_b), big_c);
1420         }
1421
1422         check(10, 2, 2);
1423         check(10, 3, 1);
1424         check(0, 3, 3);
1425         check(3, 3, 3);
1426         check(56, 42, 14);
1427     }
1428
1429     #[test]
1430     fn test_lcm() {
1431         fn check(a: uint, b: uint, c: uint) {
1432             let big_a = BigUint::from_uint(a);
1433             let big_b = BigUint::from_uint(b);
1434             let big_c = BigUint::from_uint(c);
1435
1436             assert_eq!(big_a.lcm(&big_b), big_c);
1437         }
1438
1439         check(1, 0, 0);
1440         check(0, 1, 0);
1441         check(1, 1, 1);
1442         check(8, 9, 72);
1443         check(11, 5, 55);
1444         check(99, 17, 1683);
1445     }
1446
1447     fn to_str_pairs() -> ~[ (BigUint, ~[(uint, ~str)]) ] {
1448         let bits = BigDigit::bits;
1449         ~[( Zero::zero(), ~[
1450             (2, ~"0"), (3, ~"0")
1451         ]), ( BigUint::from_slice([ 0xff ]), ~[
1452             (2,  ~"11111111"),
1453             (3,  ~"100110"),
1454             (4,  ~"3333"),
1455             (5,  ~"2010"),
1456             (6,  ~"1103"),
1457             (7,  ~"513"),
1458             (8,  ~"377"),
1459             (9,  ~"313"),
1460             (10, ~"255"),
1461             (11, ~"212"),
1462             (12, ~"193"),
1463             (13, ~"168"),
1464             (14, ~"143"),
1465             (15, ~"120"),
1466             (16, ~"ff")
1467         ]), ( BigUint::from_slice([ 0xfff ]), ~[
1468             (2,  ~"111111111111"),
1469             (4,  ~"333333"),
1470             (16, ~"fff")
1471         ]), ( BigUint::from_slice([ 1, 2 ]), ~[
1472             (2,
1473              ~"10" +
1474              str::from_chars(vec::from_elem(bits - 1, '0')) + "1"),
1475             (4,
1476              ~"2" +
1477              str::from_chars(vec::from_elem(bits / 2 - 1, '0')) + "1"),
1478             (10, match bits {
1479                 32 => ~"8589934593", 16 => ~"131073", _ => fail!()
1480             }),
1481             (16,
1482              ~"2" +
1483              str::from_chars(vec::from_elem(bits / 4 - 1, '0')) + "1")
1484         ]), ( BigUint::from_slice([ 1, 2, 3 ]), ~[
1485             (2,
1486              ~"11" +
1487              str::from_chars(vec::from_elem(bits - 2, '0')) + "10" +
1488              str::from_chars(vec::from_elem(bits - 1, '0')) + "1"),
1489             (4,
1490              ~"3" +
1491              str::from_chars(vec::from_elem(bits / 2 - 1, '0')) + "2" +
1492              str::from_chars(vec::from_elem(bits / 2 - 1, '0')) + "1"),
1493             (10, match bits {
1494                 32 => ~"55340232229718589441",
1495                 16 => ~"12885032961",
1496                 _ => fail!()
1497             }),
1498             (16, ~"3" +
1499              str::from_chars(vec::from_elem(bits / 4 - 1, '0')) + "2" +
1500              str::from_chars(vec::from_elem(bits / 4 - 1, '0')) + "1")
1501         ]) ]
1502     }
1503
1504     #[test]
1505     fn test_to_str_radix() {
1506         for to_str_pairs().each |num_pair| {
1507             let &(n, rs) = num_pair;
1508             for rs.each |str_pair| {
1509                 let &(radix, str) = str_pair;
1510                 assert!(n.to_str_radix(radix) == str);
1511             }
1512         }
1513     }
1514
1515     #[test]
1516     fn test_from_str_radix() {
1517         for to_str_pairs().each |num_pair| {
1518             let &(n, rs) = num_pair;
1519             for rs.each |str_pair| {
1520                 let &(radix, str) = str_pair;
1521                 assert_eq!(&n, &FromStrRadix::from_str_radix(str, radix).get());
1522             }
1523         }
1524
1525         assert_eq!(FromStrRadix::from_str_radix::<BigUint>(~"Z", 10), None);
1526         assert_eq!(FromStrRadix::from_str_radix::<BigUint>(~"_", 2), None);
1527         assert_eq!(FromStrRadix::from_str_radix::<BigUint>(~"-1", 10), None);
1528     }
1529
1530     #[test]
1531     fn test_factor() {
1532         fn factor(n: uint) -> BigUint {
1533             let mut f= One::one::<BigUint>();
1534             for uint::range(2, n + 1) |i| {
1535                 // FIXME(#6102): Assignment operator for BigInt causes ICE
1536                 // f *= BigUint::from_uint(i);
1537                 f = f * BigUint::from_uint(i);
1538             }
1539             return f;
1540         }
1541
1542         fn check(n: uint, s: &str) {
1543             let n = factor(n);
1544             let ans = match FromStrRadix::from_str_radix(s, 10) {
1545                 Some(x) => x, None => fail!()
1546             };
1547             assert!(n == ans);
1548         }
1549
1550         check(3, "6");
1551         check(10, "3628800");
1552         check(20, "2432902008176640000");
1553         check(30, "265252859812191058636308480000000");
1554     }
1555 }
1556
1557 #[cfg(test)]
1558 mod bigint_tests {
1559     use super::*;
1560     use core::cmp::{Less, Equal, Greater};
1561     use core::num::{IntConvertible, Zero, One, FromStrRadix};
1562
1563     #[test]
1564     fn test_from_biguint() {
1565         fn check(inp_s: Sign, inp_n: uint, ans_s: Sign, ans_n: uint) {
1566             let inp = BigInt::from_biguint(inp_s, BigUint::from_uint(inp_n));
1567             let ans = BigInt { sign: ans_s, data: BigUint::from_uint(ans_n)};
1568             assert!(inp == ans);
1569         }
1570         check(Plus, 1, Plus, 1);
1571         check(Plus, 0, Zero, 0);
1572         check(Minus, 1, Minus, 1);
1573         check(Zero, 1, Zero, 0);
1574     }
1575
1576     #[test]
1577     fn test_cmp() {
1578         let vs = [ &[2], &[1, 1], &[2, 1], &[1, 1, 1] ];
1579         let mut nums = vec::reversed(vs)
1580             .map(|s| BigInt::from_slice(Minus, *s));
1581         nums.push(Zero::zero());
1582         nums.push_all_move(vs.map(|s| BigInt::from_slice(Plus, *s)));
1583
1584         for nums.eachi |i, ni| {
1585             for vec::slice(nums, i, nums.len()).eachi |j0, nj| {
1586                 let j = i + j0;
1587                 if i == j {
1588                     assert_eq!(ni.cmp(nj), Equal);
1589                     assert_eq!(nj.cmp(ni), Equal);
1590                     assert!(ni == nj);
1591                     assert!(!(ni != nj));
1592                     assert!(ni <= nj);
1593                     assert!(ni >= nj);
1594                     assert!(!(ni < nj));
1595                     assert!(!(ni > nj));
1596                 } else {
1597                     assert_eq!(ni.cmp(nj), Less);
1598                     assert_eq!(nj.cmp(ni), Greater);
1599
1600                     assert!(!(ni == nj));
1601                     assert!(ni != nj);
1602
1603                     assert!(ni <= nj);
1604                     assert!(!(ni >= nj));
1605                     assert!(ni < nj);
1606                     assert!(!(ni > nj));
1607
1608                     assert!(!(nj <= ni));
1609                     assert!(nj >= ni);
1610                     assert!(!(nj < ni));
1611                     assert!(nj > ni);
1612                 }
1613             }
1614         }
1615     }
1616
1617     #[test]
1618     fn test_convert_int() {
1619         fn check(b: BigInt, i: int) {
1620             assert!(b == IntConvertible::from_int(i));
1621             assert!(b.to_int() == i);
1622         }
1623
1624         check(Zero::zero(), 0);
1625         check(One::one(), 1);
1626         check(BigInt::from_biguint(
1627             Plus, BigUint::from_uint(int::max_value as uint)
1628         ), int::max_value);
1629
1630         assert!(BigInt::from_biguint(
1631             Plus, BigUint::from_uint(int::max_value as uint + 1)
1632         ).to_int() == int::max_value);
1633         assert!(BigInt::from_biguint(
1634             Plus, BigUint::new(~[1, 2, 3])
1635         ).to_int() == int::max_value);
1636
1637         check(BigInt::from_biguint(
1638             Minus, BigUint::from_uint(-int::min_value as uint)
1639         ), int::min_value);
1640         assert!(BigInt::from_biguint(
1641             Minus, BigUint::from_uint(-int::min_value as uint + 1)
1642         ).to_int() == int::min_value);
1643         assert!(BigInt::from_biguint(
1644             Minus, BigUint::new(~[1, 2, 3])
1645         ).to_int() == int::min_value);
1646     }
1647
1648     #[test]
1649     fn test_convert_uint() {
1650         fn check(b: BigInt, u: uint) {
1651             assert!(b == BigInt::from_uint(u));
1652             assert!(b.to_uint() == u);
1653         }
1654
1655         check(Zero::zero(), 0);
1656         check(One::one(), 1);
1657
1658         check(
1659             BigInt::from_biguint(Plus, BigUint::from_uint(uint::max_value)),
1660             uint::max_value);
1661         assert!(BigInt::from_biguint(
1662             Plus, BigUint::new(~[1, 2, 3])
1663         ).to_uint() == uint::max_value);
1664
1665         assert!(BigInt::from_biguint(
1666             Minus, BigUint::from_uint(uint::max_value)
1667         ).to_uint() == 0);
1668         assert!(BigInt::from_biguint(
1669             Minus, BigUint::new(~[1, 2, 3])
1670         ).to_uint() == 0);
1671     }
1672
1673     static sum_triples: &'static [(&'static [BigDigit],
1674                                    &'static [BigDigit],
1675                                    &'static [BigDigit])] = &[
1676         (&[],          &[],       &[]),
1677         (&[],          &[ 1],     &[ 1]),
1678         (&[ 1],        &[ 1],     &[ 2]),
1679         (&[ 1],        &[ 1,  1], &[ 2,  1]),
1680         (&[ 1],        &[-1],     &[ 0,  1]),
1681         (&[ 1],        &[-1, -1], &[ 0,  0, 1]),
1682         (&[-1, -1],    &[-1, -1], &[-2, -1, 1]),
1683         (&[ 1,  1, 1], &[-1, -1], &[ 0,  1, 2]),
1684         (&[ 2,  2, 1], &[-1, -2], &[ 1,  1, 2])
1685     ];
1686
1687     #[test]
1688     fn test_add() {
1689         for sum_triples.each |elm| {
1690             let (aVec, bVec, cVec) = *elm;
1691             let a = BigInt::from_slice(Plus, aVec);
1692             let b = BigInt::from_slice(Plus, bVec);
1693             let c = BigInt::from_slice(Plus, cVec);
1694
1695             assert!(a + b == c);
1696             assert!(b + a == c);
1697             assert!(c + (-a) == b);
1698             assert!(c + (-b) == a);
1699             assert!(a + (-c) == (-b));
1700             assert!(b + (-c) == (-a));
1701             assert!((-a) + (-b) == (-c));
1702             assert!(a + (-a) == Zero::zero());
1703         }
1704     }
1705
1706     #[test]
1707     fn test_sub() {
1708         for sum_triples.each |elm| {
1709             let (aVec, bVec, cVec) = *elm;
1710             let a = BigInt::from_slice(Plus, aVec);
1711             let b = BigInt::from_slice(Plus, bVec);
1712             let c = BigInt::from_slice(Plus, cVec);
1713
1714             assert!(c - a == b);
1715             assert!(c - b == a);
1716             assert!((-b) - a == (-c));
1717             assert!((-a) - b == (-c));
1718             assert!(b - (-a) == c);
1719             assert!(a - (-b) == c);
1720             assert!((-c) - (-a) == (-b));
1721             assert!(a - a == Zero::zero());
1722         }
1723     }
1724
1725     static mul_triples: &'static [(&'static [BigDigit],
1726                                    &'static [BigDigit],
1727                                    &'static [BigDigit])] = &[
1728         (&[],               &[],               &[]),
1729         (&[],               &[ 1],             &[]),
1730         (&[ 2],             &[],               &[]),
1731         (&[ 1],             &[ 1],             &[1]),
1732         (&[ 2],             &[ 3],             &[ 6]),
1733         (&[ 1],             &[ 1,  1,  1],     &[1, 1,  1]),
1734         (&[ 1,  2,  3],     &[ 3],             &[ 3,  6,  9]),
1735         (&[ 1,  1,  1],     &[-1],             &[-1, -1, -1]),
1736         (&[ 1,  2,  3],     &[-1],             &[-1, -2, -2, 2]),
1737         (&[ 1,  2,  3,  4], &[-1],             &[-1, -2, -2, -2, 3]),
1738         (&[-1],             &[-1],             &[ 1, -2]),
1739         (&[-1, -1],         &[-1],             &[ 1, -1, -2]),
1740         (&[-1, -1, -1],     &[-1],             &[ 1, -1, -1, -2]),
1741         (&[-1, -1, -1, -1], &[-1],             &[ 1, -1, -1, -1, -2]),
1742         (&[-1/2 + 1],       &[ 2],             &[ 0,  1]),
1743         (&[0, -1/2 + 1],    &[ 2],             &[ 0,  0,  1]),
1744         (&[ 1,  2],         &[ 1,  2,  3],     &[1, 4,  7,  6]),
1745         (&[-1, -1],         &[-1, -1, -1],     &[1, 0, -1, -2, -1]),
1746         (&[-1, -1, -1],     &[-1, -1, -1, -1], &[1, 0,  0, -1, -2, -1, -1]),
1747         (&[ 0,  0,  1],     &[ 1,  2,  3],     &[0, 0,  1,  2,  3]),
1748         (&[ 0,  0,  1],     &[ 0,  0,  0,  1], &[0, 0,  0,  0,  0,  1])
1749     ];
1750
1751     static div_rem_quadruples: &'static [(&'static [BigDigit],
1752                                           &'static [BigDigit],
1753                                           &'static [BigDigit],
1754                                           &'static [BigDigit])]
1755         = &[
1756             (&[ 1],        &[ 2], &[],               &[1]),
1757             (&[ 1,  1],    &[ 2], &[-1/2+1],         &[1]),
1758             (&[ 1,  1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
1759             (&[ 0,  1],    &[-1], &[1],              &[1]),
1760             (&[-1, -1],    &[-2], &[2, 1],           &[3])
1761         ];
1762
1763     #[test]
1764     fn test_mul() {
1765         for mul_triples.each |elm| {
1766             let (aVec, bVec, cVec) = *elm;
1767             let a = BigInt::from_slice(Plus, aVec);
1768             let b = BigInt::from_slice(Plus, bVec);
1769             let c = BigInt::from_slice(Plus, cVec);
1770
1771             assert!(a * b == c);
1772             assert!(b * a == c);
1773
1774             assert!((-a) * b == -c);
1775             assert!((-b) * a == -c);
1776         }
1777
1778         for div_rem_quadruples.each |elm| {
1779             let (aVec, bVec, cVec, dVec) = *elm;
1780             let a = BigInt::from_slice(Plus, aVec);
1781             let b = BigInt::from_slice(Plus, bVec);
1782             let c = BigInt::from_slice(Plus, cVec);
1783             let d = BigInt::from_slice(Plus, dVec);
1784
1785             assert!(a == b * c + d);
1786             assert!(a == c * b + d);
1787         }
1788     }
1789
1790     #[test]
1791     fn test_div_mod_floor() {
1792         fn check_sub(a: &BigInt, b: &BigInt, ans_d: &BigInt, ans_m: &BigInt) {
1793             let (d, m) = a.div_mod_floor(b);
1794             if !m.is_zero() {
1795                 assert!(m.sign == b.sign);
1796             }
1797             assert!(m.abs() <= b.abs());
1798             assert!(*a == b * d + m);
1799             assert!(d == *ans_d);
1800             assert!(m == *ans_m);
1801         }
1802
1803         fn check(a: &BigInt, b: &BigInt, d: &BigInt, m: &BigInt) {
1804             if m.is_zero() {
1805                 check_sub(a, b, d, m);
1806                 check_sub(a, &b.neg(), &d.neg(), m);
1807                 check_sub(&a.neg(), b, &d.neg(), m);
1808                 check_sub(&a.neg(), &b.neg(), d, m);
1809             } else {
1810                 check_sub(a, b, d, m);
1811                 check_sub(a, &b.neg(), &(d.neg() - One::one()), &(m - *b));
1812                 check_sub(&a.neg(), b, &(d.neg() - One::one()), &(b - *m));
1813                 check_sub(&a.neg(), &b.neg(), d, &m.neg());
1814             }
1815         }
1816
1817         for mul_triples.each |elm| {
1818             let (aVec, bVec, cVec) = *elm;
1819             let a = BigInt::from_slice(Plus, aVec);
1820             let b = BigInt::from_slice(Plus, bVec);
1821             let c = BigInt::from_slice(Plus, cVec);
1822
1823             if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
1824             if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
1825         }
1826
1827         for div_rem_quadruples.each |elm| {
1828             let (aVec, bVec, cVec, dVec) = *elm;
1829             let a = BigInt::from_slice(Plus, aVec);
1830             let b = BigInt::from_slice(Plus, bVec);
1831             let c = BigInt::from_slice(Plus, cVec);
1832             let d = BigInt::from_slice(Plus, dVec);
1833
1834             if !b.is_zero() {
1835                 check(&a, &b, &c, &d);
1836             }
1837         }
1838     }
1839
1840
1841     #[test]
1842     fn test_div_rem() {
1843         fn check_sub(a: &BigInt, b: &BigInt, ans_q: &BigInt, ans_r: &BigInt) {
1844             let (q, r) = a.div_rem(b);
1845             if !r.is_zero() {
1846                 assert!(r.sign == a.sign);
1847             }
1848             assert!(r.abs() <= b.abs());
1849             assert!(*a == b * q + r);
1850             assert!(q == *ans_q);
1851             assert!(r == *ans_r);
1852         }
1853
1854         fn check(a: &BigInt, b: &BigInt, q: &BigInt, r: &BigInt) {
1855             check_sub(a, b, q, r);
1856             check_sub(a, &b.neg(), &q.neg(), r);
1857             check_sub(&a.neg(), b, &q.neg(), &r.neg());
1858             check_sub(&a.neg(), &b.neg(), q, &r.neg());
1859         }
1860         for mul_triples.each |elm| {
1861             let (aVec, bVec, cVec) = *elm;
1862             let a = BigInt::from_slice(Plus, aVec);
1863             let b = BigInt::from_slice(Plus, bVec);
1864             let c = BigInt::from_slice(Plus, cVec);
1865
1866             if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
1867             if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
1868         }
1869
1870         for div_rem_quadruples.each |elm| {
1871             let (aVec, bVec, cVec, dVec) = *elm;
1872             let a = BigInt::from_slice(Plus, aVec);
1873             let b = BigInt::from_slice(Plus, bVec);
1874             let c = BigInt::from_slice(Plus, cVec);
1875             let d = BigInt::from_slice(Plus, dVec);
1876
1877             if !b.is_zero() {
1878                 check(&a, &b, &c, &d);
1879             }
1880         }
1881     }
1882
1883     #[test]
1884     fn test_gcd() {
1885         fn check(a: int, b: int, c: int) {
1886             let big_a: BigInt = IntConvertible::from_int(a);
1887             let big_b: BigInt = IntConvertible::from_int(b);
1888             let big_c: BigInt = IntConvertible::from_int(c);
1889
1890             assert_eq!(big_a.gcd(&big_b), big_c);
1891         }
1892
1893         check(10, 2, 2);
1894         check(10, 3, 1);
1895         check(0, 3, 3);
1896         check(3, 3, 3);
1897         check(56, 42, 14);
1898         check(3, -3, 3);
1899         check(-6, 3, 3);
1900         check(-4, -2, 2);
1901     }
1902
1903     #[test]
1904     fn test_lcm() {
1905         fn check(a: int, b: int, c: int) {
1906             let big_a: BigInt = IntConvertible::from_int(a);
1907             let big_b: BigInt = IntConvertible::from_int(b);
1908             let big_c: BigInt = IntConvertible::from_int(c);
1909
1910             assert_eq!(big_a.lcm(&big_b), big_c);
1911         }
1912
1913         check(1, 0, 0);
1914         check(0, 1, 0);
1915         check(1, 1, 1);
1916         check(-1, 1, 1);
1917         check(1, -1, 1);
1918         check(-1, -1, 1);
1919         check(8, 9, 72);
1920         check(11, 5, 55);
1921     }
1922
1923     #[test]
1924     fn test_to_str_radix() {
1925         fn check(n: int, ans: &str) {
1926             assert!(ans == IntConvertible::from_int::<BigInt>(n).to_str_radix(10));
1927         }
1928         check(10, "10");
1929         check(1, "1");
1930         check(0, "0");
1931         check(-1, "-1");
1932         check(-10, "-10");
1933     }
1934
1935
1936     #[test]
1937     fn test_from_str_radix() {
1938         fn check(s: &str, ans: Option<int>) {
1939             let ans = ans.map(|&n| IntConvertible::from_int::<BigInt>(n));
1940             assert!(FromStrRadix::from_str_radix(s, 10) == ans);
1941         }
1942         check("10", Some(10));
1943         check("1", Some(1));
1944         check("0", Some(0));
1945         check("-1", Some(-1));
1946         check("-10", Some(-10));
1947         check("Z", None);
1948         check("_", None);
1949     }
1950
1951     #[test]
1952     fn test_neg() {
1953         assert!(-BigInt::new(Plus,  ~[1, 1, 1]) ==
1954             BigInt::new(Minus, ~[1, 1, 1]));
1955         assert!(-BigInt::new(Minus, ~[1, 1, 1]) ==
1956             BigInt::new(Plus,  ~[1, 1, 1]));
1957         assert!(-Zero::zero::<BigInt>() == Zero::zero::<BigInt>());
1958     }
1959 }
1960