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 #[deriving(Clone)]
  84 pub struct BigUint {
  85     priv data: ~[BigDigit]
  86 }
  87
  88 impl Eq for BigUint {
  89     #[inline(always)]
  90     fn eq(&self, other: &BigUint) -> bool { self.equals(other) }
  91     #[inline(always)]
  92     fn ne(&self, other: &BigUint) -> bool { !self.equals(other) }
  93 }
  94
  95 impl TotalEq for BigUint {
  96     #[inline(always)]
  97     fn equals(&self, other: &BigUint) -> bool {
  98         match self.cmp(other) { Equal => true, _ => false }
  99     }
 100 }
 101
 102 impl Ord for BigUint {
 103     #[inline(always)]
 104     fn lt(&self, other: &BigUint) -> bool {
 105         match self.cmp(other) { Less => true, _ => false}
 106     }
 107     #[inline(always)]
 108     fn le(&self, other: &BigUint) -> bool {
 109         match self.cmp(other) { Less | Equal => true, _ => false }
 110     }
 111     #[inline(always)]
 112     fn ge(&self, other: &BigUint) -> bool {
 113         match self.cmp(other) { Greater | Equal => true, _ => false }
 114     }
 115     #[inline(always)]
 116     fn gt(&self, other: &BigUint) -> bool {
 117         match self.cmp(other) { Greater => true, _ => false }
 118     }
 119 }
 120
 121 impl TotalOrd for BigUint {
 122     #[inline(always)]
 123     fn cmp(&self, other: &BigUint) -> Ordering {
 124         let s_len = self.data.len(), o_len = other.data.len();
 125         if s_len < o_len { return Less; }
 126         if s_len > o_len { return Greater;  }
 127
 128         for self.data.eachi_reverse |i, elm| {
 129             match (*elm, other.data[i]) {
 130                 (l, r) if l < r => return Less,
 131                 (l, r) if l > r => return Greater,
 132                 _               => loop
 133             };
 134         }
 135         return Equal;
 136     }
 137 }
 138
 139 impl ToStr for BigUint {
 140     #[inline(always)]
 141     fn to_str(&self) -> ~str { self.to_str_radix(10) }
 142 }
 143
 144 impl from_str::FromStr for BigUint {
 145     #[inline(always)]
 146     fn from_str(s: &str) -> Option<BigUint> {
 147         FromStrRadix::from_str_radix(s, 10)
 148     }
 149 }
 150
 151 impl Shl<uint, BigUint> for BigUint {
 152     #[inline(always)]
 153     fn shl(&self, rhs: &uint) -> BigUint {
 154         let n_unit = *rhs / BigDigit::bits;
 155         let n_bits = *rhs % BigDigit::bits;
 156         return self.shl_unit(n_unit).shl_bits(n_bits);
 157     }
 158 }
 159
 160 impl Shr<uint, BigUint> for BigUint {
 161     #[inline(always)]
 162     fn shr(&self, rhs: &uint) -> BigUint {
 163         let n_unit = *rhs / BigDigit::bits;
 164         let n_bits = *rhs % BigDigit::bits;
 165         return self.shr_unit(n_unit).shr_bits(n_bits);
 166     }
 167 }
 168
 169 impl Zero for BigUint {
 170     #[inline(always)]
 171     fn zero() -> BigUint { BigUint::new(~[]) }
 172
 173     #[inline(always)]
 174     fn is_zero(&self) -> bool { self.data.is_empty() }
 175 }
 176
 177 impl One for BigUint {
 178     #[inline(always)]
 179     fn one() -> BigUint { BigUint::new(~[1]) }
 180 }
 181
 182 impl Unsigned for BigUint {}
 183
 184 impl Add<BigUint, BigUint> for BigUint {
 185     #[inline(always)]
 186     fn add(&self, other: &BigUint) -> BigUint {
 187         let new_len = uint::max(self.data.len(), other.data.len());
 188
 189         let mut carry = 0;
 190         let sum = do vec::from_fn(new_len) |i| {
 191             let ai = if i < self.data.len()  { self.data[i]  } else { 0 };
 192             let bi = if i < other.data.len() { other.data[i] } else { 0 };
 193             let (hi, lo) = BigDigit::from_uint(
 194                 (ai as uint) + (bi as uint) + (carry as uint)
 195             );
 196             carry = hi;
 197             lo
 198         };
 199         if carry == 0 { return BigUint::new(sum) };
 200         return BigUint::new(sum + [carry]);
 201     }
 202 }
 203
 204 impl Sub<BigUint, BigUint> for BigUint {
 205     #[inline(always)]
 206     fn sub(&self, other: &BigUint) -> BigUint {
 207         let new_len = uint::max(self.data.len(), other.data.len());
 208
 209         let mut borrow = 0;
 210         let diff = do vec::from_fn(new_len) |i| {
 211             let ai = if i < self.data.len()  { self.data[i]  } else { 0 };
 212             let bi = if i < other.data.len() { other.data[i] } else { 0 };
 213             let (hi, lo) = BigDigit::from_uint(
 214                 (BigDigit::base) +
 215                 (ai as uint) - (bi as uint) - (borrow as uint)
 216             );
 217             /*
 218             hi * (base) + lo == 1*(base) + ai - bi - borrow
 219             => ai - bi - borrow < 0 <=> hi == 0
 220             */
 221             borrow = if hi == 0 { 1 } else { 0 };
 222             lo
 223         };
 224
 225         assert!(borrow == 0);     // <=> assert!((self >= other));
 226         return BigUint::new(diff);
 227     }
 228 }
 229
 230 impl Mul<BigUint, BigUint> for BigUint {
 231     fn mul(&self, other: &BigUint) -> BigUint {
 232         if self.is_zero() || other.is_zero() { return Zero::zero(); }
 233
 234         let s_len = self.data.len(), o_len = other.data.len();
 235         if s_len == 1 { return mul_digit(other, self.data[0]);  }
 236         if o_len == 1 { return mul_digit(self,  other.data[0]); }
 237
 238         // Using Karatsuba multiplication
 239         // (a1 * base + a0) * (b1 * base + b0)
 240         // = a1*b1 * base^2 +
 241         //   (a1*b1 + a0*b0 - (a1-b0)*(b1-a0)) * base +
 242         //   a0*b0
 243         let half_len = uint::max(s_len, o_len) / 2;
 244         let (sHi, sLo) = cut_at(self,  half_len);
 245         let (oHi, oLo) = cut_at(other, half_len);
 246
 247         let ll = sLo * oLo;
 248         let hh = sHi * oHi;
 249         let mm = {
 250             let (s1, n1) = sub_sign(sHi, sLo);
 251             let (s2, n2) = sub_sign(oHi, oLo);
 252             match (s1, s2) {
 253                 (Equal, _) | (_, Equal) => hh + ll,
 254                 (Less, Greater) | (Greater, Less) => hh + ll + (n1 * n2),
 255                 (Less, Less) | (Greater, Greater) => hh + ll - (n1 * n2)
 256             }
 257         };
 258
 259         return ll + mm.shl_unit(half_len) + hh.shl_unit(half_len * 2);
 260
 261         #[inline(always)]
 262         fn mul_digit(a: &BigUint, n: BigDigit) -> BigUint {
 263             if n == 0 { return Zero::zero(); }
 264             if n == 1 { return copy *a; }
 265
 266             let mut carry = 0;
 267             let prod = do vec::map(a.data) |ai| {
 268                 let (hi, lo) = BigDigit::from_uint(
 269                     (*ai as uint) * (n as uint) + (carry as uint)
 270                 );
 271                 carry = hi;
 272                 lo
 273             };
 274             if carry == 0 { return BigUint::new(prod) };
 275             return BigUint::new(prod + [carry]);
 276         }
 277
 278         #[inline(always)]
 279         fn cut_at(a: &BigUint, n: uint) -> (BigUint, BigUint) {
 280             let mid = uint::min(a.data.len(), n);
 281             return (BigUint::from_slice(vec::slice(a.data, mid,
 282                                                    a.data.len())),
 283                     BigUint::from_slice(vec::slice(a.data, 0, mid)));
 284         }
 285
 286         #[inline(always)]
 287         fn sub_sign(a: BigUint, b: BigUint) -> (Ordering, BigUint) {
 288             match a.cmp(&b) {
 289                 Less    => (Less,    b - a),
 290                 Greater => (Greater, a - b),
 291                 _       => (Equal,   Zero::zero())
 292             }
 293         }
 294     }
 295 }
 296
 297 impl Div<BigUint, BigUint> for BigUint {
 298     #[inline(always)]
 299     fn div(&self, other: &BigUint) -> BigUint {
 300         let (q, _) = self.div_rem(other);
 301         return q;
 302     }
 303 }
 304
 305 impl Rem<BigUint, BigUint> for BigUint {
 306     #[inline(always)]
 307     fn rem(&self, other: &BigUint) -> BigUint {
 308         let (_, r) = self.div_rem(other);
 309         return r;
 310     }
 311 }
 312
 313 impl Neg<BigUint> for BigUint {
 314     #[inline(always)]
 315     fn neg(&self) -> BigUint { fail!() }
 316 }
 317
 318 impl Integer for BigUint {
 319     #[inline(always)]
 320     fn div_rem(&self, other: &BigUint) -> (BigUint, BigUint) {
 321         self.div_mod_floor(other)
 322     }
 323
 324     #[inline(always)]
 325     fn div_floor(&self, other: &BigUint) -> BigUint {
 326         let (d, _) = self.div_mod_floor(other);
 327         return d;
 328     }
 329
 330     #[inline(always)]
 331     fn mod_floor(&self, other: &BigUint) -> BigUint {
 332         let (_, m) = self.div_mod_floor(other);
 333         return m;
 334     }
 335
 336     #[inline(always)]
 337     fn div_mod_floor(&self, other: &BigUint) -> (BigUint, BigUint) {
 338         if other.is_zero() { fail!() }
 339         if self.is_zero() { return (Zero::zero(), Zero::zero()); }
 340         if *other == One::one() { return (copy *self, Zero::zero()); }
 341
 342         match self.cmp(other) {
 343             Less    => return (Zero::zero(), copy *self),
 344             Equal   => return (One::one(), Zero::zero()),
 345             Greater => {} // Do nothing
 346         }
 347
 348         let mut shift = 0;
 349         let mut n = *other.data.last();
 350         while n < (1 << BigDigit::bits - 2) {
 351             n <<= 1;
 352             shift += 1;
 353         }
 354         assert!(shift < BigDigit::bits);
 355         let (d, m) = div_mod_floor_inner(self << shift, other << shift);
 356         return (d, m >> shift);
 357
 358         #[inline(always)]
 359         fn div_mod_floor_inner(a: BigUint, b: BigUint) -> (BigUint, BigUint) {
 360             let mut m = a;
 361             let mut d = Zero::zero::<BigUint>();
 362             let mut n = 1;
 363             while m >= b {
 364                 let mut (d0, d_unit, b_unit) = div_estimate(&m, &b, n);
 365                 let mut prod = b * d0;
 366                 while prod > m {
 367                     // FIXME(#6050): overloaded operators force moves with generic types
 368                     // d0 -= d_unit
 369                     d0   = d0 - d_unit;
 370                     // FIXME(#6050): overloaded operators force moves with generic types
 371                     // prod = prod - b_unit;
 372                     prod = prod - b_unit
 373                 }
 374                 if d0.is_zero() {
 375                     n = 2;
 376                     loop;
 377                 }
 378                 n = 1;
 379                 // FIXME(#6102): Assignment operator for BigInt causes ICE
 380                 // d += d0;
 381                 d = d + d0;
 382                 // FIXME(#6102): Assignment operator for BigInt causes ICE
 383                 // m -= prod;
 384                 m = m - prod;
 385             }
 386             return (d, m);
 387         }
 388
 389         #[inline(always)]
 390         fn div_estimate(a: &BigUint, b: &BigUint, n: uint)
 391             -> (BigUint, BigUint, BigUint) {
 392             if a.data.len() < n {
 393                 return (Zero::zero(), Zero::zero(), copy *a);
 394             }
 395
 396             let an = vec::slice(a.data, a.data.len() - n, a.data.len());
 397             let bn = *b.data.last();
 398             let mut d = ~[];
 399             let mut carry = 0;
 400             for an.each_reverse |elt| {
 401                 let ai = BigDigit::to_uint(carry, *elt);
 402                 let di = ai / (bn as uint);
 403                 assert!(di < BigDigit::base);
 404                 carry = (ai % (bn as uint)) as BigDigit;
 405                 d = ~[di as BigDigit] + d;
 406             }
 407
 408             let shift = (a.data.len() - an.len()) - (b.data.len() - 1);
 409             if shift == 0 {
 410                 return (BigUint::new(d), One::one(), copy *b);
 411             }
 412             return (BigUint::from_slice(d).shl_unit(shift),
 413                     One::one::<BigUint>().shl_unit(shift),
 414                     b.shl_unit(shift));
 415         }
 416     }
 417
 418     /**
 419      * Calculates the Greatest Common Divisor (GCD) of the number and `other`
 420      *
 421      * The result is always positive
 422      */
 423     #[inline(always)]
 424     fn gcd(&self, other: &BigUint) -> BigUint {
 425         // Use Euclid's algorithm
 426         let mut m = copy *self, n = copy *other;
 427         while !m.is_zero() {
 428             let temp = m;
 429             m = n % temp;
 430             n = temp;
 431         }
 432         return n;
 433     }
 434
 435     /**
 436      * Calculates the Lowest Common Multiple (LCM) of the number and `other`
 437      */
 438     #[inline(always)]
 439     fn lcm(&self, other: &BigUint) -> BigUint { ((*self * *other) / self.gcd(other)) }
 440
 441     /// Returns `true` if the number can be divided by `other` without leaving a remainder
 442     #[inline(always)]
 443     fn is_multiple_of(&self, other: &BigUint) -> bool { (*self % *other).is_zero() }
 444
 445     /// Returns `true` if the number is divisible by `2`
 446     #[inline(always)]
 447     fn is_even(&self) -> bool {
 448         // Considering only the last digit.
 449         if self.data.is_empty() {
 450             true
 451         } else {
 452             self.data.last().is_even()
 453         }
 454     }
 455
 456     /// Returns `true` if the number is not divisible by `2`
 457     #[inline(always)]
 458     fn is_odd(&self) -> bool { !self.is_even() }
 459 }
 460
 461 impl IntConvertible for BigUint {
 462     #[inline(always)]
 463     fn to_int(&self) -> int {
 464         uint::min(self.to_uint(), int::max_value as uint) as int
 465     }
 466
 467     #[inline(always)]
 468     fn from_int(n: int) -> BigUint {
 469         if (n < 0) { Zero::zero() } else { BigUint::from_uint(n as uint) }
 470     }
 471 }
 472
 473 impl ToStrRadix for BigUint {
 474     #[inline(always)]
 475     fn to_str_radix(&self, radix: uint) -> ~str {
 476         assert!(1 < radix && radix <= 16);
 477         let (base, max_len) = get_radix_base(radix);
 478         if base == BigDigit::base {
 479             return fill_concat(self.data, radix, max_len)
 480         }
 481         return fill_concat(convert_base(copy *self, base), radix, max_len);
 482
 483         #[inline(always)]
 484         fn convert_base(n: BigUint, base: uint) -> ~[BigDigit] {
 485             let divider    = BigUint::from_uint(base);
 486             let mut result = ~[];
 487             let mut m      = n;
 488             while m > divider {
 489                 let (d, m0) = m.div_mod_floor(&divider);
 490                 result += [m0.to_uint() as BigDigit];
 491                 m = d;
 492             }
 493             if !m.is_zero() {
 494                 result += [m.to_uint() as BigDigit];
 495             }
 496             return result;
 497         }
 498
 499         #[inline(always)]
 500         fn fill_concat(v: &[BigDigit], radix: uint, l: uint) -> ~str {
 501             if v.is_empty() { return ~"0" }
 502             let s = str::concat(vec::reversed(v).map(|n| {
 503                 let s = uint::to_str_radix(*n as uint, radix);
 504                 str::from_chars(vec::from_elem(l - s.len(), '0')) + s
 505             }));
 506             str::trim_left_chars(s, ['0']).to_owned()
 507         }
 508     }
 509 }
 510
 511 impl FromStrRadix for BigUint {
 512     /// Creates and initializes an BigUint.
 513     #[inline(always)]
 514     pub fn from_str_radix(s: &str, radix: uint)
 515         -> Option<BigUint> {
 516         BigUint::parse_bytes(str::to_bytes(s), radix)
 517     }
 518 }
 519
 520 impl BigUint {
 521     /// Creates and initializes an BigUint.
 522     #[inline(always)]
 523     pub fn new(v: ~[BigDigit]) -> BigUint {
 524         // omit trailing zeros
 525         let new_len = v.rposition(|n| *n != 0).map_default(0, |p| *p + 1);
 526
 527         if new_len == v.len() { return BigUint { data: v }; }
 528         let mut v = v;
 529         v.truncate(new_len);
 530         return BigUint { data: v };
 531     }
 532
 533     /// Creates and initializes an BigUint.
 534     #[inline(always)]
 535     pub fn from_uint(n: uint) -> BigUint {
 536         match BigDigit::from_uint(n) {
 537             (0,  0)  => Zero::zero(),
 538             (0,  n0) => BigUint::new(~[n0]),
 539             (n1, n0) => BigUint::new(~[n0, n1])
 540         }
 541     }
 542
 543     /// Creates and initializes an BigUint.
 544     #[inline(always)]
 545     pub fn from_slice(slice: &[BigDigit]) -> BigUint {
 546         return BigUint::new(vec::from_slice(slice));
 547     }
 548
 549     /// Creates and initializes an BigUint.
 550     #[inline(always)]
 551     pub fn parse_bytes(buf: &[u8], radix: uint)
 552         -> Option<BigUint> {
 553         let (base, unit_len) = get_radix_base(radix);
 554         let base_num: BigUint = BigUint::from_uint(base);
 555
 556         let mut end             = buf.len();
 557         let mut n: BigUint      = Zero::zero();
 558         let mut power: BigUint  = One::one();
 559         loop {
 560             let start = uint::max(end, unit_len) - unit_len;
 561             match uint::parse_bytes(vec::slice(buf, start, end), radix) {
 562                 // FIXME(#6102): Assignment operator for BigInt causes ICE
 563                 // Some(d) => n += BigUint::from_uint(d) * power,
 564                 Some(d) => n = n + BigUint::from_uint(d) * power,
 565                 None    => return None
 566             }
 567             if end <= unit_len {
 568                 return Some(n);
 569             }
 570             end -= unit_len;
 571             // FIXME(#6050): overloaded operators force moves with generic types
 572             // power *= base_num;
 573             power = power * base_num;
 574         }
 575     }
 576
 577     #[inline(always)]
 578     pub fn to_uint(&self) -> uint {
 579         match self.data.len() {
 580             0 => 0,
 581             1 => self.data[0] as uint,
 582             2 => BigDigit::to_uint(self.data[1], self.data[0]),
 583             _ => uint::max_value
 584         }
 585     }
 586
 587     #[inline(always)]
 588     priv fn shl_unit(&self, n_unit: uint) -> BigUint {
 589         if n_unit == 0 || self.is_zero() { return copy *self; }
 590
 591         return BigUint::new(vec::from_elem(n_unit, 0) + self.data);
 592     }
 593
 594     #[inline(always)]
 595     priv fn shl_bits(&self, n_bits: uint) -> BigUint {
 596         if n_bits == 0 || self.is_zero() { return copy *self; }
 597
 598         let mut carry = 0;
 599         let shifted = do vec::map(self.data) |elem| {
 600             let (hi, lo) = BigDigit::from_uint(
 601                 (*elem as uint) << n_bits | (carry as uint)
 602             );
 603             carry = hi;
 604             lo
 605         };
 606         if carry == 0 { return BigUint::new(shifted); }
 607         return BigUint::new(shifted + [carry]);
 608     }
 609
 610     #[inline(always)]
 611     priv fn shr_unit(&self, n_unit: uint) -> BigUint {
 612         if n_unit == 0 { return copy *self; }
 613         if self.data.len() < n_unit { return Zero::zero(); }
 614         return BigUint::from_slice(
 615             vec::slice(self.data, n_unit, self.data.len())
 616         );
 617     }
 618
 619     #[inline(always)]
 620     priv fn shr_bits(&self, n_bits: uint) -> BigUint {
 621         if n_bits == 0 || self.data.is_empty() { return copy *self; }
 622
 623         let mut borrow = 0;
 624         let mut shifted = ~[];
 625         for self.data.each_reverse |elem| {
 626             shifted = ~[(*elem >> n_bits) | borrow] + shifted;
 627             borrow = *elem << (BigDigit::bits - n_bits);
 628         }
 629         return BigUint::new(shifted);
 630     }
 631 }
 632
 633 #[cfg(target_arch = "x86_64")]
 634 #[inline(always)]
 635 priv fn get_radix_base(radix: uint) -> (uint, uint) {
 636     assert!(1 < radix && radix <= 16);
 637     match radix {
 638         2  => (4294967296, 32),
 639         3  => (3486784401, 20),
 640         4  => (4294967296, 16),
 641         5  => (1220703125, 13),
 642         6  => (2176782336, 12),
 643         7  => (1977326743, 11),
 644         8  => (1073741824, 10),
 645         9  => (3486784401, 10),
 646         10 => (1000000000, 9),
 647         11 => (2357947691, 9),
 648         12 => (429981696,  8),
 649         13 => (815730721,  8),
 650         14 => (1475789056, 8),
 651         15 => (2562890625, 8),
 652         16 => (4294967296, 8),
 653         _  => fail!()
 654     }
 655 }
 656
 657 #[cfg(target_arch = "arm")]
 658 #[cfg(target_arch = "x86")]
 659 #[cfg(target_arch = "mips")]
 660 #[inline(always)]
 661 priv fn get_radix_base(radix: uint) -> (uint, uint) {
 662     assert!(1 < radix && radix <= 16);
 663     match radix {
 664         2  => (65536, 16),
 665         3  => (59049, 10),
 666         4  => (65536, 8),
 667         5  => (15625, 6),
 668         6  => (46656, 6),
 669         7  => (16807, 5),
 670         8  => (32768, 5),
 671         9  => (59049, 5),
 672         10 => (10000, 4),
 673         11 => (14641, 4),
 674         12 => (20736, 4),
 675         13 => (28561, 4),
 676         14 => (38416, 4),
 677         15 => (50625, 4),
 678         16 => (65536, 4),
 679         _  => fail!()
 680     }
 681 }
 682
 683 /// A Sign is a BigInt's composing element.
 684 #[deriving(Eq, Clone)]
 685 pub enum Sign { Minus, Zero, Plus }
 686
 687 impl Ord for Sign {
 688     #[inline(always)]
 689     fn lt(&self, other: &Sign) -> bool {
 690         match self.cmp(other) { Less => true, _ => false}
 691     }
 692     #[inline(always)]
 693     fn le(&self, other: &Sign) -> bool {
 694         match self.cmp(other) { Less | Equal => true, _ => false }
 695     }
 696     #[inline(always)]
 697     fn ge(&self, other: &Sign) -> bool {
 698         match self.cmp(other) { Greater | Equal => true, _ => false }
 699     }
 700     #[inline(always)]
 701     fn gt(&self, other: &Sign) -> bool {
 702         match self.cmp(other) { Greater => true, _ => false }
 703     }
 704 }
 705
 706 impl TotalOrd for Sign {
 707     #[inline(always)]
 708     fn cmp(&self, other: &Sign) -> Ordering {
 709         match (*self, *other) {
 710           (Minus, Minus) | (Zero,  Zero) | (Plus, Plus) => Equal,
 711           (Minus, Zero)  | (Minus, Plus) | (Zero, Plus) => Less,
 712           _                                             => Greater
 713         }
 714     }
 715 }
 716
 717 impl Neg<Sign> for Sign {
 718     /// Negate Sign value.
 719     #[inline(always)]
 720     fn neg(&self) -> Sign {
 721         match *self {
 722           Minus => Plus,
 723           Zero  => Zero,
 724           Plus  => Minus
 725         }
 726     }
 727 }
 728
 729 /// A big signed integer type.
 730 #[deriving(Clone)]
 731 pub struct BigInt {
 732     priv sign: Sign,
 733     priv data: BigUint
 734 }
 735
 736 impl Eq for BigInt {
 737     #[inline(always)]
 738     fn eq(&self, other: &BigInt) -> bool { self.equals(other) }
 739     #[inline(always)]
 740     fn ne(&self, other: &BigInt) -> bool { !self.equals(other) }
 741 }
 742
 743 impl TotalEq for BigInt {
 744     #[inline(always)]
 745     fn equals(&self, other: &BigInt) -> bool {
 746         match self.cmp(other) { Equal => true, _ => false }
 747     }
 748 }
 749
 750 impl Ord for BigInt {
 751     #[inline(always)]
 752     fn lt(&self, other: &BigInt) -> bool {
 753         match self.cmp(other) { Less => true, _ => false}
 754     }
 755     #[inline(always)]
 756     fn le(&self, other: &BigInt) -> bool {
 757         match self.cmp(other) { Less | Equal => true, _ => false }
 758     }
 759     #[inline(always)]
 760     fn ge(&self, other: &BigInt) -> bool {
 761         match self.cmp(other) { Greater | Equal => true, _ => false }
 762     }
 763     #[inline(always)]
 764     fn gt(&self, other: &BigInt) -> bool {
 765         match self.cmp(other) { Greater => true, _ => false }
 766     }
 767 }
 768
 769 impl TotalOrd for BigInt {
 770     #[inline(always)]
 771     fn cmp(&self, other: &BigInt) -> Ordering {
 772         let scmp = self.sign.cmp(&other.sign);
 773         if scmp != Equal { return scmp; }
 774
 775         match self.sign {
 776             Zero  => Equal,
 777             Plus  => self.data.cmp(&other.data),
 778             Minus => other.data.cmp(&self.data),
 779         }
 780     }
 781 }
 782
 783 impl ToStr for BigInt {
 784     #[inline(always)]
 785     fn to_str(&self) -> ~str { self.to_str_radix(10) }
 786 }
 787
 788 impl from_str::FromStr for BigInt {
 789     #[inline(always)]
 790     fn from_str(s: &str) -> Option<BigInt> {
 791         FromStrRadix::from_str_radix(s, 10)
 792     }
 793 }
 794
 795 impl Shl<uint, BigInt> for BigInt {
 796     #[inline(always)]
 797     fn shl(&self, rhs: &uint) -> BigInt {
 798         BigInt::from_biguint(self.sign, self.data << *rhs)
 799     }
 800 }
 801
 802 impl Shr<uint, BigInt> for BigInt {
 803     #[inline(always)]
 804     fn shr(&self, rhs: &uint) -> BigInt {
 805         BigInt::from_biguint(self.sign, self.data >> *rhs)
 806     }
 807 }
 808
 809 impl Zero for BigInt {
 810     #[inline(always)]
 811     fn zero() -> BigInt {
 812         BigInt::from_biguint(Zero, Zero::zero())
 813     }
 814
 815     #[inline(always)]
 816     fn is_zero(&self) -> bool { self.sign == Zero }
 817 }
 818
 819 impl One for BigInt {
 820     #[inline(always)]
 821     fn one() -> BigInt {
 822         BigInt::from_biguint(Plus, One::one())
 823     }
 824 }
 825
 826 impl Signed for BigInt {
 827     #[inline(always)]
 828     fn abs(&self) -> BigInt {
 829         match self.sign {
 830             Plus | Zero => self.clone(),
 831             Minus => BigInt::from_biguint(Plus, self.data.clone())
 832         }
 833     }
 834
 835     #[inline(always)]
 836     fn signum(&self) -> BigInt {
 837         match self.sign {
 838             Plus  => BigInt::from_biguint(Plus, One::one()),
 839             Minus => BigInt::from_biguint(Minus, One::one()),
 840             Zero  => Zero::zero(),
 841         }
 842     }
 843
 844     #[inline(always)]
 845     fn is_positive(&self) -> bool { self.sign == Plus }
 846
 847     #[inline(always)]
 848     fn is_negative(&self) -> bool { self.sign == Minus }
 849 }
 850
 851 impl Add<BigInt, BigInt> for BigInt {
 852     #[inline(always)]
 853     fn add(&self, other: &BigInt) -> BigInt {
 854         match (self.sign, other.sign) {
 855             (Zero, _)      => other.clone(),
 856             (_,    Zero)   => self.clone(),
 857             (Plus, Plus)   => BigInt::from_biguint(Plus,
 858                                                    self.data + other.data),
 859             (Plus, Minus)  => self - (-*other),
 860             (Minus, Plus)  => other - (-*self),
 861             (Minus, Minus) => -((-self) + (-*other))
 862         }
 863     }
 864 }
 865
 866 impl Sub<BigInt, BigInt> for BigInt {
 867     #[inline(always)]
 868     fn sub(&self, other: &BigInt) -> BigInt {
 869         match (self.sign, other.sign) {
 870             (Zero, _)    => -other,
 871             (_,    Zero) => self.clone(),
 872             (Plus, Plus) => match self.data.cmp(&other.data) {
 873                 Less    => BigInt::from_biguint(Minus, other.data - self.data),
 874                 Greater => BigInt::from_biguint(Plus, self.data - other.data),
 875                 Equal   => Zero::zero()
 876             },
 877             (Plus, Minus) => self + (-*other),
 878             (Minus, Plus) => -((-self) + *other),
 879             (Minus, Minus) => (-other) - (-*self)
 880         }
 881     }
 882 }
 883
 884 impl Mul<BigInt, BigInt> for BigInt {
 885     #[inline(always)]
 886     fn mul(&self, other: &BigInt) -> BigInt {
 887         match (self.sign, other.sign) {
 888             (Zero, _)     | (_,     Zero)  => Zero::zero(),
 889             (Plus, Plus)  | (Minus, Minus) => {
 890                 BigInt::from_biguint(Plus, self.data * other.data)
 891             },
 892             (Plus, Minus) | (Minus, Plus) => {
 893                 BigInt::from_biguint(Minus, self.data * other.data)
 894             }
 895         }
 896     }
 897 }
 898
 899 impl Div<BigInt, BigInt> for BigInt {
 900     #[inline(always)]
 901     fn div(&self, other: &BigInt) -> BigInt {
 902         let (q, _) = self.div_rem(other);
 903         return q;
 904     }
 905 }
 906
 907 impl Rem<BigInt, BigInt> for BigInt {
 908     #[inline(always)]
 909     fn rem(&self, other: &BigInt) -> BigInt {
 910         let (_, r) = self.div_rem(other);
 911         return r;
 912     }
 913 }
 914
 915 impl Neg<BigInt> for BigInt {
 916     #[inline(always)]
 917     fn neg(&self) -> BigInt {
 918         BigInt::from_biguint(self.sign.neg(), self.data.clone())
 919     }
 920 }
 921
 922 impl Integer for BigInt {
 923     #[inline(always)]
 924     fn div_rem(&self, other: &BigInt) -> (BigInt, BigInt) {
 925         // r.sign == self.sign
 926         let (d_ui, r_ui) = self.data.div_mod_floor(&other.data);
 927         let d = BigInt::from_biguint(Plus, d_ui);
 928         let r = BigInt::from_biguint(Plus, r_ui);
 929         match (self.sign, other.sign) {
 930             (_,    Zero)   => fail!(),
 931             (Plus, Plus)  | (Zero, Plus)  => ( d,  r),
 932             (Plus, Minus) | (Zero, Minus) => (-d,  r),
 933             (Minus, Plus)                 => (-d, -r),
 934             (Minus, Minus)                => ( d, -r)
 935         }
 936     }
 937
 938     #[inline(always)]
 939     fn div_floor(&self, other: &BigInt) -> BigInt {
 940         let (d, _) = self.div_mod_floor(other);
 941         return d;
 942     }
 943
 944     #[inline(always)]
 945     fn mod_floor(&self, other: &BigInt) -> BigInt {
 946         let (_, m) = self.div_mod_floor(other);
 947         return m;
 948     }
 949
 950     #[inline(always)]
 951     fn div_mod_floor(&self, other: &BigInt) -> (BigInt, BigInt) {
 952         // m.sign == other.sign
 953         let (d_ui, m_ui) = self.data.div_rem(&other.data);
 954         let d = BigInt::from_biguint(Plus, d_ui),
 955             m = BigInt::from_biguint(Plus, m_ui);
 956         match (self.sign, other.sign) {
 957             (_,    Zero)   => fail!(),
 958             (Plus, Plus)  | (Zero, Plus)  => (d, m),
 959             (Plus, Minus) | (Zero, Minus) => if m.is_zero() {
 960                 (-d, Zero::zero())
 961             } else {
 962                 (-d - One::one(), m + *other)
 963             },
 964             (Minus, Plus) => if m.is_zero() {
 965                 (-d, Zero::zero())
 966             } else {
 967                 (-d - One::one(), other - m)
 968             },
 969             (Minus, Minus) => (d, -m)
 970         }
 971     }
 972
 973     /**
 974      * Calculates the Greatest Common Divisor (GCD) of the number and `other`
 975      *
 976      * The result is always positive
 977      */
 978     #[inline(always)]
 979     fn gcd(&self, other: &BigInt) -> BigInt {
 980         BigInt::from_biguint(Plus, self.data.gcd(&other.data))
 981     }
 982
 983     /**
 984      * Calculates the Lowest Common Multiple (LCM) of the number and `other`
 985      */
 986     #[inline(always)]
 987     fn lcm(&self, other: &BigInt) -> BigInt {
 988         BigInt::from_biguint(Plus, self.data.lcm(&other.data))
 989     }
 990
 991     /// Returns `true` if the number can be divided by `other` without leaving a remainder
 992     #[inline(always)]
 993     fn is_multiple_of(&self, other: &BigInt) -> bool { self.data.is_multiple_of(&other.data) }
 994
 995     /// Returns `true` if the number is divisible by `2`
 996     #[inline(always)]
 997     fn is_even(&self) -> bool { self.data.is_even() }
 998
 999     /// Returns `true` if the number is not divisible by `2`
1000     #[inline(always)]
1001     fn is_odd(&self) -> bool { self.data.is_odd() }
1002 }
1003
1004 impl IntConvertible for BigInt {
1005     #[inline(always)]
1006     fn to_int(&self) -> int {
1007         match self.sign {
1008             Plus  => uint::min(self.to_uint(), int::max_value as uint) as int,
1009             Zero  => 0,
1010             Minus => uint::min((-self).to_uint(),
1011                                (int::max_value as uint) + 1) as int
1012         }
1013     }
1014
1015     #[inline(always)]
1016     fn from_int(n: int) -> BigInt {
1017         if n > 0 {
1018            return BigInt::from_biguint(Plus,  BigUint::from_uint(n as uint));
1019         }
1020         if n < 0 {
1021             return BigInt::from_biguint(
1022                 Minus, BigUint::from_uint(uint::max_value - (n as uint) + 1)
1023             );
1024         }
1025         return Zero::zero();
1026     }
1027 }
1028
1029 impl ToStrRadix for BigInt {
1030     #[inline(always)]
1031     fn to_str_radix(&self, radix: uint) -> ~str {
1032         match self.sign {
1033             Plus  => self.data.to_str_radix(radix),
1034             Zero  => ~"0",
1035             Minus => ~"-" + self.data.to_str_radix(radix)
1036         }
1037     }
1038 }
1039
1040 impl FromStrRadix for BigInt {
1041     /// Creates and initializes an BigInt.
1042     #[inline(always)]
1043     fn from_str_radix(s: &str, radix: uint)
1044         -> Option<BigInt> {
1045         BigInt::parse_bytes(str::to_bytes(s), radix)
1046     }
1047 }
1048
1049 pub impl BigInt {
1050     /// Creates and initializes an BigInt.
1051     #[inline(always)]
1052     pub fn new(sign: Sign, v: ~[BigDigit]) -> BigInt {
1053         BigInt::from_biguint(sign, BigUint::new(v))
1054     }
1055
1056     /// Creates and initializes an BigInt.
1057     #[inline(always)]
1058     pub fn from_biguint(sign: Sign, data: BigUint) -> BigInt {
1059         if sign == Zero || data.is_zero() {
1060             return BigInt { sign: Zero, data: Zero::zero() };
1061         }
1062         return BigInt { sign: sign, data: data };
1063     }
1064
1065     /// Creates and initializes an BigInt.
1066     #[inline(always)]
1067     pub fn from_uint(n: uint) -> BigInt {
1068         if n == 0 { return Zero::zero(); }
1069         return BigInt::from_biguint(Plus, BigUint::from_uint(n));
1070     }
1071
1072     /// Creates and initializes an BigInt.
1073     #[inline(always)]
1074     pub fn from_slice(sign: Sign, slice: &[BigDigit]) -> BigInt {
1075         BigInt::from_biguint(sign, BigUint::from_slice(slice))
1076     }
1077
1078     /// Creates and initializes an BigInt.
1079     #[inline(always)]
1080     pub fn parse_bytes(buf: &[u8], radix: uint)
1081         -> Option<BigInt> {
1082         if buf.is_empty() { return None; }
1083         let mut sign  = Plus;
1084         let mut start = 0;
1085         if buf[0] == ('-' as u8) {
1086             sign  = Minus;
1087             start = 1;
1088         }
1089         return BigUint::parse_bytes(vec::slice(buf, start, buf.len()), radix)
1090             .map_consume(|bu| BigInt::from_biguint(sign, bu));
1091     }
1092
1093     #[inline(always)]
1094     fn to_uint(&self) -> uint {
1095         match self.sign {
1096             Plus  => self.data.to_uint(),
1097             Zero  => 0,
1098             Minus => 0
1099         }
1100     }
1101 }
1102
1103 #[cfg(test)]
1104 mod biguint_tests {
1105     use super::*;
1106     use core::num::{IntConvertible, Zero, One, FromStrRadix};
1107     use core::cmp::{Less, Equal, Greater};
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 div_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 div_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_div_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.div_rem(&a) == (b.clone(), Zero::zero()));
1396             }
1397             if !b.is_zero() {
1398                 assert!(c.div_rem(&b) == (a.clone(), Zero::zero()));
1399             }
1400         }
1401
1402         for div_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.div_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::*;
1561     use core::cmp::{Less, Equal, Greater};
1562     use core::num::{IntConvertible, Zero, One, FromStrRadix};
1563
1564     #[test]
1565     fn test_from_biguint() {
1566         fn check(inp_s: Sign, inp_n: uint, ans_s: Sign, ans_n: uint) {
1567             let inp = BigInt::from_biguint(inp_s, BigUint::from_uint(inp_n));
1568             let ans = BigInt { sign: ans_s, data: BigUint::from_uint(ans_n)};
1569             assert!(inp == ans);
1570         }
1571         check(Plus, 1, Plus, 1);
1572         check(Plus, 0, Zero, 0);
1573         check(Minus, 1, Minus, 1);
1574         check(Zero, 1, Zero, 0);
1575     }
1576
1577     #[test]
1578     fn test_cmp() {
1579         let vs = [ &[2], &[1, 1], &[2, 1], &[1, 1, 1] ];
1580         let mut nums = vec::reversed(vs)
1581             .map(|s| BigInt::from_slice(Minus, *s));
1582         nums.push(Zero::zero());
1583         nums.push_all_move(vs.map(|s| BigInt::from_slice(Plus, *s)));
1584
1585         for nums.eachi |i, ni| {
1586             for vec::slice(nums, i, nums.len()).eachi |j0, nj| {
1587                 let j = i + j0;
1588                 if i == j {
1589                     assert_eq!(ni.cmp(nj), Equal);
1590                     assert_eq!(nj.cmp(ni), Equal);
1591                     assert!(ni == nj);
1592                     assert!(!(ni != nj));
1593                     assert!(ni <= nj);
1594                     assert!(ni >= nj);
1595                     assert!(!(ni < nj));
1596                     assert!(!(ni > nj));
1597                 } else {
1598                     assert_eq!(ni.cmp(nj), Less);
1599                     assert_eq!(nj.cmp(ni), Greater);
1600
1601                     assert!(!(ni == nj));
1602                     assert!(ni != nj);
1603
1604                     assert!(ni <= nj);
1605                     assert!(!(ni >= nj));
1606                     assert!(ni < nj);
1607                     assert!(!(ni > nj));
1608
1609                     assert!(!(nj <= ni));
1610                     assert!(nj >= ni);
1611                     assert!(!(nj < ni));
1612                     assert!(nj > ni);
1613                 }
1614             }
1615         }
1616     }
1617
1618     #[test]
1619     fn test_convert_int() {
1620         fn check(b: BigInt, i: int) {
1621             assert!(b == IntConvertible::from_int(i));
1622             assert!(b.to_int() == i);
1623         }
1624
1625         check(Zero::zero(), 0);
1626         check(One::one(), 1);
1627         check(BigInt::from_biguint(
1628             Plus, BigUint::from_uint(int::max_value as uint)
1629         ), int::max_value);
1630
1631         assert!(BigInt::from_biguint(
1632             Plus, BigUint::from_uint(int::max_value as uint + 1)
1633         ).to_int() == int::max_value);
1634         assert!(BigInt::from_biguint(
1635             Plus, BigUint::new(~[1, 2, 3])
1636         ).to_int() == int::max_value);
1637
1638         check(BigInt::from_biguint(
1639             Minus, BigUint::from_uint(-int::min_value as uint)
1640         ), int::min_value);
1641         assert!(BigInt::from_biguint(
1642             Minus, BigUint::from_uint(-int::min_value as uint + 1)
1643         ).to_int() == int::min_value);
1644         assert!(BigInt::from_biguint(
1645             Minus, BigUint::new(~[1, 2, 3])
1646         ).to_int() == int::min_value);
1647     }
1648
1649     #[test]
1650     fn test_convert_uint() {
1651         fn check(b: BigInt, u: uint) {
1652             assert!(b == BigInt::from_uint(u));
1653             assert!(b.to_uint() == u);
1654         }
1655
1656         check(Zero::zero(), 0);
1657         check(One::one(), 1);
1658
1659         check(
1660             BigInt::from_biguint(Plus, BigUint::from_uint(uint::max_value)),
1661             uint::max_value);
1662         assert!(BigInt::from_biguint(
1663             Plus, BigUint::new(~[1, 2, 3])
1664         ).to_uint() == uint::max_value);
1665
1666         assert!(BigInt::from_biguint(
1667             Minus, BigUint::from_uint(uint::max_value)
1668         ).to_uint() == 0);
1669         assert!(BigInt::from_biguint(
1670             Minus, BigUint::new(~[1, 2, 3])
1671         ).to_uint() == 0);
1672     }
1673
1674     static sum_triples: &'static [(&'static [BigDigit],
1675                                    &'static [BigDigit],
1676                                    &'static [BigDigit])] = &[
1677         (&[],          &[],       &[]),
1678         (&[],          &[ 1],     &[ 1]),
1679         (&[ 1],        &[ 1],     &[ 2]),
1680         (&[ 1],        &[ 1,  1], &[ 2,  1]),
1681         (&[ 1],        &[-1],     &[ 0,  1]),
1682         (&[ 1],        &[-1, -1], &[ 0,  0, 1]),
1683         (&[-1, -1],    &[-1, -1], &[-2, -1, 1]),
1684         (&[ 1,  1, 1], &[-1, -1], &[ 0,  1, 2]),
1685         (&[ 2,  2, 1], &[-1, -2], &[ 1,  1, 2])
1686     ];
1687
1688     #[test]
1689     fn test_add() {
1690         for sum_triples.each |elm| {
1691             let (aVec, bVec, cVec) = *elm;
1692             let a = BigInt::from_slice(Plus, aVec);
1693             let b = BigInt::from_slice(Plus, bVec);
1694             let c = BigInt::from_slice(Plus, cVec);
1695
1696             assert!(a + b == c);
1697             assert!(b + a == c);
1698             assert!(c + (-a) == b);
1699             assert!(c + (-b) == a);
1700             assert!(a + (-c) == (-b));
1701             assert!(b + (-c) == (-a));
1702             assert!((-a) + (-b) == (-c));
1703             assert!(a + (-a) == Zero::zero());
1704         }
1705     }
1706
1707     #[test]
1708     fn test_sub() {
1709         for sum_triples.each |elm| {
1710             let (aVec, bVec, cVec) = *elm;
1711             let a = BigInt::from_slice(Plus, aVec);
1712             let b = BigInt::from_slice(Plus, bVec);
1713             let c = BigInt::from_slice(Plus, cVec);
1714
1715             assert!(c - a == b);
1716             assert!(c - b == a);
1717             assert!((-b) - a == (-c));
1718             assert!((-a) - b == (-c));
1719             assert!(b - (-a) == c);
1720             assert!(a - (-b) == c);
1721             assert!((-c) - (-a) == (-b));
1722             assert!(a - a == Zero::zero());
1723         }
1724     }
1725
1726     static mul_triples: &'static [(&'static [BigDigit],
1727                                    &'static [BigDigit],
1728                                    &'static [BigDigit])] = &[
1729         (&[],               &[],               &[]),
1730         (&[],               &[ 1],             &[]),
1731         (&[ 2],             &[],               &[]),
1732         (&[ 1],             &[ 1],             &[1]),
1733         (&[ 2],             &[ 3],             &[ 6]),
1734         (&[ 1],             &[ 1,  1,  1],     &[1, 1,  1]),
1735         (&[ 1,  2,  3],     &[ 3],             &[ 3,  6,  9]),
1736         (&[ 1,  1,  1],     &[-1],             &[-1, -1, -1]),
1737         (&[ 1,  2,  3],     &[-1],             &[-1, -2, -2, 2]),
1738         (&[ 1,  2,  3,  4], &[-1],             &[-1, -2, -2, -2, 3]),
1739         (&[-1],             &[-1],             &[ 1, -2]),
1740         (&[-1, -1],         &[-1],             &[ 1, -1, -2]),
1741         (&[-1, -1, -1],     &[-1],             &[ 1, -1, -1, -2]),
1742         (&[-1, -1, -1, -1], &[-1],             &[ 1, -1, -1, -1, -2]),
1743         (&[-1/2 + 1],       &[ 2],             &[ 0,  1]),
1744         (&[0, -1/2 + 1],    &[ 2],             &[ 0,  0,  1]),
1745         (&[ 1,  2],         &[ 1,  2,  3],     &[1, 4,  7,  6]),
1746         (&[-1, -1],         &[-1, -1, -1],     &[1, 0, -1, -2, -1]),
1747         (&[-1, -1, -1],     &[-1, -1, -1, -1], &[1, 0,  0, -1, -2, -1, -1]),
1748         (&[ 0,  0,  1],     &[ 1,  2,  3],     &[0, 0,  1,  2,  3]),
1749         (&[ 0,  0,  1],     &[ 0,  0,  0,  1], &[0, 0,  0,  0,  0,  1])
1750     ];
1751
1752     static div_rem_quadruples: &'static [(&'static [BigDigit],
1753                                           &'static [BigDigit],
1754                                           &'static [BigDigit],
1755                                           &'static [BigDigit])]
1756         = &[
1757             (&[ 1],        &[ 2], &[],               &[1]),
1758             (&[ 1,  1],    &[ 2], &[-1/2+1],         &[1]),
1759             (&[ 1,  1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
1760             (&[ 0,  1],    &[-1], &[1],              &[1]),
1761             (&[-1, -1],    &[-2], &[2, 1],           &[3])
1762         ];
1763
1764     #[test]
1765     fn test_mul() {
1766         for mul_triples.each |elm| {
1767             let (aVec, bVec, cVec) = *elm;
1768             let a = BigInt::from_slice(Plus, aVec);
1769             let b = BigInt::from_slice(Plus, bVec);
1770             let c = BigInt::from_slice(Plus, cVec);
1771
1772             assert!(a * b == c);
1773             assert!(b * a == c);
1774
1775             assert!((-a) * b == -c);
1776             assert!((-b) * a == -c);
1777         }
1778
1779         for div_rem_quadruples.each |elm| {
1780             let (aVec, bVec, cVec, dVec) = *elm;
1781             let a = BigInt::from_slice(Plus, aVec);
1782             let b = BigInt::from_slice(Plus, bVec);
1783             let c = BigInt::from_slice(Plus, cVec);
1784             let d = BigInt::from_slice(Plus, dVec);
1785
1786             assert!(a == b * c + d);
1787             assert!(a == c * b + d);
1788         }
1789     }
1790
1791     #[test]
1792     fn test_div_mod_floor() {
1793         fn check_sub(a: &BigInt, b: &BigInt, ans_d: &BigInt, ans_m: &BigInt) {
1794             let (d, m) = a.div_mod_floor(b);
1795             if !m.is_zero() {
1796                 assert!(m.sign == b.sign);
1797             }
1798             assert!(m.abs() <= b.abs());
1799             assert!(*a == b * d + m);
1800             assert!(d == *ans_d);
1801             assert!(m == *ans_m);
1802         }
1803
1804         fn check(a: &BigInt, b: &BigInt, d: &BigInt, m: &BigInt) {
1805             if m.is_zero() {
1806                 check_sub(a, b, d, m);
1807                 check_sub(a, &b.neg(), &d.neg(), m);
1808                 check_sub(&a.neg(), b, &d.neg(), m);
1809                 check_sub(&a.neg(), &b.neg(), d, m);
1810             } else {
1811                 check_sub(a, b, d, m);
1812                 check_sub(a, &b.neg(), &(d.neg() - One::one()), &(m - *b));
1813                 check_sub(&a.neg(), b, &(d.neg() - One::one()), &(b - *m));
1814                 check_sub(&a.neg(), &b.neg(), d, &m.neg());
1815             }
1816         }
1817
1818         for mul_triples.each |elm| {
1819             let (aVec, bVec, cVec) = *elm;
1820             let a = BigInt::from_slice(Plus, aVec);
1821             let b = BigInt::from_slice(Plus, bVec);
1822             let c = BigInt::from_slice(Plus, cVec);
1823
1824             if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
1825             if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
1826         }
1827
1828         for div_rem_quadruples.each |elm| {
1829             let (aVec, bVec, cVec, dVec) = *elm;
1830             let a = BigInt::from_slice(Plus, aVec);
1831             let b = BigInt::from_slice(Plus, bVec);
1832             let c = BigInt::from_slice(Plus, cVec);
1833             let d = BigInt::from_slice(Plus, dVec);
1834
1835             if !b.is_zero() {
1836                 check(&a, &b, &c, &d);
1837             }
1838         }
1839     }
1840
1841
1842     #[test]
1843     fn test_div_rem() {
1844         fn check_sub(a: &BigInt, b: &BigInt, ans_q: &BigInt, ans_r: &BigInt) {
1845             let (q, r) = a.div_rem(b);
1846             if !r.is_zero() {
1847                 assert!(r.sign == a.sign);
1848             }
1849             assert!(r.abs() <= b.abs());
1850             assert!(*a == b * q + r);
1851             assert!(q == *ans_q);
1852             assert!(r == *ans_r);
1853         }
1854
1855         fn check(a: &BigInt, b: &BigInt, q: &BigInt, r: &BigInt) {
1856             check_sub(a, b, q, r);
1857             check_sub(a, &b.neg(), &q.neg(), r);
1858             check_sub(&a.neg(), b, &q.neg(), &r.neg());
1859             check_sub(&a.neg(), &b.neg(), q, &r.neg());
1860         }
1861         for mul_triples.each |elm| {
1862             let (aVec, bVec, cVec) = *elm;
1863             let a = BigInt::from_slice(Plus, aVec);
1864             let b = BigInt::from_slice(Plus, bVec);
1865             let c = BigInt::from_slice(Plus, cVec);
1866
1867             if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
1868             if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
1869         }
1870
1871         for div_rem_quadruples.each |elm| {
1872             let (aVec, bVec, cVec, dVec) = *elm;
1873             let a = BigInt::from_slice(Plus, aVec);
1874             let b = BigInt::from_slice(Plus, bVec);
1875             let c = BigInt::from_slice(Plus, cVec);
1876             let d = BigInt::from_slice(Plus, dVec);
1877
1878             if !b.is_zero() {
1879                 check(&a, &b, &c, &d);
1880             }
1881         }
1882     }
1883
1884     #[test]
1885     fn test_gcd() {
1886         fn check(a: int, b: int, c: int) {
1887             let big_a: BigInt = IntConvertible::from_int(a);
1888             let big_b: BigInt = IntConvertible::from_int(b);
1889             let big_c: BigInt = IntConvertible::from_int(c);
1890
1891             assert_eq!(big_a.gcd(&big_b), big_c);
1892         }
1893
1894         check(10, 2, 2);
1895         check(10, 3, 1);
1896         check(0, 3, 3);
1897         check(3, 3, 3);
1898         check(56, 42, 14);
1899         check(3, -3, 3);
1900         check(-6, 3, 3);
1901         check(-4, -2, 2);
1902     }
1903
1904     #[test]
1905     fn test_lcm() {
1906         fn check(a: int, b: int, c: int) {
1907             let big_a: BigInt = IntConvertible::from_int(a);
1908             let big_b: BigInt = IntConvertible::from_int(b);
1909             let big_c: BigInt = IntConvertible::from_int(c);
1910
1911             assert_eq!(big_a.lcm(&big_b), big_c);
1912         }
1913
1914         check(1, 0, 0);
1915         check(0, 1, 0);
1916         check(1, 1, 1);
1917         check(-1, 1, 1);
1918         check(1, -1, 1);
1919         check(-1, -1, 1);
1920         check(8, 9, 72);
1921         check(11, 5, 55);
1922     }
1923
1924     #[test]
1925     fn test_to_str_radix() {
1926         fn check(n: int, ans: &str) {
1927             assert!(ans == IntConvertible::from_int::<BigInt>(n).to_str_radix(10));
1928         }
1929         check(10, "10");
1930         check(1, "1");
1931         check(0, "0");
1932         check(-1, "-1");
1933         check(-10, "-10");
1934     }
1935
1936
1937     #[test]
1938     fn test_from_str_radix() {
1939         fn check(s: &str, ans: Option<int>) {
1940             let ans = ans.map(|&n| IntConvertible::from_int::<BigInt>(n));
1941             assert!(FromStrRadix::from_str_radix(s, 10) == ans);
1942         }
1943         check("10", Some(10));
1944         check("1", Some(1));
1945         check("0", Some(0));
1946         check("-1", Some(-1));
1947         check("-10", Some(-10));
1948         check("Z", None);
1949         check("_", None);
1950     }
1951
1952     #[test]
1953     fn test_neg() {
1954         assert!(-BigInt::new(Plus,  ~[1, 1, 1]) ==
1955             BigInt::new(Minus, ~[1, 1, 1]));
1956         assert!(-BigInt::new(Minus, ~[1, 1, 1]) ==
1957             BigInt::new(Plus,  ~[1, 1, 1]));
1958         assert!(-Zero::zero::<BigInt>() == Zero::zero::<BigInt>());
1959     }
1960 }
1961