libstd: Rename libcore to libstd and libstd to libextra; update makefiles.

This only changes the directory names; it does not change the "real"
metadata names.

3 files changed, 2861 insertions, 0 deletions

diff --git a/src/libextra/num/bigint.rs b/src/libextra/num/bigint.rs
new file mode 100644
index 00000000000..21685b03c07
--- /dev/null
+++ b/src/libextra/num/bigint.rs
@@ -0,0 +1,2021 @@
+// Copyright 2013 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+/*!
+
+A Big integer (signed version: BigInt, unsigned version: BigUint).
+
+A BigUint is represented as an array of BigDigits.
+A BigInt is a combination of BigUint and Sign.
+*/
+
+use core::cmp::{Eq, Ord, TotalEq, TotalOrd, Ordering, Less, Equal, Greater};
+use core::num::{IntConvertible, Zero, One, ToStrRadix, FromStrRadix, Orderable};
+
+/**
+A BigDigit is a BigUint's composing element.
+
+A BigDigit is half the size of machine word size.
+*/
+#[cfg(target_arch = "x86")]
+#[cfg(target_arch = "arm")]
+#[cfg(target_arch = "mips")]
+pub type BigDigit = u16;
+
+/**
+A BigDigit is a BigUint's composing element.
+
+A BigDigit is half the size of machine word size.
+*/
+#[cfg(target_arch = "x86_64")]
+pub type BigDigit = u32;
+
+pub mod BigDigit {
+    use bigint::BigDigit;
+
+    #[cfg(target_arch = "x86")]
+    #[cfg(target_arch = "arm")]
+    #[cfg(target_arch = "mips")]
+    pub static bits: uint = 16;
+
+    #[cfg(target_arch = "x86_64")]
+    pub static bits: uint = 32;
+
+    pub static base: uint = 1 << bits;
+    priv static hi_mask: uint = (-1 as uint) << bits;
+    priv static lo_mask: uint = (-1 as uint) >> bits;
+
+    #[inline(always)]
+    priv fn get_hi(n: uint) -> BigDigit { (n >> bits) as BigDigit }
+    #[inline(always)]
+    priv fn get_lo(n: uint) -> BigDigit { (n & lo_mask) as BigDigit }
+
+    /// Split one machine sized unsigned integer into two BigDigits.
+    #[inline(always)]
+    pub fn from_uint(n: uint) -> (BigDigit, BigDigit) {
+        (get_hi(n), get_lo(n))
+    }
+
+    /// Join two BigDigits into one machine sized unsigned integer
+    #[inline(always)]
+    pub fn to_uint(hi: BigDigit, lo: BigDigit) -> uint {
+        (lo as uint) | ((hi as uint) << bits)
+    }
+}
+
+/**
+A big unsigned integer type.
+
+A BigUint-typed value BigUint { data: @[a, b, c] } represents a number
+(a + b * BigDigit::base + c * BigDigit::base^2).
+*/
+#[deriving(Clone)]
+pub struct BigUint {
+    priv data: ~[BigDigit]
+}
+
+impl Eq for BigUint {
+    #[inline(always)]
+    fn eq(&self, other: &BigUint) -> bool { self.equals(other) }
+    #[inline(always)]
+    fn ne(&self, other: &BigUint) -> bool { !self.equals(other) }
+}
+
+impl TotalEq for BigUint {
+    #[inline(always)]
+    fn equals(&self, other: &BigUint) -> bool {
+        match self.cmp(other) { Equal => true, _ => false }
+    }
+}
+
+impl Ord for BigUint {
+    #[inline(always)]
+    fn lt(&self, other: &BigUint) -> bool {
+        match self.cmp(other) { Less => true, _ => false}
+    }
+    #[inline(always)]
+    fn le(&self, other: &BigUint) -> bool {
+        match self.cmp(other) { Less | Equal => true, _ => false }
+    }
+    #[inline(always)]
+    fn ge(&self, other: &BigUint) -> bool {
+        match self.cmp(other) { Greater | Equal => true, _ => false }
+    }
+    #[inline(always)]
+    fn gt(&self, other: &BigUint) -> bool {
+        match self.cmp(other) { Greater => true, _ => false }
+    }
+}
+
+impl TotalOrd for BigUint {
+    #[inline(always)]
+    fn cmp(&self, other: &BigUint) -> Ordering {
+        let s_len = self.data.len(), o_len = other.data.len();
+        if s_len < o_len { return Less; }
+        if s_len > o_len { return Greater;  }
+
+        for self.data.eachi_reverse |i, elm| {
+            match (*elm, other.data[i]) {
+                (l, r) if l < r => return Less,
+                (l, r) if l > r => return Greater,
+                _               => loop
+            };
+        }
+        return Equal;
+    }
+}
+
+impl ToStr for BigUint {
+    #[inline(always)]
+    fn to_str(&self) -> ~str { self.to_str_radix(10) }
+}
+
+impl FromStr for BigUint {
+    #[inline(always)]
+    fn from_str(s: &str) -> Option<BigUint> {
+        FromStrRadix::from_str_radix(s, 10)
+    }
+}
+
+impl Num for BigUint {}
+
+impl Orderable for BigUint {
+    #[inline(always)]
+    fn min(&self, other: &BigUint) -> BigUint {
+        if self < other { self.clone() } else { other.clone() }
+    }
+
+    #[inline(always)]
+    fn max(&self, other: &BigUint) -> BigUint {
+        if self > other { self.clone() } else { other.clone() }
+    }
+
+    #[inline(always)]
+    fn clamp(&self, mn: &BigUint, mx: &BigUint) -> BigUint {
+        if self > mx { mx.clone() } else
+        if self < mn { mn.clone() } else { self.clone() }
+    }
+}
+
+impl Shl<uint, BigUint> for BigUint {
+    #[inline(always)]
+    fn shl(&self, rhs: &uint) -> BigUint {
+        let n_unit = *rhs / BigDigit::bits;
+        let n_bits = *rhs % BigDigit::bits;
+        return self.shl_unit(n_unit).shl_bits(n_bits);
+    }
+}
+
+impl Shr<uint, BigUint> for BigUint {
+    #[inline(always)]
+    fn shr(&self, rhs: &uint) -> BigUint {
+        let n_unit = *rhs / BigDigit::bits;
+        let n_bits = *rhs % BigDigit::bits;
+        return self.shr_unit(n_unit).shr_bits(n_bits);
+    }
+}
+
+impl Zero for BigUint {
+    #[inline(always)]
+    fn zero() -> BigUint { BigUint::new(~[]) }
+
+    #[inline(always)]
+    fn is_zero(&self) -> bool { self.data.is_empty() }
+}
+
+impl One for BigUint {
+    #[inline(always)]
+    fn one() -> BigUint { BigUint::new(~[1]) }
+}
+
+impl Unsigned for BigUint {}
+
+impl Add<BigUint, BigUint> for BigUint {
+    #[inline(always)]
+    fn add(&self, other: &BigUint) -> BigUint {
+        let new_len = uint::max(self.data.len(), other.data.len());
+
+        let mut carry = 0;
+        let sum = do vec::from_fn(new_len) |i| {
+            let ai = if i < self.data.len()  { self.data[i]  } else { 0 };
+            let bi = if i < other.data.len() { other.data[i] } else { 0 };
+            let (hi, lo) = BigDigit::from_uint(
+                (ai as uint) + (bi as uint) + (carry as uint)
+            );
+            carry = hi;
+            lo
+        };
+        if carry == 0 { return BigUint::new(sum) };
+        return BigUint::new(sum + [carry]);
+    }
+}
+
+impl Sub<BigUint, BigUint> for BigUint {
+    #[inline(always)]
+    fn sub(&self, other: &BigUint) -> BigUint {
+        let new_len = uint::max(self.data.len(), other.data.len());
+
+        let mut borrow = 0;
+        let diff = do vec::from_fn(new_len) |i| {
+            let ai = if i < self.data.len()  { self.data[i]  } else { 0 };
+            let bi = if i < other.data.len() { other.data[i] } else { 0 };
+            let (hi, lo) = BigDigit::from_uint(
+                (BigDigit::base) +
+                (ai as uint) - (bi as uint) - (borrow as uint)
+            );
+            /*
+            hi * (base) + lo == 1*(base) + ai - bi - borrow
+            => ai - bi - borrow < 0 <=> hi == 0
+            */
+            borrow = if hi == 0 { 1 } else { 0 };
+            lo
+        };
+
+        assert_eq!(borrow, 0);     // <=> assert!((self >= other));
+        return BigUint::new(diff);
+    }
+}
+
+impl Mul<BigUint, BigUint> for BigUint {
+    fn mul(&self, other: &BigUint) -> BigUint {
+        if self.is_zero() || other.is_zero() { return Zero::zero(); }
+
+        let s_len = self.data.len(), o_len = other.data.len();
+        if s_len == 1 { return mul_digit(other, self.data[0]);  }
+        if o_len == 1 { return mul_digit(self,  other.data[0]); }
+
+        // Using Karatsuba multiplication
+        // (a1 * base + a0) * (b1 * base + b0)
+        // = a1*b1 * base^2 +
+        //   (a1*b1 + a0*b0 - (a1-b0)*(b1-a0)) * base +
+        //   a0*b0
+        let half_len = uint::max(s_len, o_len) / 2;
+        let (sHi, sLo) = cut_at(self,  half_len);
+        let (oHi, oLo) = cut_at(other, half_len);
+
+        let ll = sLo * oLo;
+        let hh = sHi * oHi;
+        let mm = {
+            let (s1, n1) = sub_sign(sHi, sLo);
+            let (s2, n2) = sub_sign(oHi, oLo);
+            match (s1, s2) {
+                (Equal, _) | (_, Equal) => hh + ll,
+                (Less, Greater) | (Greater, Less) => hh + ll + (n1 * n2),
+                (Less, Less) | (Greater, Greater) => hh + ll - (n1 * n2)
+            }
+        };
+
+        return ll + mm.shl_unit(half_len) + hh.shl_unit(half_len * 2);
+
+        #[inline(always)]
+        fn mul_digit(a: &BigUint, n: BigDigit) -> BigUint {
+            if n == 0 { return Zero::zero(); }
+            if n == 1 { return copy *a; }
+
+            let mut carry = 0;
+            let prod = do vec::map(a.data) |ai| {
+                let (hi, lo) = BigDigit::from_uint(
+                    (*ai as uint) * (n as uint) + (carry as uint)
+                );
+                carry = hi;
+                lo
+            };
+            if carry == 0 { return BigUint::new(prod) };
+            return BigUint::new(prod + [carry]);
+        }
+
+        #[inline(always)]
+        fn cut_at(a: &BigUint, n: uint) -> (BigUint, BigUint) {
+            let mid = uint::min(a.data.len(), n);
+            return (BigUint::from_slice(vec::slice(a.data, mid,
+                                                   a.data.len())),
+                    BigUint::from_slice(vec::slice(a.data, 0, mid)));
+        }
+
+        #[inline(always)]
+        fn sub_sign(a: BigUint, b: BigUint) -> (Ordering, BigUint) {
+            match a.cmp(&b) {
+                Less    => (Less,    b - a),
+                Greater => (Greater, a - b),
+                _       => (Equal,   Zero::zero())
+            }
+        }
+    }
+}
+
+impl Div<BigUint, BigUint> for BigUint {
+    #[inline(always)]
+    fn div(&self, other: &BigUint) -> BigUint {
+        let (q, _) = self.div_rem(other);
+        return q;
+    }
+}
+
+impl Rem<BigUint, BigUint> for BigUint {
+    #[inline(always)]
+    fn rem(&self, other: &BigUint) -> BigUint {
+        let (_, r) = self.div_rem(other);
+        return r;
+    }
+}
+
+impl Neg<BigUint> for BigUint {
+    #[inline(always)]
+    fn neg(&self) -> BigUint { fail!() }
+}
+
+impl Integer for BigUint {
+    #[inline(always)]
+    fn div_rem(&self, other: &BigUint) -> (BigUint, BigUint) {
+        self.div_mod_floor(other)
+    }
+
+    #[inline(always)]
+    fn div_floor(&self, other: &BigUint) -> BigUint {
+        let (d, _) = self.div_mod_floor(other);
+        return d;
+    }
+
+    #[inline(always)]
+    fn mod_floor(&self, other: &BigUint) -> BigUint {
+        let (_, m) = self.div_mod_floor(other);
+        return m;
+    }
+
+    #[inline(always)]
+    fn div_mod_floor(&self, other: &BigUint) -> (BigUint, BigUint) {
+        if other.is_zero() { fail!() }
+        if self.is_zero() { return (Zero::zero(), Zero::zero()); }
+        if *other == One::one() { return (copy *self, Zero::zero()); }
+
+        match self.cmp(other) {
+            Less    => return (Zero::zero(), copy *self),
+            Equal   => return (One::one(), Zero::zero()),
+            Greater => {} // Do nothing
+        }
+
+        let mut shift = 0;
+        let mut n = *other.data.last();
+        while n < (1 << BigDigit::bits - 2) {
+            n <<= 1;
+            shift += 1;
+        }
+        assert!(shift < BigDigit::bits);
+        let (d, m) = div_mod_floor_inner(self << shift, other << shift);
+        return (d, m >> shift);
+
+        #[inline(always)]
+        fn div_mod_floor_inner(a: BigUint, b: BigUint) -> (BigUint, BigUint) {
+            let mut m = a;
+            let mut d = Zero::zero::<BigUint>();
+            let mut n = 1;
+            while m >= b {
+                let mut (d0, d_unit, b_unit) = div_estimate(&m, &b, n);
+                let mut prod = b * d0;
+                while prod > m {
+                    // FIXME(#6050): overloaded operators force moves with generic types
+                    // d0 -= d_unit
+                    d0   = d0 - d_unit;
+                    // FIXME(#6050): overloaded operators force moves with generic types
+                    // prod = prod - b_unit;
+                    prod = prod - b_unit
+                }
+                if d0.is_zero() {
+                    n = 2;
+                    loop;
+                }
+                n = 1;
+                // FIXME(#6102): Assignment operator for BigInt causes ICE
+                // d += d0;
+                d = d + d0;
+                // FIXME(#6102): Assignment operator for BigInt causes ICE
+                // m -= prod;
+                m = m - prod;
+            }
+            return (d, m);
+        }
+
+        #[inline(always)]
+        fn div_estimate(a: &BigUint, b: &BigUint, n: uint)
+            -> (BigUint, BigUint, BigUint) {
+            if a.data.len() < n {
+                return (Zero::zero(), Zero::zero(), copy *a);
+            }
+
+            let an = vec::slice(a.data, a.data.len() - n, a.data.len());
+            let bn = *b.data.last();
+            let mut d = ~[];
+            let mut carry = 0;
+            for an.each_reverse |elt| {
+                let ai = BigDigit::to_uint(carry, *elt);
+                let di = ai / (bn as uint);
+                assert!(di < BigDigit::base);
+                carry = (ai % (bn as uint)) as BigDigit;
+                d = ~[di as BigDigit] + d;
+            }
+
+            let shift = (a.data.len() - an.len()) - (b.data.len() - 1);
+            if shift == 0 {
+                return (BigUint::new(d), One::one(), copy *b);
+            }
+            return (BigUint::from_slice(d).shl_unit(shift),
+                    One::one::<BigUint>().shl_unit(shift),
+                    b.shl_unit(shift));
+        }
+    }
+
+    /**
+     * Calculates the Greatest Common Divisor (GCD) of the number and `other`
+     *
+     * The result is always positive
+     */
+    #[inline(always)]
+    fn gcd(&self, other: &BigUint) -> BigUint {
+        // Use Euclid's algorithm
+        let mut m = copy *self, n = copy *other;
+        while !m.is_zero() {
+            let temp = m;
+            m = n % temp;
+            n = temp;
+        }
+        return n;
+    }
+
+    /**
+     * Calculates the Lowest Common Multiple (LCM) of the number and `other`
+     */
+    #[inline(always)]
+    fn lcm(&self, other: &BigUint) -> BigUint { ((*self * *other) / self.gcd(other)) }
+
+    /// Returns `true` if the number can be divided by `other` without leaving a remainder
+    #[inline(always)]
+    fn is_multiple_of(&self, other: &BigUint) -> bool { (*self % *other).is_zero() }
+
+    /// Returns `true` if the number is divisible by `2`
+    #[inline(always)]
+    fn is_even(&self) -> bool {
+        // Considering only the last digit.
+        if self.data.is_empty() {
+            true
+        } else {
+            self.data[0].is_even()
+        }
+    }
+
+    /// Returns `true` if the number is not divisible by `2`
+    #[inline(always)]
+    fn is_odd(&self) -> bool { !self.is_even() }
+}
+
+impl IntConvertible for BigUint {
+    #[inline(always)]
+    fn to_int(&self) -> int {
+        uint::min(self.to_uint(), int::max_value as uint) as int
+    }
+
+    #[inline(always)]
+    fn from_int(n: int) -> BigUint {
+        if (n < 0) { Zero::zero() } else { BigUint::from_uint(n as uint) }
+    }
+}
+
+impl ToStrRadix for BigUint {
+    #[inline(always)]
+    fn to_str_radix(&self, radix: uint) -> ~str {
+        assert!(1 < radix && radix <= 16);
+        let (base, max_len) = get_radix_base(radix);
+        if base == BigDigit::base {
+            return fill_concat(self.data, radix, max_len)
+        }
+        return fill_concat(convert_base(copy *self, base), radix, max_len);
+
+        #[inline(always)]
+        fn convert_base(n: BigUint, base: uint) -> ~[BigDigit] {
+            let divider    = BigUint::from_uint(base);
+            let mut result = ~[];
+            let mut m      = n;
+            while m > divider {
+                let (d, m0) = m.div_mod_floor(&divider);
+                result += [m0.to_uint() as BigDigit];
+                m = d;
+            }
+            if !m.is_zero() {
+                result += [m.to_uint() as BigDigit];
+            }
+            return result;
+        }
+
+        #[inline(always)]
+        fn fill_concat(v: &[BigDigit], radix: uint, l: uint) -> ~str {
+            if v.is_empty() { return ~"0" }
+            let s = str::concat(vec::reversed(v).map(|n| {
+                let s = uint::to_str_radix(*n as uint, radix);
+                str::from_chars(vec::from_elem(l - s.len(), '0')) + s
+            }));
+            str::trim_left_chars(s, ['0']).to_owned()
+        }
+    }
+}
+
+impl FromStrRadix for BigUint {
+    /// Creates and initializes an BigUint.
+    #[inline(always)]
+    pub fn from_str_radix(s: &str, radix: uint)
+        -> Option<BigUint> {
+        BigUint::parse_bytes(str::to_bytes(s), radix)
+    }
+}
+
+impl BigUint {
+    /// Creates and initializes an BigUint.
+    #[inline(always)]
+    pub fn new(v: ~[BigDigit]) -> BigUint {
+        // omit trailing zeros
+        let new_len = v.rposition(|n| *n != 0).map_default(0, |p| *p + 1);
+
+        if new_len == v.len() { return BigUint { data: v }; }
+        let mut v = v;
+        v.truncate(new_len);
+        return BigUint { data: v };
+    }
+
+    /// Creates and initializes an BigUint.
+    #[inline(always)]
+    pub fn from_uint(n: uint) -> BigUint {
+        match BigDigit::from_uint(n) {
+            (0,  0)  => Zero::zero(),
+            (0,  n0) => BigUint::new(~[n0]),
+            (n1, n0) => BigUint::new(~[n0, n1])
+        }
+    }
+
+    /// Creates and initializes an BigUint.
+    #[inline(always)]
+    pub fn from_slice(slice: &[BigDigit]) -> BigUint {
+        return BigUint::new(vec::to_owned(slice));
+    }
+
+    /// Creates and initializes an BigUint.
+    #[inline(always)]
+    pub fn parse_bytes(buf: &[u8], radix: uint)
+        -> Option<BigUint> {
+        let (base, unit_len) = get_radix_base(radix);
+        let base_num: BigUint = BigUint::from_uint(base);
+
+        let mut end             = buf.len();
+        let mut n: BigUint      = Zero::zero();
+        let mut power: BigUint  = One::one();
+        loop {
+            let start = uint::max(end, unit_len) - unit_len;
+            match uint::parse_bytes(vec::slice(buf, start, end), radix) {
+                // FIXME(#6102): Assignment operator for BigInt causes ICE
+                // Some(d) => n += BigUint::from_uint(d) * power,
+                Some(d) => n = n + BigUint::from_uint(d) * power,
+                None    => return None
+            }
+            if end <= unit_len {
+                return Some(n);
+            }
+            end -= unit_len;
+            // FIXME(#6050): overloaded operators force moves with generic types
+            // power *= base_num;
+            power = power * base_num;
+        }
+    }
+
+    #[inline(always)]
+    pub fn to_uint(&self) -> uint {
+        match self.data.len() {
+            0 => 0,
+            1 => self.data[0] as uint,
+            2 => BigDigit::to_uint(self.data[1], self.data[0]),
+            _ => uint::max_value
+        }
+    }
+
+    #[inline(always)]
+    priv fn shl_unit(&self, n_unit: uint) -> BigUint {
+        if n_unit == 0 || self.is_zero() { return copy *self; }
+
+        return BigUint::new(vec::from_elem(n_unit, 0) + self.data);
+    }
+
+    #[inline(always)]
+    priv fn shl_bits(&self, n_bits: uint) -> BigUint {
+        if n_bits == 0 || self.is_zero() { return copy *self; }
+
+        let mut carry = 0;
+        let shifted = do vec::map(self.data) |elem| {
+            let (hi, lo) = BigDigit::from_uint(
+                (*elem as uint) << n_bits | (carry as uint)
+            );
+            carry = hi;
+            lo
+        };
+        if carry == 0 { return BigUint::new(shifted); }
+        return BigUint::new(shifted + [carry]);
+    }
+
+    #[inline(always)]
+    priv fn shr_unit(&self, n_unit: uint) -> BigUint {
+        if n_unit == 0 { return copy *self; }
+        if self.data.len() < n_unit { return Zero::zero(); }
+        return BigUint::from_slice(
+            vec::slice(self.data, n_unit, self.data.len())
+        );
+    }
+
+    #[inline(always)]
+    priv fn shr_bits(&self, n_bits: uint) -> BigUint {
+        if n_bits == 0 || self.data.is_empty() { return copy *self; }
+
+        let mut borrow = 0;
+        let mut shifted = ~[];
+        for self.data.each_reverse |elem| {
+            shifted = ~[(*elem >> n_bits) | borrow] + shifted;
+            borrow = *elem << (BigDigit::bits - n_bits);
+        }
+        return BigUint::new(shifted);
+    }
+}
+
+#[cfg(target_arch = "x86_64")]
+#[inline(always)]
+priv fn get_radix_base(radix: uint) -> (uint, uint) {
+    assert!(1 < radix && radix <= 16);
+    match radix {
+        2  => (4294967296, 32),
+        3  => (3486784401, 20),
+        4  => (4294967296, 16),
+        5  => (1220703125, 13),
+        6  => (2176782336, 12),
+        7  => (1977326743, 11),
+        8  => (1073741824, 10),
+        9  => (3486784401, 10),
+        10 => (1000000000, 9),
+        11 => (2357947691, 9),
+        12 => (429981696,  8),
+        13 => (815730721,  8),
+        14 => (1475789056, 8),
+        15 => (2562890625, 8),
+        16 => (4294967296, 8),
+        _  => fail!()
+    }
+}
+
+#[cfg(target_arch = "arm")]
+#[cfg(target_arch = "x86")]
+#[cfg(target_arch = "mips")]
+#[inline(always)]
+priv fn get_radix_base(radix: uint) -> (uint, uint) {
+    assert!(1 < radix && radix <= 16);
+    match radix {
+        2  => (65536, 16),
+        3  => (59049, 10),
+        4  => (65536, 8),
+        5  => (15625, 6),
+        6  => (46656, 6),
+        7  => (16807, 5),
+        8  => (32768, 5),
+        9  => (59049, 5),
+        10 => (10000, 4),
+        11 => (14641, 4),
+        12 => (20736, 4),
+        13 => (28561, 4),
+        14 => (38416, 4),
+        15 => (50625, 4),
+        16 => (65536, 4),
+        _  => fail!()
+    }
+}
+
+/// A Sign is a BigInt's composing element.
+#[deriving(Eq, Clone)]
+pub enum Sign { Minus, Zero, Plus }
+
+impl Ord for Sign {
+    #[inline(always)]
+    fn lt(&self, other: &Sign) -> bool {
+        match self.cmp(other) { Less => true, _ => false}
+    }
+    #[inline(always)]
+    fn le(&self, other: &Sign) -> bool {
+        match self.cmp(other) { Less | Equal => true, _ => false }
+    }
+    #[inline(always)]
+    fn ge(&self, other: &Sign) -> bool {
+        match self.cmp(other) { Greater | Equal => true, _ => false }
+    }
+    #[inline(always)]
+    fn gt(&self, other: &Sign) -> bool {
+        match self.cmp(other) { Greater => true, _ => false }
+    }
+}
+
+impl TotalOrd for Sign {
+    #[inline(always)]
+    fn cmp(&self, other: &Sign) -> Ordering {
+        match (*self, *other) {
+          (Minus, Minus) | (Zero,  Zero) | (Plus, Plus) => Equal,
+          (Minus, Zero)  | (Minus, Plus) | (Zero, Plus) => Less,
+          _                                             => Greater
+        }
+    }
+}
+
+impl Neg<Sign> for Sign {
+    /// Negate Sign value.
+    #[inline(always)]
+    fn neg(&self) -> Sign {
+        match *self {
+          Minus => Plus,
+          Zero  => Zero,
+          Plus  => Minus
+        }
+    }
+}
+
+/// A big signed integer type.
+#[deriving(Clone)]
+pub struct BigInt {
+    priv sign: Sign,
+    priv data: BigUint
+}
+
+impl Eq for BigInt {
+    #[inline(always)]
+    fn eq(&self, other: &BigInt) -> bool { self.equals(other) }
+    #[inline(always)]
+    fn ne(&self, other: &BigInt) -> bool { !self.equals(other) }
+}
+
+impl TotalEq for BigInt {
+    #[inline(always)]
+    fn equals(&self, other: &BigInt) -> bool {
+        match self.cmp(other) { Equal => true, _ => false }
+    }
+}
+
+impl Ord for BigInt {
+    #[inline(always)]
+    fn lt(&self, other: &BigInt) -> bool {
+        match self.cmp(other) { Less => true, _ => false}
+    }
+    #[inline(always)]
+    fn le(&self, other: &BigInt) -> bool {
+        match self.cmp(other) { Less | Equal => true, _ => false }
+    }
+    #[inline(always)]
+    fn ge(&self, other: &BigInt) -> bool {
+        match self.cmp(other) { Greater | Equal => true, _ => false }
+    }
+    #[inline(always)]
+    fn gt(&self, other: &BigInt) -> bool {
+        match self.cmp(other) { Greater => true, _ => false }
+    }
+}
+
+impl TotalOrd for BigInt {
+    #[inline(always)]
+    fn cmp(&self, other: &BigInt) -> Ordering {
+        let scmp = self.sign.cmp(&other.sign);
+        if scmp != Equal { return scmp; }
+
+        match self.sign {
+            Zero  => Equal,
+            Plus  => self.data.cmp(&other.data),
+            Minus => other.data.cmp(&self.data),
+        }
+    }
+}
+
+impl ToStr for BigInt {
+    #[inline(always)]
+    fn to_str(&self) -> ~str { self.to_str_radix(10) }
+}
+
+impl FromStr for BigInt {
+    #[inline(always)]
+    fn from_str(s: &str) -> Option<BigInt> {
+        FromStrRadix::from_str_radix(s, 10)
+    }
+}
+
+impl Num for BigInt {}
+
+impl Orderable for BigInt {
+    #[inline(always)]
+    fn min(&self, other: &BigInt) -> BigInt {
+        if self < other { self.clone() } else { other.clone() }
+    }
+
+    #[inline(always)]
+    fn max(&self, other: &BigInt) -> BigInt {
+        if self > other { self.clone() } else { other.clone() }
+    }
+
+    #[inline(always)]
+    fn clamp(&self, mn: &BigInt, mx: &BigInt) -> BigInt {
+        if self > mx { mx.clone() } else
+        if self < mn { mn.clone() } else { self.clone() }
+    }
+}
+
+impl Shl<uint, BigInt> for BigInt {
+    #[inline(always)]
+    fn shl(&self, rhs: &uint) -> BigInt {
+        BigInt::from_biguint(self.sign, self.data << *rhs)
+    }
+}
+
+impl Shr<uint, BigInt> for BigInt {
+    #[inline(always)]
+    fn shr(&self, rhs: &uint) -> BigInt {
+        BigInt::from_biguint(self.sign, self.data >> *rhs)
+    }
+}
+
+impl Zero for BigInt {
+    #[inline(always)]
+    fn zero() -> BigInt {
+        BigInt::from_biguint(Zero, Zero::zero())
+    }
+
+    #[inline(always)]
+    fn is_zero(&self) -> bool { self.sign == Zero }
+}
+
+impl One for BigInt {
+    #[inline(always)]
+    fn one() -> BigInt {
+        BigInt::from_biguint(Plus, One::one())
+    }
+}
+
+impl Signed for BigInt {
+    #[inline(always)]
+    fn abs(&self) -> BigInt {
+        match self.sign {
+            Plus | Zero => self.clone(),
+            Minus => BigInt::from_biguint(Plus, self.data.clone())
+        }
+    }
+
+    #[inline(always)]
+    fn abs_sub(&self, other: &BigInt) -> BigInt {
+        if *self <= *other { Zero::zero() } else { *self - *other }
+    }
+
+    #[inline(always)]
+    fn signum(&self) -> BigInt {
+        match self.sign {
+            Plus  => BigInt::from_biguint(Plus, One::one()),
+            Minus => BigInt::from_biguint(Minus, One::one()),
+            Zero  => Zero::zero(),
+        }
+    }
+
+    #[inline(always)]
+    fn is_positive(&self) -> bool { self.sign == Plus }
+
+    #[inline(always)]
+    fn is_negative(&self) -> bool { self.sign == Minus }
+}
+
+impl Add<BigInt, BigInt> for BigInt {
+    #[inline(always)]
+    fn add(&self, other: &BigInt) -> BigInt {
+        match (self.sign, other.sign) {
+            (Zero, _)      => other.clone(),
+            (_,    Zero)   => self.clone(),
+            (Plus, Plus)   => BigInt::from_biguint(Plus,
+                                                   self.data + other.data),
+            (Plus, Minus)  => self - (-*other),
+            (Minus, Plus)  => other - (-*self),
+            (Minus, Minus) => -((-self) + (-*other))
+        }
+    }
+}
+
+impl Sub<BigInt, BigInt> for BigInt {
+    #[inline(always)]
+    fn sub(&self, other: &BigInt) -> BigInt {
+        match (self.sign, other.sign) {
+            (Zero, _)    => -other,
+            (_,    Zero) => self.clone(),
+            (Plus, Plus) => match self.data.cmp(&other.data) {
+                Less    => BigInt::from_biguint(Minus, other.data - self.data),
+                Greater => BigInt::from_biguint(Plus, self.data - other.data),
+                Equal   => Zero::zero()
+            },
+            (Plus, Minus) => self + (-*other),
+            (Minus, Plus) => -((-self) + *other),
+            (Minus, Minus) => (-other) - (-*self)
+        }
+    }
+}
+
+impl Mul<BigInt, BigInt> for BigInt {
+    #[inline(always)]
+    fn mul(&self, other: &BigInt) -> BigInt {
+        match (self.sign, other.sign) {
+            (Zero, _)     | (_,     Zero)  => Zero::zero(),
+            (Plus, Plus)  | (Minus, Minus) => {
+                BigInt::from_biguint(Plus, self.data * other.data)
+            },
+            (Plus, Minus) | (Minus, Plus) => {
+                BigInt::from_biguint(Minus, self.data * other.data)
+            }
+        }
+    }
+}
+
+impl Div<BigInt, BigInt> for BigInt {
+    #[inline(always)]
+    fn div(&self, other: &BigInt) -> BigInt {
+        let (q, _) = self.div_rem(other);
+        return q;
+    }
+}
+
+impl Rem<BigInt, BigInt> for BigInt {
+    #[inline(always)]
+    fn rem(&self, other: &BigInt) -> BigInt {
+        let (_, r) = self.div_rem(other);
+        return r;
+    }
+}
+
+impl Neg<BigInt> for BigInt {
+    #[inline(always)]
+    fn neg(&self) -> BigInt {
+        BigInt::from_biguint(self.sign.neg(), self.data.clone())
+    }
+}
+
+impl Integer for BigInt {
+    #[inline(always)]
+    fn div_rem(&self, other: &BigInt) -> (BigInt, BigInt) {
+        // r.sign == self.sign
+        let (d_ui, r_ui) = self.data.div_mod_floor(&other.data);
+        let d = BigInt::from_biguint(Plus, d_ui);
+        let r = BigInt::from_biguint(Plus, r_ui);
+        match (self.sign, other.sign) {
+            (_,    Zero)   => fail!(),
+            (Plus, Plus)  | (Zero, Plus)  => ( d,  r),
+            (Plus, Minus) | (Zero, Minus) => (-d,  r),
+            (Minus, Plus)                 => (-d, -r),
+            (Minus, Minus)                => ( d, -r)
+        }
+    }
+
+    #[inline(always)]
+    fn div_floor(&self, other: &BigInt) -> BigInt {
+        let (d, _) = self.div_mod_floor(other);
+        return d;
+    }
+
+    #[inline(always)]
+    fn mod_floor(&self, other: &BigInt) -> BigInt {
+        let (_, m) = self.div_mod_floor(other);
+        return m;
+    }
+
+    #[inline(always)]
+    fn div_mod_floor(&self, other: &BigInt) -> (BigInt, BigInt) {
+        // m.sign == other.sign
+        let (d_ui, m_ui) = self.data.div_rem(&other.data);
+        let d = BigInt::from_biguint(Plus, d_ui),
+            m = BigInt::from_biguint(Plus, m_ui);
+        match (self.sign, other.sign) {
+            (_,    Zero)   => fail!(),
+            (Plus, Plus)  | (Zero, Plus)  => (d, m),
+            (Plus, Minus) | (Zero, Minus) => if m.is_zero() {
+                (-d, Zero::zero())
+            } else {
+                (-d - One::one(), m + *other)
+            },
+            (Minus, Plus) => if m.is_zero() {
+                (-d, Zero::zero())
+            } else {
+                (-d - One::one(), other - m)
+            },
+            (Minus, Minus) => (d, -m)
+        }
+    }
+
+    /**
+     * Calculates the Greatest Common Divisor (GCD) of the number and `other`
+     *
+     * The result is always positive
+     */
+    #[inline(always)]
+    fn gcd(&self, other: &BigInt) -> BigInt {
+        BigInt::from_biguint(Plus, self.data.gcd(&other.data))
+    }
+
+    /**
+     * Calculates the Lowest Common Multiple (LCM) of the number and `other`
+     */
+    #[inline(always)]
+    fn lcm(&self, other: &BigInt) -> BigInt {
+        BigInt::from_biguint(Plus, self.data.lcm(&other.data))
+    }
+
+    /// Returns `true` if the number can be divided by `other` without leaving a remainder
+    #[inline(always)]
+    fn is_multiple_of(&self, other: &BigInt) -> bool { self.data.is_multiple_of(&other.data) }
+
+    /// Returns `true` if the number is divisible by `2`
+    #[inline(always)]
+    fn is_even(&self) -> bool { self.data.is_even() }
+
+    /// Returns `true` if the number is not divisible by `2`
+    #[inline(always)]
+    fn is_odd(&self) -> bool { self.data.is_odd() }
+}
+
+impl IntConvertible for BigInt {
+    #[inline(always)]
+    fn to_int(&self) -> int {
+        match self.sign {
+            Plus  => uint::min(self.to_uint(), int::max_value as uint) as int,
+            Zero  => 0,
+            Minus => uint::min((-self).to_uint(),
+                               (int::max_value as uint) + 1) as int
+        }
+    }
+
+    #[inline(always)]
+    fn from_int(n: int) -> BigInt {
+        if n > 0 {
+           return BigInt::from_biguint(Plus,  BigUint::from_uint(n as uint));
+        }
+        if n < 0 {
+            return BigInt::from_biguint(
+                Minus, BigUint::from_uint(uint::max_value - (n as uint) + 1)
+            );
+        }
+        return Zero::zero();
+    }
+}
+
+impl ToStrRadix for BigInt {
+    #[inline(always)]
+    fn to_str_radix(&self, radix: uint) -> ~str {
+        match self.sign {
+            Plus  => self.data.to_str_radix(radix),
+            Zero  => ~"0",
+            Minus => ~"-" + self.data.to_str_radix(radix)
+        }
+    }
+}
+
+impl FromStrRadix for BigInt {
+    /// Creates and initializes an BigInt.
+    #[inline(always)]
+    fn from_str_radix(s: &str, radix: uint)
+        -> Option<BigInt> {
+        BigInt::parse_bytes(str::to_bytes(s), radix)
+    }
+}
+
+pub impl BigInt {
+    /// Creates and initializes an BigInt.
+    #[inline(always)]
+    pub fn new(sign: Sign, v: ~[BigDigit]) -> BigInt {
+        BigInt::from_biguint(sign, BigUint::new(v))
+    }
+
+    /// Creates and initializes an BigInt.
+    #[inline(always)]
+    pub fn from_biguint(sign: Sign, data: BigUint) -> BigInt {
+        if sign == Zero || data.is_zero() {
+            return BigInt { sign: Zero, data: Zero::zero() };
+        }
+        return BigInt { sign: sign, data: data };
+    }
+
+    /// Creates and initializes an BigInt.
+    #[inline(always)]
+    pub fn from_uint(n: uint) -> BigInt {
+        if n == 0 { return Zero::zero(); }
+        return BigInt::from_biguint(Plus, BigUint::from_uint(n));
+    }
+
+    /// Creates and initializes an BigInt.
+    #[inline(always)]
+    pub fn from_slice(sign: Sign, slice: &[BigDigit]) -> BigInt {
+        BigInt::from_biguint(sign, BigUint::from_slice(slice))
+    }
+
+    /// Creates and initializes an BigInt.
+    #[inline(always)]
+    pub fn parse_bytes(buf: &[u8], radix: uint)
+        -> Option<BigInt> {
+        if buf.is_empty() { return None; }
+        let mut sign  = Plus;
+        let mut start = 0;
+        if buf[0] == ('-' as u8) {
+            sign  = Minus;
+            start = 1;
+        }
+        return BigUint::parse_bytes(vec::slice(buf, start, buf.len()), radix)
+            .map_consume(|bu| BigInt::from_biguint(sign, bu));
+    }
+
+    #[inline(always)]
+    fn to_uint(&self) -> uint {
+        match self.sign {
+            Plus  => self.data.to_uint(),
+            Zero  => 0,
+            Minus => 0
+        }
+    }
+}
+
+#[cfg(test)]
+mod biguint_tests {
+    use super::*;
+    use core::num::{IntConvertible, Zero, One, FromStrRadix};
+    use core::cmp::{Less, Equal, Greater};
+
+    #[test]
+    fn test_from_slice() {
+        fn check(slice: &[BigDigit], data: &[BigDigit]) {
+            assert!(data == BigUint::from_slice(slice).data);
+        }
+        check(~[1], ~[1]);
+        check(~[0, 0, 0], ~[]);
+        check(~[1, 2, 0, 0], ~[1, 2]);
+        check(~[0, 0, 1, 2], ~[0, 0, 1, 2]);
+        check(~[0, 0, 1, 2, 0, 0], ~[0, 0, 1, 2]);
+        check(~[-1], ~[-1]);
+    }
+
+    #[test]
+    fn test_cmp() {
+        let data = [ &[], &[1], &[2], &[-1], &[0, 1], &[2, 1], &[1, 1, 1]  ]
+            .map(|v| BigUint::from_slice(*v));
+        for data.eachi |i, ni| {
+            for vec::slice(data, i, data.len()).eachi |j0, nj| {
+                let j = j0 + i;
+                if i == j {
+                    assert_eq!(ni.cmp(nj), Equal);
+                    assert_eq!(nj.cmp(ni), Equal);
+                    assert_eq!(ni, nj);
+                    assert!(!(ni != nj));
+                    assert!(ni <= nj);
+                    assert!(ni >= nj);
+                    assert!(!(ni < nj));
+                    assert!(!(ni > nj));
+                } else {
+                    assert_eq!(ni.cmp(nj), Less);
+                    assert_eq!(nj.cmp(ni), Greater);
+
+                    assert!(!(ni == nj));
+                    assert!(ni != nj);
+
+                    assert!(ni <= nj);
+                    assert!(!(ni >= nj));
+                    assert!(ni < nj);
+                    assert!(!(ni > nj));
+
+                    assert!(!(nj <= ni));
+                    assert!(nj >= ni);
+                    assert!(!(nj < ni));
+                    assert!(nj > ni);
+                }
+            }
+        }
+    }
+
+    #[test]
+    fn test_shl() {
+        fn check(v: ~[BigDigit], shift: uint, ans: ~[BigDigit]) {
+            assert_eq!(BigUint::new(v) << shift, BigUint::new(ans));
+        }
+
+        check(~[], 3, ~[]);
+        check(~[1, 1, 1], 3, ~[1 << 3, 1 << 3, 1 << 3]);
+        check(~[1 << (BigDigit::bits - 2)], 2, ~[0, 1]);
+        check(~[1 << (BigDigit::bits - 2)], 3, ~[0, 2]);
+        check(~[1 << (BigDigit::bits - 2)], 3 + BigDigit::bits, ~[0, 0, 2]);
+
+        test_shl_bits();
+
+        #[cfg(target_arch = "x86_64")]
+        fn test_shl_bits() {
+            check(~[0x7654_3210, 0xfedc_ba98,
+                    0x7654_3210, 0xfedc_ba98], 4,
+                  ~[0x6543_2100, 0xedcb_a987,
+                    0x6543_210f, 0xedcb_a987, 0xf]);
+            check(~[0x2222_1111, 0x4444_3333,
+                    0x6666_5555, 0x8888_7777], 16,
+                  ~[0x1111_0000, 0x3333_2222,
+                    0x5555_4444, 0x7777_6666, 0x8888]);
+        }
+
+        #[cfg(target_arch = "arm")]
+        #[cfg(target_arch = "x86")]
+        #[cfg(target_arch = "mips")]
+        fn test_shl_bits() {
+            check(~[0x3210, 0x7654, 0xba98, 0xfedc,
+                    0x3210, 0x7654, 0xba98, 0xfedc], 4,
+                  ~[0x2100, 0x6543, 0xa987, 0xedcb,
+                    0x210f, 0x6543, 0xa987, 0xedcb, 0xf]);
+            check(~[0x1111, 0x2222, 0x3333, 0x4444,
+                    0x5555, 0x6666, 0x7777, 0x8888], 16,
+                  ~[0x0000, 0x1111, 0x2222, 0x3333,
+                    0x4444, 0x5555, 0x6666, 0x7777, 0x8888]);
+        }
+
+    }
+
+    #[test]
+    #[ignore(cfg(target_arch = "x86"))]
+    #[ignore(cfg(target_arch = "arm"))]
+    #[ignore(cfg(target_arch = "mips"))]
+    fn test_shr() {
+        fn check(v: ~[BigDigit], shift: uint, ans: ~[BigDigit]) {
+            assert_eq!(BigUint::new(v) >> shift, BigUint::new(ans));
+        }
+
+        check(~[], 3, ~[]);
+        check(~[1, 1, 1], 3,
+              ~[1 << (BigDigit::bits - 3), 1 << (BigDigit::bits - 3)]);
+        check(~[1 << 2], 2, ~[1]);
+        check(~[1, 2], 3, ~[1 << (BigDigit::bits - 2)]);
+        check(~[1, 1, 2], 3 + BigDigit::bits, ~[1 << (BigDigit::bits - 2)]);
+        check(~[0, 1], 1, ~[0x80000000]);
+        test_shr_bits();
+
+        #[cfg(target_arch = "x86_64")]
+        fn test_shr_bits() {
+            check(~[0x6543_2100, 0xedcb_a987,
+                    0x6543_210f, 0xedcb_a987, 0xf], 4,
+                  ~[0x7654_3210, 0xfedc_ba98,
+                    0x7654_3210, 0xfedc_ba98]);
+            check(~[0x1111_0000, 0x3333_2222,
+                    0x5555_4444, 0x7777_6666, 0x8888], 16,
+                  ~[0x2222_1111, 0x4444_3333,
+                    0x6666_5555, 0x8888_7777]);
+        }
+
+        #[cfg(target_arch = "arm")]
+        #[cfg(target_arch = "x86")]
+        #[cfg(target_arch = "mips")]
+        fn test_shr_bits() {
+            check(~[0x2100, 0x6543, 0xa987, 0xedcb,
+                    0x210f, 0x6543, 0xa987, 0xedcb, 0xf], 4,
+                  ~[0x3210, 0x7654, 0xba98, 0xfedc,
+                    0x3210, 0x7654, 0xba98, 0xfedc]);
+            check(~[0x0000, 0x1111, 0x2222, 0x3333,
+                    0x4444, 0x5555, 0x6666, 0x7777, 0x8888], 16,
+                  ~[0x1111, 0x2222, 0x3333, 0x4444,
+                    0x5555, 0x6666, 0x7777, 0x8888]);
+        }
+    }
+
+    #[test]
+    fn test_convert_int() {
+        fn check(v: ~[BigDigit], i: int) {
+            let b = BigUint::new(v);
+            assert!(b == IntConvertible::from_int(i));
+            assert!(b.to_int() == i);
+        }
+
+        check(~[], 0);
+        check(~[1], 1);
+        check(~[-1], (uint::max_value >> BigDigit::bits) as int);
+        check(~[ 0,  1], ((uint::max_value >> BigDigit::bits) + 1) as int);
+        check(~[-1, -1 >> 1], int::max_value);
+
+        assert_eq!(BigUint::new(~[0, -1]).to_int(), int::max_value);
+        assert_eq!(BigUint::new(~[0, 0, 1]).to_int(), int::max_value);
+        assert_eq!(BigUint::new(~[0, 0, -1]).to_int(), int::max_value);
+    }
+
+    #[test]
+    fn test_convert_uint() {
+        fn check(v: ~[BigDigit], u: uint) {
+            let b = BigUint::new(v);
+            assert!(b == BigUint::from_uint(u));
+            assert!(b.to_uint() == u);
+        }
+
+        check(~[], 0);
+        check(~[ 1], 1);
+        check(~[-1], uint::max_value >> BigDigit::bits);
+        check(~[ 0,  1], (uint::max_value >> BigDigit::bits) + 1);
+        check(~[ 0, -1], uint::max_value << BigDigit::bits);
+        check(~[-1, -1], uint::max_value);
+
+        assert_eq!(BigUint::new(~[0, 0, 1]).to_uint(), uint::max_value);
+        assert_eq!(BigUint::new(~[0, 0, -1]).to_uint(), uint::max_value);
+    }
+
+    static sum_triples: &'static [(&'static [BigDigit],
+                                   &'static [BigDigit],
+                                   &'static [BigDigit])] = &[
+        (&[],          &[],       &[]),
+        (&[],          &[ 1],     &[ 1]),
+        (&[ 1],        &[ 1],     &[ 2]),
+        (&[ 1],        &[ 1,  1], &[ 2,  1]),
+        (&[ 1],        &[-1],     &[ 0,  1]),
+        (&[ 1],        &[-1, -1], &[ 0,  0, 1]),
+        (&[-1, -1],    &[-1, -1], &[-2, -1, 1]),
+        (&[ 1,  1, 1], &[-1, -1], &[ 0,  1, 2]),
+        (&[ 2,  2, 1], &[-1, -2], &[ 1,  1, 2])
+    ];
+
+    #[test]
+    fn test_add() {
+        for sum_triples.each |elm| {
+            let (aVec, bVec, cVec) = *elm;
+            let a = BigUint::from_slice(aVec);
+            let b = BigUint::from_slice(bVec);
+            let c = BigUint::from_slice(cVec);
+
+            assert!(a + b == c);
+            assert!(b + a == c);
+        }
+    }
+
+    #[test]
+    fn test_sub() {
+        for sum_triples.each |elm| {
+            let (aVec, bVec, cVec) = *elm;
+            let a = BigUint::from_slice(aVec);
+            let b = BigUint::from_slice(bVec);
+            let c = BigUint::from_slice(cVec);
+
+            assert!(c - a == b);
+            assert!(c - b == a);
+        }
+    }
+
+    static mul_triples: &'static [(&'static [BigDigit],
+                                   &'static [BigDigit],
+                                   &'static [BigDigit])] = &[
+        (&[],               &[],               &[]),
+        (&[],               &[ 1],             &[]),
+        (&[ 2],             &[],               &[]),
+        (&[ 1],             &[ 1],             &[1]),
+        (&[ 2],             &[ 3],             &[ 6]),
+        (&[ 1],             &[ 1,  1,  1],     &[1, 1,  1]),
+        (&[ 1,  2,  3],     &[ 3],             &[ 3,  6,  9]),
+        (&[ 1,  1,  1],     &[-1],             &[-1, -1, -1]),
+        (&[ 1,  2,  3],     &[-1],             &[-1, -2, -2, 2]),
+        (&[ 1,  2,  3,  4], &[-1],             &[-1, -2, -2, -2, 3]),
+        (&[-1],             &[-1],             &[ 1, -2]),
+        (&[-1, -1],         &[-1],             &[ 1, -1, -2]),
+        (&[-1, -1, -1],     &[-1],             &[ 1, -1, -1, -2]),
+        (&[-1, -1, -1, -1], &[-1],             &[ 1, -1, -1, -1, -2]),
+        (&[-1/2 + 1],       &[ 2],             &[ 0,  1]),
+        (&[0, -1/2 + 1],    &[ 2],             &[ 0,  0,  1]),
+        (&[ 1,  2],         &[ 1,  2,  3],     &[1, 4,  7,  6]),
+        (&[-1, -1],         &[-1, -1, -1],     &[1, 0, -1, -2, -1]),
+        (&[-1, -1, -1],     &[-1, -1, -1, -1], &[1, 0,  0, -1, -2, -1, -1]),
+        (&[ 0,  0,  1],     &[ 1,  2,  3],     &[0, 0,  1,  2,  3]),
+        (&[ 0,  0,  1],     &[ 0,  0,  0,  1], &[0, 0,  0,  0,  0,  1])
+    ];
+
+    static div_rem_quadruples: &'static [(&'static [BigDigit],
+                                           &'static [BigDigit],
+                                           &'static [BigDigit],
+                                           &'static [BigDigit])]
+        = &[
+            (&[ 1],        &[ 2], &[],               &[1]),
+            (&[ 1,  1],    &[ 2], &[-1/2+1],         &[1]),
+            (&[ 1,  1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
+            (&[ 0,  1],    &[-1], &[1],              &[1]),
+            (&[-1, -1],    &[-2], &[2, 1],           &[3])
+        ];
+
+    #[test]
+    fn test_mul() {
+        for mul_triples.each |elm| {
+            let (aVec, bVec, cVec) = *elm;
+            let a = BigUint::from_slice(aVec);
+            let b = BigUint::from_slice(bVec);
+            let c = BigUint::from_slice(cVec);
+
+            assert!(a * b == c);
+            assert!(b * a == c);
+        }
+
+        for div_rem_quadruples.each |elm| {
+            let (aVec, bVec, cVec, dVec) = *elm;
+            let a = BigUint::from_slice(aVec);
+            let b = BigUint::from_slice(bVec);
+            let c = BigUint::from_slice(cVec);
+            let d = BigUint::from_slice(dVec);
+
+            assert!(a == b * c + d);
+            assert!(a == c * b + d);
+        }
+    }
+
+    #[test]
+    fn test_div_rem() {
+        for mul_triples.each |elm| {
+            let (aVec, bVec, cVec) = *elm;
+            let a = BigUint::from_slice(aVec);
+            let b = BigUint::from_slice(bVec);
+            let c = BigUint::from_slice(cVec);
+
+            if !a.is_zero() {
+                assert_eq!(c.div_rem(&a), (b.clone(), Zero::zero()));
+            }
+            if !b.is_zero() {
+                assert_eq!(c.div_rem(&b), (a.clone(), Zero::zero()));
+            }
+        }
+
+        for div_rem_quadruples.each |elm| {
+            let (aVec, bVec, cVec, dVec) = *elm;
+            let a = BigUint::from_slice(aVec);
+            let b = BigUint::from_slice(bVec);
+            let c = BigUint::from_slice(cVec);
+            let d = BigUint::from_slice(dVec);
+
+            if !b.is_zero() { assert!(a.div_rem(&b) == (c, d)); }
+        }
+    }
+
+    #[test]
+    fn test_gcd() {
+        fn check(a: uint, b: uint, c: uint) {
+            let big_a = BigUint::from_uint(a);
+            let big_b = BigUint::from_uint(b);
+            let big_c = BigUint::from_uint(c);
+
+            assert_eq!(big_a.gcd(&big_b), big_c);
+        }
+
+        check(10, 2, 2);
+        check(10, 3, 1);
+        check(0, 3, 3);
+        check(3, 3, 3);
+        check(56, 42, 14);
+    }
+
+    #[test]
+    fn test_lcm() {
+        fn check(a: uint, b: uint, c: uint) {
+            let big_a = BigUint::from_uint(a);
+            let big_b = BigUint::from_uint(b);
+            let big_c = BigUint::from_uint(c);
+
+            assert_eq!(big_a.lcm(&big_b), big_c);
+        }
+
+        check(1, 0, 0);
+        check(0, 1, 0);
+        check(1, 1, 1);
+        check(8, 9, 72);
+        check(11, 5, 55);
+        check(99, 17, 1683);
+    }
+
+    #[test]
+    fn test_is_even() {
+        assert!(FromStr::from_str::<BigUint>("1").get().is_odd());
+        assert!(FromStr::from_str::<BigUint>("2").get().is_even());
+        assert!(FromStr::from_str::<BigUint>("1000").get().is_even());
+        assert!(FromStr::from_str::<BigUint>("1000000000000000000000").get().is_even());
+        assert!(FromStr::from_str::<BigUint>("1000000000000000000001").get().is_odd());
+        assert!((BigUint::from_uint(1) << 64).is_even());
+        assert!(((BigUint::from_uint(1) << 64) + BigUint::from_uint(1)).is_odd());
+    }
+
+    fn to_str_pairs() -> ~[ (BigUint, ~[(uint, ~str)]) ] {
+        let bits = BigDigit::bits;
+        ~[( Zero::zero(), ~[
+            (2, ~"0"), (3, ~"0")
+        ]), ( BigUint::from_slice([ 0xff ]), ~[
+            (2,  ~"11111111"),
+            (3,  ~"100110"),
+            (4,  ~"3333"),
+            (5,  ~"2010"),
+            (6,  ~"1103"),
+            (7,  ~"513"),
+            (8,  ~"377"),
+            (9,  ~"313"),
+            (10, ~"255"),
+            (11, ~"212"),
+            (12, ~"193"),
+            (13, ~"168"),
+            (14, ~"143"),
+            (15, ~"120"),
+            (16, ~"ff")
+        ]), ( BigUint::from_slice([ 0xfff ]), ~[
+            (2,  ~"111111111111"),
+            (4,  ~"333333"),
+            (16, ~"fff")
+        ]), ( BigUint::from_slice([ 1, 2 ]), ~[
+            (2,
+             ~"10" +
+             str::from_chars(vec::from_elem(bits - 1, '0')) + "1"),
+            (4,
+             ~"2" +
+             str::from_chars(vec::from_elem(bits / 2 - 1, '0')) + "1"),
+            (10, match bits {
+                32 => ~"8589934593", 16 => ~"131073", _ => fail!()
+            }),
+            (16,
+             ~"2" +
+             str::from_chars(vec::from_elem(bits / 4 - 1, '0')) + "1")
+        ]), ( BigUint::from_slice([ 1, 2, 3 ]), ~[
+            (2,
+             ~"11" +
+             str::from_chars(vec::from_elem(bits - 2, '0')) + "10" +
+             str::from_chars(vec::from_elem(bits - 1, '0')) + "1"),
+            (4,
+             ~"3" +
+             str::from_chars(vec::from_elem(bits / 2 - 1, '0')) + "2" +
+             str::from_chars(vec::from_elem(bits / 2 - 1, '0')) + "1"),
+            (10, match bits {
+                32 => ~"55340232229718589441",
+                16 => ~"12885032961",
+                _ => fail!()
+            }),
+            (16, ~"3" +
+             str::from_chars(vec::from_elem(bits / 4 - 1, '0')) + "2" +
+             str::from_chars(vec::from_elem(bits / 4 - 1, '0')) + "1")
+        ]) ]
+    }
+
+    #[test]
+    fn test_to_str_radix() {
+        for to_str_pairs().each |num_pair| {
+            let &(n, rs) = num_pair;
+            for rs.each |str_pair| {
+                let &(radix, str) = str_pair;
+                assert_eq!(n.to_str_radix(radix), str);
+            }
+        }
+    }
+
+    #[test]
+    fn test_from_str_radix() {
+        for to_str_pairs().each |num_pair| {
+            let &(n, rs) = num_pair;
+            for rs.each |str_pair| {
+                let &(radix, str) = str_pair;
+                assert_eq!(&n, &FromStrRadix::from_str_radix(str, radix).get());
+            }
+        }
+
+        assert_eq!(FromStrRadix::from_str_radix::<BigUint>(~"Z", 10), None);
+        assert_eq!(FromStrRadix::from_str_radix::<BigUint>(~"_", 2), None);
+        assert_eq!(FromStrRadix::from_str_radix::<BigUint>(~"-1", 10), None);
+    }
+
+    #[test]
+    fn test_factor() {
+        fn factor(n: uint) -> BigUint {
+            let mut f= One::one::<BigUint>();
+            for uint::range(2, n + 1) |i| {
+                // FIXME(#6102): Assignment operator for BigInt causes ICE
+                // f *= BigUint::from_uint(i);
+                f = f * BigUint::from_uint(i);
+            }
+            return f;
+        }
+
+        fn check(n: uint, s: &str) {
+            let n = factor(n);
+            let ans = match FromStrRadix::from_str_radix(s, 10) {
+                Some(x) => x, None => fail!()
+            };
+            assert_eq!(n, ans);
+        }
+
+        check(3, "6");
+        check(10, "3628800");
+        check(20, "2432902008176640000");
+        check(30, "265252859812191058636308480000000");
+    }
+}
+
+#[cfg(test)]
+mod bigint_tests {
+    use super::*;
+    use core::cmp::{Less, Equal, Greater};
+    use core::num::{IntConvertible, Zero, One, FromStrRadix};
+
+    #[test]
+    fn test_from_biguint() {
+        fn check(inp_s: Sign, inp_n: uint, ans_s: Sign, ans_n: uint) {
+            let inp = BigInt::from_biguint(inp_s, BigUint::from_uint(inp_n));
+            let ans = BigInt { sign: ans_s, data: BigUint::from_uint(ans_n)};
+            assert_eq!(inp, ans);
+        }
+        check(Plus, 1, Plus, 1);
+        check(Plus, 0, Zero, 0);
+        check(Minus, 1, Minus, 1);
+        check(Zero, 1, Zero, 0);
+    }
+
+    #[test]
+    fn test_cmp() {
+        let vs = [ &[2], &[1, 1], &[2, 1], &[1, 1, 1] ];
+        let mut nums = vec::reversed(vs)
+            .map(|s| BigInt::from_slice(Minus, *s));
+        nums.push(Zero::zero());
+        nums.push_all_move(vs.map(|s| BigInt::from_slice(Plus, *s)));
+
+        for nums.eachi |i, ni| {
+            for vec::slice(nums, i, nums.len()).eachi |j0, nj| {
+                let j = i + j0;
+                if i == j {
+                    assert_eq!(ni.cmp(nj), Equal);
+                    assert_eq!(nj.cmp(ni), Equal);
+                    assert_eq!(ni, nj);
+                    assert!(!(ni != nj));
+                    assert!(ni <= nj);
+                    assert!(ni >= nj);
+                    assert!(!(ni < nj));
+                    assert!(!(ni > nj));
+                } else {
+                    assert_eq!(ni.cmp(nj), Less);
+                    assert_eq!(nj.cmp(ni), Greater);
+
+                    assert!(!(ni == nj));
+                    assert!(ni != nj);
+
+                    assert!(ni <= nj);
+                    assert!(!(ni >= nj));
+                    assert!(ni < nj);
+                    assert!(!(ni > nj));
+
+                    assert!(!(nj <= ni));
+                    assert!(nj >= ni);
+                    assert!(!(nj < ni));
+                    assert!(nj > ni);
+                }
+            }
+        }
+    }
+
+    #[test]
+    fn test_convert_int() {
+        fn check(b: BigInt, i: int) {
+            assert!(b == IntConvertible::from_int(i));
+            assert!(b.to_int() == i);
+        }
+
+        check(Zero::zero(), 0);
+        check(One::one(), 1);
+        check(BigInt::from_biguint(
+            Plus, BigUint::from_uint(int::max_value as uint)
+        ), int::max_value);
+
+        assert!(BigInt::from_biguint(
+            Plus, BigUint::from_uint(int::max_value as uint + 1)
+        ).to_int() == int::max_value);
+        assert!(BigInt::from_biguint(
+            Plus, BigUint::new(~[1, 2, 3])
+        ).to_int() == int::max_value);
+
+        check(BigInt::from_biguint(
+            Minus, BigUint::from_uint(-int::min_value as uint)
+        ), int::min_value);
+        assert!(BigInt::from_biguint(
+            Minus, BigUint::from_uint(-int::min_value as uint + 1)
+        ).to_int() == int::min_value);
+        assert!(BigInt::from_biguint(
+            Minus, BigUint::new(~[1, 2, 3])
+        ).to_int() == int::min_value);
+    }
+
+    #[test]
+    fn test_convert_uint() {
+        fn check(b: BigInt, u: uint) {
+            assert!(b == BigInt::from_uint(u));
+            assert!(b.to_uint() == u);
+        }
+
+        check(Zero::zero(), 0);
+        check(One::one(), 1);
+
+        check(
+            BigInt::from_biguint(Plus, BigUint::from_uint(uint::max_value)),
+            uint::max_value);
+        assert!(BigInt::from_biguint(
+            Plus, BigUint::new(~[1, 2, 3])
+        ).to_uint() == uint::max_value);
+
+        assert!(BigInt::from_biguint(
+            Minus, BigUint::from_uint(uint::max_value)
+        ).to_uint() == 0);
+        assert!(BigInt::from_biguint(
+            Minus, BigUint::new(~[1, 2, 3])
+        ).to_uint() == 0);
+    }
+
+    static sum_triples: &'static [(&'static [BigDigit],
+                                   &'static [BigDigit],
+                                   &'static [BigDigit])] = &[
+        (&[],          &[],       &[]),
+        (&[],          &[ 1],     &[ 1]),
+        (&[ 1],        &[ 1],     &[ 2]),
+        (&[ 1],        &[ 1,  1], &[ 2,  1]),
+        (&[ 1],        &[-1],     &[ 0,  1]),
+        (&[ 1],        &[-1, -1], &[ 0,  0, 1]),
+        (&[-1, -1],    &[-1, -1], &[-2, -1, 1]),
+        (&[ 1,  1, 1], &[-1, -1], &[ 0,  1, 2]),
+        (&[ 2,  2, 1], &[-1, -2], &[ 1,  1, 2])
+    ];
+
+    #[test]
+    fn test_add() {
+        for sum_triples.each |elm| {
+            let (aVec, bVec, cVec) = *elm;
+            let a = BigInt::from_slice(Plus, aVec);
+            let b = BigInt::from_slice(Plus, bVec);
+            let c = BigInt::from_slice(Plus, cVec);
+
+            assert!(a + b == c);
+            assert!(b + a == c);
+            assert!(c + (-a) == b);
+            assert!(c + (-b) == a);
+            assert!(a + (-c) == (-b));
+            assert!(b + (-c) == (-a));
+            assert!((-a) + (-b) == (-c))
+            assert!(a + (-a) == Zero::zero());
+        }
+    }
+
+    #[test]
+    fn test_sub() {
+        for sum_triples.each |elm| {
+            let (aVec, bVec, cVec) = *elm;
+            let a = BigInt::from_slice(Plus, aVec);
+            let b = BigInt::from_slice(Plus, bVec);
+            let c = BigInt::from_slice(Plus, cVec);
+
+            assert!(c - a == b);
+            assert!(c - b == a);
+            assert!((-b) - a == (-c))
+            assert!((-a) - b == (-c))
+            assert!(b - (-a) == c);
+            assert!(a - (-b) == c);
+            assert!((-c) - (-a) == (-b));
+            assert!(a - a == Zero::zero());
+        }
+    }
+
+    static mul_triples: &'static [(&'static [BigDigit],
+                                   &'static [BigDigit],
+                                   &'static [BigDigit])] = &[
+        (&[],               &[],               &[]),
+        (&[],               &[ 1],             &[]),
+        (&[ 2],             &[],               &[]),
+        (&[ 1],             &[ 1],             &[1]),
+        (&[ 2],             &[ 3],             &[ 6]),
+        (&[ 1],             &[ 1,  1,  1],     &[1, 1,  1]),
+        (&[ 1,  2,  3],     &[ 3],             &[ 3,  6,  9]),
+        (&[ 1,  1,  1],     &[-1],             &[-1, -1, -1]),
+        (&[ 1,  2,  3],     &[-1],             &[-1, -2, -2, 2]),
+        (&[ 1,  2,  3,  4], &[-1],             &[-1, -2, -2, -2, 3]),
+        (&[-1],             &[-1],             &[ 1, -2]),
+        (&[-1, -1],         &[-1],             &[ 1, -1, -2]),
+        (&[-1, -1, -1],     &[-1],             &[ 1, -1, -1, -2]),
+        (&[-1, -1, -1, -1], &[-1],             &[ 1, -1, -1, -1, -2]),
+        (&[-1/2 + 1],       &[ 2],             &[ 0,  1]),
+        (&[0, -1/2 + 1],    &[ 2],             &[ 0,  0,  1]),
+        (&[ 1,  2],         &[ 1,  2,  3],     &[1, 4,  7,  6]),
+        (&[-1, -1],         &[-1, -1, -1],     &[1, 0, -1, -2, -1]),
+        (&[-1, -1, -1],     &[-1, -1, -1, -1], &[1, 0,  0, -1, -2, -1, -1]),
+        (&[ 0,  0,  1],     &[ 1,  2,  3],     &[0, 0,  1,  2,  3]),
+        (&[ 0,  0,  1],     &[ 0,  0,  0,  1], &[0, 0,  0,  0,  0,  1])
+    ];
+
+    static div_rem_quadruples: &'static [(&'static [BigDigit],
+                                          &'static [BigDigit],
+                                          &'static [BigDigit],
+                                          &'static [BigDigit])]
+        = &[
+            (&[ 1],        &[ 2], &[],               &[1]),
+            (&[ 1,  1],    &[ 2], &[-1/2+1],         &[1]),
+            (&[ 1,  1, 1], &[ 2], &[-1/2+1, -1/2+1], &[1]),
+            (&[ 0,  1],    &[-1], &[1],              &[1]),
+            (&[-1, -1],    &[-2], &[2, 1],           &[3])
+        ];
+
+    #[test]
+    fn test_mul() {
+        for mul_triples.each |elm| {
+            let (aVec, bVec, cVec) = *elm;
+            let a = BigInt::from_slice(Plus, aVec);
+            let b = BigInt::from_slice(Plus, bVec);
+            let c = BigInt::from_slice(Plus, cVec);
+
+            assert!(a * b == c);
+            assert!(b * a == c);
+
+            assert!((-a) * b == -c);
+            assert!((-b) * a == -c);
+        }
+
+        for div_rem_quadruples.each |elm| {
+            let (aVec, bVec, cVec, dVec) = *elm;
+            let a = BigInt::from_slice(Plus, aVec);
+            let b = BigInt::from_slice(Plus, bVec);
+            let c = BigInt::from_slice(Plus, cVec);
+            let d = BigInt::from_slice(Plus, dVec);
+
+            assert!(a == b * c + d);
+            assert!(a == c * b + d);
+        }
+    }
+
+    #[test]
+    fn test_div_mod_floor() {
+        fn check_sub(a: &BigInt, b: &BigInt, ans_d: &BigInt, ans_m: &BigInt) {
+            let (d, m) = a.div_mod_floor(b);
+            if !m.is_zero() {
+                assert_eq!(m.sign, b.sign);
+            }
+            assert!(m.abs() <= b.abs());
+            assert!(*a == b * d + m);
+            assert!(d == *ans_d);
+            assert!(m == *ans_m);
+        }
+
+        fn check(a: &BigInt, b: &BigInt, d: &BigInt, m: &BigInt) {
+            if m.is_zero() {
+                check_sub(a, b, d, m);
+                check_sub(a, &b.neg(), &d.neg(), m);
+                check_sub(&a.neg(), b, &d.neg(), m);
+                check_sub(&a.neg(), &b.neg(), d, m);
+            } else {
+                check_sub(a, b, d, m);
+                check_sub(a, &b.neg(), &(d.neg() - One::one()), &(m - *b));
+                check_sub(&a.neg(), b, &(d.neg() - One::one()), &(b - *m));
+                check_sub(&a.neg(), &b.neg(), d, &m.neg());
+            }
+        }
+
+        for mul_triples.each |elm| {
+            let (aVec, bVec, cVec) = *elm;
+            let a = BigInt::from_slice(Plus, aVec);
+            let b = BigInt::from_slice(Plus, bVec);
+            let c = BigInt::from_slice(Plus, cVec);
+
+            if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
+            if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
+        }
+
+        for div_rem_quadruples.each |elm| {
+            let (aVec, bVec, cVec, dVec) = *elm;
+            let a = BigInt::from_slice(Plus, aVec);
+            let b = BigInt::from_slice(Plus, bVec);
+            let c = BigInt::from_slice(Plus, cVec);
+            let d = BigInt::from_slice(Plus, dVec);
+
+            if !b.is_zero() {
+                check(&a, &b, &c, &d);
+            }
+        }
+    }
+
+
+    #[test]
+    fn test_div_rem() {
+        fn check_sub(a: &BigInt, b: &BigInt, ans_q: &BigInt, ans_r: &BigInt) {
+            let (q, r) = a.div_rem(b);
+            if !r.is_zero() {
+                assert_eq!(r.sign, a.sign);
+            }
+            assert!(r.abs() <= b.abs());
+            assert!(*a == b * q + r);
+            assert!(q == *ans_q);
+            assert!(r == *ans_r);
+        }
+
+        fn check(a: &BigInt, b: &BigInt, q: &BigInt, r: &BigInt) {
+            check_sub(a, b, q, r);
+            check_sub(a, &b.neg(), &q.neg(), r);
+            check_sub(&a.neg(), b, &q.neg(), &r.neg());
+            check_sub(&a.neg(), &b.neg(), q, &r.neg());
+        }
+        for mul_triples.each |elm| {
+            let (aVec, bVec, cVec) = *elm;
+            let a = BigInt::from_slice(Plus, aVec);
+            let b = BigInt::from_slice(Plus, bVec);
+            let c = BigInt::from_slice(Plus, cVec);
+
+            if !a.is_zero() { check(&c, &a, &b, &Zero::zero()); }
+            if !b.is_zero() { check(&c, &b, &a, &Zero::zero()); }
+        }
+
+        for div_rem_quadruples.each |elm| {
+            let (aVec, bVec, cVec, dVec) = *elm;
+            let a = BigInt::from_slice(Plus, aVec);
+            let b = BigInt::from_slice(Plus, bVec);
+            let c = BigInt::from_slice(Plus, cVec);
+            let d = BigInt::from_slice(Plus, dVec);
+
+            if !b.is_zero() {
+                check(&a, &b, &c, &d);
+            }
+        }
+    }
+
+    #[test]
+    fn test_gcd() {
+        fn check(a: int, b: int, c: int) {
+            let big_a: BigInt = IntConvertible::from_int(a);
+            let big_b: BigInt = IntConvertible::from_int(b);
+            let big_c: BigInt = IntConvertible::from_int(c);
+
+            assert_eq!(big_a.gcd(&big_b), big_c);
+        }
+
+        check(10, 2, 2);
+        check(10, 3, 1);
+        check(0, 3, 3);
+        check(3, 3, 3);
+        check(56, 42, 14);
+        check(3, -3, 3);
+        check(-6, 3, 3);
+        check(-4, -2, 2);
+    }
+
+    #[test]
+    fn test_lcm() {
+        fn check(a: int, b: int, c: int) {
+            let big_a: BigInt = IntConvertible::from_int(a);
+            let big_b: BigInt = IntConvertible::from_int(b);
+            let big_c: BigInt = IntConvertible::from_int(c);
+
+            assert_eq!(big_a.lcm(&big_b), big_c);
+        }
+
+        check(1, 0, 0);
+        check(0, 1, 0);
+        check(1, 1, 1);
+        check(-1, 1, 1);
+        check(1, -1, 1);
+        check(-1, -1, 1);
+        check(8, 9, 72);
+        check(11, 5, 55);
+    }
+
+    #[test]
+    fn test_abs_sub() {
+        assert_eq!((-One::one::<BigInt>()).abs_sub(&One::one()), Zero::zero());
+        assert_eq!(One::one::<BigInt>().abs_sub(&One::one()), Zero::zero());
+        assert_eq!(One::one::<BigInt>().abs_sub(&Zero::zero()), One::one());
+        assert_eq!(One::one::<BigInt>().abs_sub(&-One::one::<BigInt>()),
+                   IntConvertible::from_int(2));
+    }
+
+    #[test]
+    fn test_to_str_radix() {
+        fn check(n: int, ans: &str) {
+            assert!(ans == IntConvertible::from_int::<BigInt>(n).to_str_radix(10));
+        }
+        check(10, "10");
+        check(1, "1");
+        check(0, "0");
+        check(-1, "-1");
+        check(-10, "-10");
+    }
+
+
+    #[test]
+    fn test_from_str_radix() {
+        fn check(s: &str, ans: Option<int>) {
+            let ans = ans.map(|&n| IntConvertible::from_int::<BigInt>(n));
+            assert_eq!(FromStrRadix::from_str_radix(s, 10), ans);
+        }
+        check("10", Some(10));
+        check("1", Some(1));
+        check("0", Some(0));
+        check("-1", Some(-1));
+        check("-10", Some(-10));
+        check("Z", None);
+        check("_", None);
+    }
+
+    #[test]
+    fn test_neg() {
+        assert!(-BigInt::new(Plus,  ~[1, 1, 1]) ==
+            BigInt::new(Minus, ~[1, 1, 1]));
+        assert!(-BigInt::new(Minus, ~[1, 1, 1]) ==
+            BigInt::new(Plus,  ~[1, 1, 1]));
+        assert_eq!(-Zero::zero::<BigInt>(), Zero::zero::<BigInt>());
+    }
+}
diff --git a/src/libextra/num/complex.rs b/src/libextra/num/complex.rs
new file mode 100644
index 00000000000..41d2b4a101c
--- /dev/null
+++ b/src/libextra/num/complex.rs
@@ -0,0 +1,309 @@
+// Copyright 2013 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+
+//! Complex numbers.
+
+use core::num::{Zero,One,ToStrRadix};
+
+// FIXME #1284: handle complex NaN & infinity etc. This
+// probably doesn't map to C's _Complex correctly.
+
+// FIXME #5734:: Need generic sin/cos for .to/from_polar().
+// FIXME #5735: Need generic sqrt to implement .norm().
+
+
+/// A complex number in Cartesian form.
+#[deriving(Eq,Clone)]
+pub struct Cmplx<T> {
+    re: T,
+    im: T
+}
+
+pub type Complex = Cmplx<float>;
+pub type Complex32 = Cmplx<f32>;
+pub type Complex64 = Cmplx<f64>;
+
+impl<T: Copy + Num> Cmplx<T> {
+    /// Create a new Cmplx
+    #[inline]
+    pub fn new(re: T, im: T) -> Cmplx<T> {
+        Cmplx { re: re, im: im }
+    }
+
+    /**
+    Returns the square of the norm (since `T` doesn't necessarily
+    have a sqrt function), i.e. `re^2 + im^2`.
+    */
+    #[inline]
+    pub fn norm_sqr(&self) -> T {
+        self.re * self.re + self.im * self.im
+    }
+
+
+    /// Returns the complex conjugate. i.e. `re - i im`
+    #[inline]
+    pub fn conj(&self) -> Cmplx<T> {
+        Cmplx::new(self.re, -self.im)
+    }
+
+
+    /// Multiplies `self` by the scalar `t`.
+    #[inline]
+    pub fn scale(&self, t: T) -> Cmplx<T> {
+        Cmplx::new(self.re * t, self.im * t)
+    }
+
+    /// Divides `self` by the scalar `t`.
+    #[inline]
+    pub fn unscale(&self, t: T) -> Cmplx<T> {
+        Cmplx::new(self.re / t, self.im / t)
+    }
+
+    /// Returns `1/self`
+    #[inline]
+    pub fn inv(&self) -> Cmplx<T> {
+        let norm_sqr = self.norm_sqr();
+        Cmplx::new(self.re / norm_sqr,
+                    -self.im / norm_sqr)
+    }
+}
+
+/* arithmetic */
+// (a + i b) + (c + i d) == (a + c) + i (b + d)
+impl<T: Copy + Num> Add<Cmplx<T>, Cmplx<T>> for Cmplx<T> {
+    #[inline]
+    fn add(&self, other: &Cmplx<T>) -> Cmplx<T> {
+        Cmplx::new(self.re + other.re, self.im + other.im)
+    }
+}
+// (a + i b) - (c + i d) == (a - c) + i (b - d)
+impl<T: Copy + Num> Sub<Cmplx<T>, Cmplx<T>> for Cmplx<T> {
+    #[inline]
+    fn sub(&self, other: &Cmplx<T>) -> Cmplx<T> {
+        Cmplx::new(self.re - other.re, self.im - other.im)
+    }
+}
+// (a + i b) * (c + i d) == (a*c - b*d) + i (a*d + b*c)
+impl<T: Copy + Num> Mul<Cmplx<T>, Cmplx<T>> for Cmplx<T> {
+    #[inline]
+    fn mul(&self, other: &Cmplx<T>) -> Cmplx<T> {
+        Cmplx::new(self.re*other.re - self.im*other.im,
+                     self.re*other.im + self.im*other.re)
+    }
+}
+
+// (a + i b) / (c + i d) == [(a + i b) * (c - i d)] / (c*c + d*d)
+//   == [(a*c + b*d) / (c*c + d*d)] + i [(b*c - a*d) / (c*c + d*d)]
+impl<T: Copy + Num> Div<Cmplx<T>, Cmplx<T>> for Cmplx<T> {
+    #[inline]
+    fn div(&self, other: &Cmplx<T>) -> Cmplx<T> {
+        let norm_sqr = other.norm_sqr();
+        Cmplx::new((self.re*other.re + self.im*other.im) / norm_sqr,
+                     (self.im*other.re - self.re*other.im) / norm_sqr)
+    }
+}
+
+impl<T: Copy + Num> Neg<Cmplx<T>> for Cmplx<T> {
+    #[inline]
+    fn neg(&self) -> Cmplx<T> {
+        Cmplx::new(-self.re, -self.im)
+    }
+}
+
+/* constants */
+impl<T: Copy + Num> Zero for Cmplx<T> {
+    #[inline]
+    fn zero() -> Cmplx<T> {
+        Cmplx::new(Zero::zero(), Zero::zero())
+    }
+
+    #[inline]
+    fn is_zero(&self) -> bool {
+        *self == Zero::zero()
+    }
+}
+
+impl<T: Copy + Num> One for Cmplx<T> {
+    #[inline]
+    fn one() -> Cmplx<T> {
+        Cmplx::new(One::one(), Zero::zero())
+    }
+}
+
+/* string conversions */
+impl<T: ToStr + Num + Ord> ToStr for Cmplx<T> {
+    fn to_str(&self) -> ~str {
+        if self.im < Zero::zero() {
+            fmt!("%s-%si", self.re.to_str(), (-self.im).to_str())
+        } else {
+            fmt!("%s+%si", self.re.to_str(), self.im.to_str())
+        }
+    }
+}
+
+impl<T: ToStrRadix + Num + Ord> ToStrRadix for Cmplx<T> {
+    fn to_str_radix(&self, radix: uint) -> ~str {
+        if self.im < Zero::zero() {
+            fmt!("%s-%si", self.re.to_str_radix(radix), (-self.im).to_str_radix(radix))
+        } else {
+            fmt!("%s+%si", self.re.to_str_radix(radix), self.im.to_str_radix(radix))
+        }
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+    use core::num::{Zero,One};
+
+    pub static _0_0i : Complex = Cmplx { re: 0f, im: 0f };
+    pub static _1_0i : Complex = Cmplx { re: 1f, im: 0f };
+    pub static _1_1i : Complex = Cmplx { re: 1f, im: 1f };
+    pub static _0_1i : Complex = Cmplx { re: 0f, im: 1f };
+    pub static _neg1_1i : Complex = Cmplx { re: -1f, im: 1f };
+    pub static _05_05i : Complex = Cmplx { re: 0.5f, im: 0.5f };
+    pub static all_consts : [Complex, .. 5] = [_0_0i, _1_0i, _1_1i, _neg1_1i, _05_05i];
+
+    #[test]
+    fn test_consts() {
+        // check our constants are what Cmplx::new creates
+        fn test(c : Complex, r : float, i: float) {
+            assert_eq!(c, Cmplx::new(r,i));
+        }
+        test(_0_0i, 0f, 0f);
+        test(_1_0i, 1f, 0f);
+        test(_1_1i, 1f, 1f);
+        test(_neg1_1i, -1f, 1f);
+        test(_05_05i, 0.5f, 0.5f);
+
+        assert_eq!(_0_0i, Zero::zero());
+        assert_eq!(_1_0i, One::one());
+    }
+
+    #[test]
+    fn test_norm_sqr() {
+        fn test(c: Complex, ns: float) {
+            assert_eq!(c.norm_sqr(), ns);
+        }
+        test(_0_0i, 0f);
+        test(_1_0i, 1f);
+        test(_1_1i, 2f);
+        test(_neg1_1i, 2f);
+        test(_05_05i, 0.5f);
+    }
+
+    #[test]
+    fn test_scale_unscale() {
+        assert_eq!(_05_05i.scale(2f), _1_1i);
+        assert_eq!(_1_1i.unscale(2f), _05_05i);
+        for all_consts.each |&c| {
+            assert_eq!(c.scale(2f).unscale(2f), c);
+        }
+    }
+
+    #[test]
+    fn test_conj() {
+        for all_consts.each |&c| {
+            assert_eq!(c.conj(), Cmplx::new(c.re, -c.im));
+            assert_eq!(c.conj().conj(), c);
+        }
+    }
+
+    #[test]
+    fn test_inv() {
+        assert_eq!(_1_1i.inv(), _05_05i.conj());
+        assert_eq!(_1_0i.inv(), _1_0i.inv());
+    }
+
+    #[test]
+    #[should_fail]
+    #[ignore]
+    fn test_inv_zero() {
+        // FIXME #5736: should this really fail, or just NaN?
+        _0_0i.inv();
+    }
+
+
+    mod arith {
+        use super::*;
+        use core::num::Zero;
+
+        #[test]
+        fn test_add() {
+            assert_eq!(_05_05i + _05_05i, _1_1i);
+            assert_eq!(_0_1i + _1_0i, _1_1i);
+            assert_eq!(_1_0i + _neg1_1i, _0_1i);
+
+            for all_consts.each |&c| {
+                assert_eq!(_0_0i + c, c);
+                assert_eq!(c + _0_0i, c);
+            }
+        }
+
+        #[test]
+        fn test_sub() {
+            assert_eq!(_05_05i - _05_05i, _0_0i);
+            assert_eq!(_0_1i - _1_0i, _neg1_1i);
+            assert_eq!(_0_1i - _neg1_1i, _1_0i);
+
+            for all_consts.each |&c| {
+                assert_eq!(c - _0_0i, c);
+                assert_eq!(c - c, _0_0i);
+            }
+        }
+
+        #[test]
+        fn test_mul() {
+            assert_eq!(_05_05i * _05_05i, _0_1i.unscale(2f));
+            assert_eq!(_1_1i * _0_1i, _neg1_1i);
+
+            // i^2 & i^4
+            assert_eq!(_0_1i * _0_1i, -_1_0i);
+            assert_eq!(_0_1i * _0_1i * _0_1i * _0_1i, _1_0i);
+
+            for all_consts.each |&c| {
+                assert_eq!(c * _1_0i, c);
+                assert_eq!(_1_0i * c, c);
+            }
+        }
+        #[test]
+        fn test_div() {
+            assert_eq!(_neg1_1i / _0_1i, _1_1i);
+            for all_consts.each |&c| {
+                if c != Zero::zero() {
+                    assert_eq!(c / c, _1_0i);
+                }
+            }
+        }
+        #[test]
+        fn test_neg() {
+            assert_eq!(-_1_0i + _0_1i, _neg1_1i);
+            assert_eq!((-_0_1i) * _0_1i, _1_0i);
+            for all_consts.each |&c| {
+                assert_eq!(-(-c), c);
+            }
+        }
+    }
+
+    #[test]
+    fn test_to_str() {
+        fn test(c : Complex, s: ~str) {
+            assert_eq!(c.to_str(), s);
+        }
+        test(_0_0i, ~"0+0i");
+        test(_1_0i, ~"1+0i");
+        test(_0_1i, ~"0+1i");
+        test(_1_1i, ~"1+1i");
+        test(_neg1_1i, ~"-1+1i");
+        test(-_neg1_1i, ~"1-1i");
+        test(_05_05i, ~"0.5+0.5i");
+    }
+}
diff --git a/src/libextra/num/rational.rs b/src/libextra/num/rational.rs
new file mode 100644
index 00000000000..d57c642c5a2
--- /dev/null
+++ b/src/libextra/num/rational.rs
@@ -0,0 +1,531 @@
+// Copyright 2013 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+
+//! Rational numbers
+
+use core::num::{Zero,One,ToStrRadix,FromStrRadix,Round};
+use core::from_str::FromStr;
+use super::bigint::BigInt;
+
+/// Represents the ratio between 2 numbers.
+#[deriving(Clone)]
+pub struct Ratio<T> {
+    numer: T,
+    denom: T
+}
+
+/// Alias for a `Ratio` of machine-sized integers.
+pub type Rational = Ratio<int>;
+pub type Rational32 = Ratio<i32>;
+pub type Rational64 = Ratio<i64>;
+
+/// Alias for arbitrary precision rationals.
+pub type BigRational = Ratio<BigInt>;
+
+impl<T: Clone + Integer + Ord>
+    Ratio<T> {
+    /// Create a ratio representing the integer `t`.
+    #[inline(always)]
+    pub fn from_integer(t: T) -> Ratio<T> {
+        Ratio::new_raw(t, One::one())
+    }
+
+    /// Create a ratio without checking for `denom == 0` or reducing.
+    #[inline(always)]
+    pub fn new_raw(numer: T, denom: T) -> Ratio<T> {
+        Ratio { numer: numer, denom: denom }
+    }
+
+    // Create a new Ratio. Fails if `denom == 0`.
+    #[inline(always)]
+    pub fn new(numer: T, denom: T) -> Ratio<T> {
+        if denom == Zero::zero() {
+            fail!("denominator == 0");
+        }
+        let mut ret = Ratio::new_raw(numer, denom);
+        ret.reduce();
+        ret
+    }
+
+    /// Put self into lowest terms, with denom > 0.
+    fn reduce(&mut self) {
+        let g : T = self.numer.gcd(&self.denom);
+
+        // FIXME(#6050): overloaded operators force moves with generic types
+        // self.numer /= g;
+        self.numer = self.numer / g;
+        // FIXME(#6050): overloaded operators force moves with generic types
+        // self.denom /= g;
+        self.denom = self.denom / g;
+
+        // keep denom positive!
+        if self.denom < Zero::zero() {
+            self.numer = -self.numer;
+            self.denom = -self.denom;
+        }
+    }
+
+    /// Return a `reduce`d copy of self.
+    fn reduced(&self) -> Ratio<T> {
+        let mut ret = self.clone();
+        ret.reduce();
+        ret
+    }
+}
+
+/* Comparisons */
+
+// comparing a/b and c/d is the same as comparing a*d and b*c, so we
+// abstract that pattern. The following macro takes a trait and either
+// a comma-separated list of "method name -> return value" or just
+// "method name" (return value is bool in that case)
+macro_rules! cmp_impl {
+    (impl $imp:ident, $($method:ident),+) => {
+        cmp_impl!(impl $imp, $($method -> bool),+)
+    };
+    // return something other than a Ratio<T>
+    (impl $imp:ident, $($method:ident -> $res:ty),+) => {
+        impl<T: Mul<T,T> + $imp> $imp for Ratio<T> {
+            $(
+                #[inline]
+                fn $method(&self, other: &Ratio<T>) -> $res {
+                    (self.numer * other.denom). $method (&(self.denom*other.numer))
+                }
+            )+
+        }
+    };
+}
+cmp_impl!(impl Eq, eq, ne)
+cmp_impl!(impl TotalEq, equals)
+cmp_impl!(impl Ord, lt, gt, le, ge)
+cmp_impl!(impl TotalOrd, cmp -> cmp::Ordering)
+
+/* Arithmetic */
+// a/b * c/d = (a*c)/(b*d)
+impl<T: Clone + Integer + Ord>
+    Mul<Ratio<T>,Ratio<T>> for Ratio<T> {
+    #[inline]
+    fn mul(&self, rhs: &Ratio<T>) -> Ratio<T> {
+        Ratio::new(self.numer * rhs.numer, self.denom * rhs.denom)
+    }
+}
+
+// (a/b) / (c/d) = (a*d)/(b*c)
+impl<T: Clone + Integer + Ord>
+    Div<Ratio<T>,Ratio<T>> for Ratio<T> {
+    #[inline]
+    fn div(&self, rhs: &Ratio<T>) -> Ratio<T> {
+        Ratio::new(self.numer * rhs.denom, self.denom * rhs.numer)
+    }
+}
+
+// Abstracts the a/b `op` c/d = (a*d `op` b*d) / (b*d) pattern
+macro_rules! arith_impl {
+    (impl $imp:ident, $method:ident) => {
+        impl<T: Clone + Integer + Ord>
+            $imp<Ratio<T>,Ratio<T>> for Ratio<T> {
+            #[inline]
+            fn $method(&self, rhs: &Ratio<T>) -> Ratio<T> {
+                Ratio::new((self.numer * rhs.denom).$method(&(self.denom * rhs.numer)),
+                           self.denom * rhs.denom)
+            }
+        }
+    }
+}
+
+// a/b + c/d = (a*d + b*c)/(b*d
+arith_impl!(impl Add, add)
+
+// a/b - c/d = (a*d - b*c)/(b*d)
+arith_impl!(impl Sub, sub)
+
+// a/b % c/d = (a*d % b*c)/(b*d)
+arith_impl!(impl Rem, rem)
+
+impl<T: Clone + Integer + Ord>
+    Neg<Ratio<T>> for Ratio<T> {
+    #[inline]
+    fn neg(&self) -> Ratio<T> {
+        Ratio::new_raw(-self.numer, self.denom.clone())
+    }
+}
+
+/* Constants */
+impl<T: Clone + Integer + Ord>
+    Zero for Ratio<T> {
+    #[inline]
+    fn zero() -> Ratio<T> {
+        Ratio::new_raw(Zero::zero(), One::one())
+    }
+
+    #[inline]
+    fn is_zero(&self) -> bool {
+        *self == Zero::zero()
+    }
+}
+
+impl<T: Clone + Integer + Ord>
+    One for Ratio<T> {
+    #[inline]
+    fn one() -> Ratio<T> {
+        Ratio::new_raw(One::one(), One::one())
+    }
+}
+
+impl<T: Clone + Integer + Ord>
+    Num for Ratio<T> {}
+
+/* Utils */
+impl<T: Clone + Integer + Ord>
+    Round for Ratio<T> {
+
+    fn floor(&self) -> Ratio<T> {
+        if *self < Zero::zero() {
+            Ratio::from_integer((self.numer - self.denom + One::one()) / self.denom)
+        } else {
+            Ratio::from_integer(self.numer / self.denom)
+        }
+    }
+
+    fn ceil(&self) -> Ratio<T> {
+        if *self < Zero::zero() {
+            Ratio::from_integer(self.numer / self.denom)
+        } else {
+            Ratio::from_integer((self.numer + self.denom - One::one()) / self.denom)
+        }
+    }
+
+    #[inline(always)]
+    fn round(&self) -> Ratio<T> {
+        if *self < Zero::zero() {
+            Ratio::from_integer((self.numer - self.denom + One::one()) / self.denom)
+        } else {
+            Ratio::from_integer((self.numer + self.denom - One::one()) / self.denom)
+        }
+    }
+
+    #[inline(always)]
+    fn trunc(&self) -> Ratio<T> {
+        Ratio::from_integer(self.numer / self.denom)
+    }
+
+    fn fract(&self) -> Ratio<T> {
+        Ratio::new_raw(self.numer % self.denom, self.denom.clone())
+    }
+}
+
+impl<T: Clone + Integer + Ord> Fractional for Ratio<T> {
+    #[inline]
+    fn recip(&self) -> Ratio<T> {
+        Ratio::new_raw(self.denom.clone(), self.numer.clone())
+    }
+}
+
+/* String conversions */
+impl<T: ToStr> ToStr for Ratio<T> {
+    /// Renders as `numer/denom`.
+    fn to_str(&self) -> ~str {
+        fmt!("%s/%s", self.numer.to_str(), self.denom.to_str())
+    }
+}
+impl<T: ToStrRadix> ToStrRadix for Ratio<T> {
+    /// Renders as `numer/denom` where the numbers are in base `radix`.
+    fn to_str_radix(&self, radix: uint) -> ~str {
+        fmt!("%s/%s", self.numer.to_str_radix(radix), self.denom.to_str_radix(radix))
+    }
+}
+
+impl<T: FromStr + Clone + Integer + Ord>
+    FromStr for Ratio<T> {
+    /// Parses `numer/denom`.
+    fn from_str(s: &str) -> Option<Ratio<T>> {
+        let split = vec::build(|push| {
+            for str::each_splitn_char(s, '/', 1) |s| {
+                push(s.to_owned());
+            }
+        });
+        if split.len() < 2 { return None; }
+        do FromStr::from_str::<T>(split[0]).chain |a| {
+            do FromStr::from_str::<T>(split[1]).chain |b| {
+                Some(Ratio::new(a.clone(), b.clone()))
+            }
+        }
+    }
+}
+impl<T: FromStrRadix + Clone + Integer + Ord>
+    FromStrRadix for Ratio<T> {
+    /// Parses `numer/denom` where the numbers are in base `radix`.
+    fn from_str_radix(s: &str, radix: uint) -> Option<Ratio<T>> {
+        let split = vec::build(|push| {
+            for str::each_splitn_char(s, '/', 1) |s| {
+                push(s.to_owned());
+            }
+        });
+        if split.len() < 2 { None }
+        else {
+            do FromStrRadix::from_str_radix::<T>(split[0], radix).chain |a| {
+                do FromStrRadix::from_str_radix::<T>(split[1], radix).chain |b| {
+                    Some(Ratio::new(a.clone(), b.clone()))
+                }
+            }
+        }
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+    use core::num::{Zero,One,FromStrRadix,IntConvertible};
+    use core::from_str::FromStr;
+
+    pub static _0 : Rational = Ratio { numer: 0, denom: 1};
+    pub static _1 : Rational = Ratio { numer: 1, denom: 1};
+    pub static _2: Rational = Ratio { numer: 2, denom: 1};
+    pub static _1_2: Rational = Ratio { numer: 1, denom: 2};
+    pub static _3_2: Rational = Ratio { numer: 3, denom: 2};
+    pub static _neg1_2: Rational =  Ratio { numer: -1, denom: 2};
+
+    pub fn to_big(n: Rational) -> BigRational {
+        Ratio::new(
+            IntConvertible::from_int(n.numer),
+            IntConvertible::from_int(n.denom)
+        )
+    }
+
+    #[test]
+    fn test_test_constants() {
+        // check our constants are what Ratio::new etc. would make.
+        assert_eq!(_0, Zero::zero());
+        assert_eq!(_1, One::one());
+        assert_eq!(_2, Ratio::from_integer(2));
+        assert_eq!(_1_2, Ratio::new(1,2));
+        assert_eq!(_3_2, Ratio::new(3,2));
+        assert_eq!(_neg1_2, Ratio::new(-1,2));
+    }
+
+    #[test]
+    fn test_new_reduce() {
+        let one22 = Ratio::new(2i,2);
+
+        assert_eq!(one22, One::one());
+    }
+    #[test]
+    #[should_fail]
+    fn test_new_zero() {
+        let _a = Ratio::new(1,0);
+    }
+
+
+    #[test]
+    fn test_cmp() {
+        assert!(_0 == _0 && _1 == _1);
+        assert!(_0 != _1 && _1 != _0);
+        assert!(_0 < _1 && !(_1 < _0));
+        assert!(_1 > _0 && !(_0 > _1));
+
+        assert!(_0 <= _0 && _1 <= _1);
+        assert!(_0 <= _1 && !(_1 <= _0));
+
+        assert!(_0 >= _0 && _1 >= _1);
+        assert!(_1 >= _0 && !(_0 >= _1));
+    }
+
+
+    mod arith {
+        use super::*;
+        use super::super::*;
+
+
+        #[test]
+        fn test_add() {
+            fn test(a: Rational, b: Rational, c: Rational) {
+                assert_eq!(a + b, c);
+                assert_eq!(to_big(a) + to_big(b), to_big(c));
+            }
+
+            test(_1, _1_2, _3_2);
+            test(_1, _1, _2);
+            test(_1_2, _3_2, _2);
+            test(_1_2, _neg1_2, _0);
+        }
+
+        #[test]
+        fn test_sub() {
+            fn test(a: Rational, b: Rational, c: Rational) {
+                assert_eq!(a - b, c);
+                assert_eq!(to_big(a) - to_big(b), to_big(c))
+            }
+
+            test(_1, _1_2, _1_2);
+            test(_3_2, _1_2, _1);
+            test(_1, _neg1_2, _3_2);
+        }
+
+        #[test]
+        fn test_mul() {
+            fn test(a: Rational, b: Rational, c: Rational) {
+                assert_eq!(a * b, c);
+                assert_eq!(to_big(a) * to_big(b), to_big(c))
+            }
+
+            test(_1, _1_2, _1_2);
+            test(_1_2, _3_2, Ratio::new(3,4));
+            test(_1_2, _neg1_2, Ratio::new(-1, 4));
+        }
+
+        #[test]
+        fn test_div() {
+            fn test(a: Rational, b: Rational, c: Rational) {
+                assert_eq!(a / b, c);
+                assert_eq!(to_big(a) / to_big(b), to_big(c))
+            }
+
+            test(_1, _1_2, _2);
+            test(_3_2, _1_2, _1 + _2);
+            test(_1, _neg1_2, _neg1_2 + _neg1_2 + _neg1_2 + _neg1_2);
+        }
+
+        #[test]
+        fn test_rem() {
+            fn test(a: Rational, b: Rational, c: Rational) {
+                assert_eq!(a % b, c);
+                assert_eq!(to_big(a) % to_big(b), to_big(c))
+            }
+
+            test(_3_2, _1, _1_2);
+            test(_2, _neg1_2, _0);
+            test(_1_2, _2,  _1_2);
+        }
+
+        #[test]
+        fn test_neg() {
+            fn test(a: Rational, b: Rational) {
+                assert_eq!(-a, b);
+                assert_eq!(-to_big(a), to_big(b))
+            }
+
+            test(_0, _0);
+            test(_1_2, _neg1_2);
+            test(-_1, _1);
+        }
+        #[test]
+        fn test_zero() {
+            assert_eq!(_0 + _0, _0);
+            assert_eq!(_0 * _0, _0);
+            assert_eq!(_0 * _1, _0);
+            assert_eq!(_0 / _neg1_2, _0);
+            assert_eq!(_0 - _0, _0);
+        }
+        #[test]
+        #[should_fail]
+        fn test_div_0() {
+            let _a =  _1 / _0;
+        }
+    }
+
+    #[test]
+    fn test_round() {
+        assert_eq!(_1_2.ceil(), _1);
+        assert_eq!(_1_2.floor(), _0);
+        assert_eq!(_1_2.round(), _1);
+        assert_eq!(_1_2.trunc(), _0);
+
+        assert_eq!(_neg1_2.ceil(), _0);
+        assert_eq!(_neg1_2.floor(), -_1);
+        assert_eq!(_neg1_2.round(), -_1);
+        assert_eq!(_neg1_2.trunc(), _0);
+
+        assert_eq!(_1.ceil(), _1);
+        assert_eq!(_1.floor(), _1);
+        assert_eq!(_1.round(), _1);
+        assert_eq!(_1.trunc(), _1);
+    }
+
+    #[test]
+    fn test_fract() {
+        assert_eq!(_1.fract(), _0);
+        assert_eq!(_neg1_2.fract(), _neg1_2);
+        assert_eq!(_1_2.fract(), _1_2);
+        assert_eq!(_3_2.fract(), _1_2);
+    }
+
+    #[test]
+    fn test_recip() {
+        assert_eq!(_1 * _1.recip(), _1);
+        assert_eq!(_2 * _2.recip(), _1);
+        assert_eq!(_1_2 * _1_2.recip(), _1);
+        assert_eq!(_3_2 * _3_2.recip(), _1);
+        assert_eq!(_neg1_2 * _neg1_2.recip(), _1);
+    }
+
+    #[test]
+    fn test_to_from_str() {
+        fn test(r: Rational, s: ~str) {
+            assert_eq!(FromStr::from_str(s), Some(r));
+            assert_eq!(r.to_str(), s);
+        }
+        test(_1, ~"1/1");
+        test(_0, ~"0/1");
+        test(_1_2, ~"1/2");
+        test(_3_2, ~"3/2");
+        test(_2, ~"2/1");
+        test(_neg1_2, ~"-1/2");
+    }
+    #[test]
+    fn test_from_str_fail() {
+        fn test(s: &str) {
+            assert_eq!(FromStr::from_str::<Rational>(s), None);
+        }
+
+        for ["0 /1", "abc", "", "1/", "--1/2","3/2/1"].each |&s| {
+            test(s);
+        }
+    }
+
+    #[test]
+    fn test_to_from_str_radix() {
+        fn test(r: Rational, s: ~str, n: uint) {
+            assert_eq!(FromStrRadix::from_str_radix(s, n), Some(r));
+            assert_eq!(r.to_str_radix(n), s);
+        }
+        fn test3(r: Rational, s: ~str) { test(r, s, 3) }
+        fn test16(r: Rational, s: ~str) { test(r, s, 16) }
+
+        test3(_1, ~"1/1");
+        test3(_0, ~"0/1");
+        test3(_1_2, ~"1/2");
+        test3(_3_2, ~"10/2");
+        test3(_2, ~"2/1");
+        test3(_neg1_2, ~"-1/2");
+        test3(_neg1_2 / _2, ~"-1/11");
+
+        test16(_1, ~"1/1");
+        test16(_0, ~"0/1");
+        test16(_1_2, ~"1/2");
+        test16(_3_2, ~"3/2");
+        test16(_2, ~"2/1");
+        test16(_neg1_2, ~"-1/2");
+        test16(_neg1_2 / _2, ~"-1/4");
+        test16(Ratio::new(13,15), ~"d/f");
+        test16(_1_2*_1_2*_1_2*_1_2, ~"1/10");
+    }
+
+    #[test]
+    fn test_from_str_radix_fail() {
+        fn test(s: &str) {
+            assert_eq!(FromStrRadix::from_str_radix::<Rational>(s, 3), None);
+        }
+
+        for ["0 /1", "abc", "", "1/", "--1/2","3/2/1", "3/2"].each |&s| {
+            test(s);
+        }
+    }
+}