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