auto merge of #5733 : dbaupp/rust/std-complex-rational, r=thestinger

This adds two generic data types, `Ratio` and `Cmplx` (and some aliases for useful instances, e.g. `Ratio<int>` and `Cmplx<f64>`), and basic arithmetic support, as well as `.to_str` (for both) and `.from_str` (for rational).

The complex number implementation doesn't solve #1284 other than getting something into the libraries, specifically it doesn't even try to address C interop. If the complex part of this gets merged, maybe it's worth closing that issue and reopening more specific issue(s) about the failings.

The implementations can be fleshed out when the numeric traits stabilise (and trait inheritance works).

3 files changed, 2473 insertions, 0 deletions

diff --git a/src/libstd/num/bigint.rs b/src/libstd/num/bigint.rs
new file mode 100644
index 00000000000..35b1a28a465
--- /dev/null
+++ b/src/libstd/num/bigint.rs
@@ -0,0 +1,1647 @@
+// 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};
+use core::num::{IntConvertible, Zero, One};
+use core::*;
+
+/**
+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;
+
+    priv fn get_hi(n: uint) -> BigDigit { (n >> bits) as BigDigit }
+    priv fn get_lo(n: uint) -> BigDigit { (n & lo_mask) as BigDigit }
+
+    /// Split one machine sized unsigned integer into two BigDigits.
+    pub fn from_uint(n: uint) -> (BigDigit, BigDigit) {
+        (get_hi(n), get_lo(n))
+    }
+
+    /// Join two BigDigits into one machine sized unsigned integer
+    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).
+*/
+pub struct BigUint {
+    priv data: ~[BigDigit]
+}
+
+impl Eq for BigUint {
+    fn eq(&self, other: &BigUint) -> bool { self.cmp(other) == 0 }
+    fn ne(&self, other: &BigUint) -> bool { self.cmp(other) != 0 }
+}
+
+impl Ord for BigUint {
+    fn lt(&self, other: &BigUint) -> bool { self.cmp(other) <  0 }
+    fn le(&self, other: &BigUint) -> bool { self.cmp(other) <= 0 }
+    fn ge(&self, other: &BigUint) -> bool { self.cmp(other) >= 0 }
+    fn gt(&self, other: &BigUint) -> bool { self.cmp(other) >  0 }
+}
+
+impl ToStr for BigUint {
+    fn to_str(&self) -> ~str { self.to_str_radix(10) }
+}
+
+impl from_str::FromStr for BigUint {
+    fn from_str(s: &str) -> Option<BigUint> {
+        BigUint::from_str_radix(s, 10)
+    }
+}
+
+impl Shl<uint, BigUint> for BigUint {
+    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 {
+    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 {
+    fn zero() -> BigUint { BigUint::new(~[]) }
+}
+
+impl One for BigUint {
+    pub fn one() -> BigUint { BigUint::new(~[1]) }
+}
+
+impl Add<BigUint, BigUint> for BigUint {
+    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 {
+    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!(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);
+            if s1 * s2 < 0 {
+                hh + ll + (n1 * n2)
+            } else if s1 * s2 > 0 {
+                hh + ll - (n1 * n2)
+            } else {
+                hh + ll
+            }
+        };
+
+        return ll + mm.shl_unit(half_len) + hh.shl_unit(half_len * 2);
+
+        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]);
+        }
+
+        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)));
+        }
+
+        fn sub_sign(a: BigUint, b: BigUint) -> (int, BigUint) {
+            match a.cmp(&b) {
+                s if s < 0 => (s, b - a),
+                s if s > 0 => (s, a - b),
+                _          => (0, Zero::zero())
+            }
+        }
+    }
+}
+
+impl Div<BigUint, BigUint> for BigUint {
+    fn div(&self, other: &BigUint) -> BigUint {
+        let (d, _) = self.divmod(other);
+        return d;
+    }
+}
+
+impl Modulo<BigUint, BigUint> for BigUint {
+    fn modulo(&self, other: &BigUint) -> BigUint {
+        let (_, m) = self.divmod(other);
+        return m;
+    }
+}
+
+impl Neg<BigUint> for BigUint {
+    fn neg(&self) -> BigUint { fail!() }
+}
+
+impl IntConvertible for BigUint {
+    fn to_int(&self) -> int {
+        uint::min(self.to_uint(), int::max_value as uint) as int
+    }
+
+    fn from_int(n: int) -> BigUint {
+        if (n < 0) { Zero::zero() } else { BigUint::from_uint(n as uint) }
+    }
+}
+
+pub impl BigUint {
+    /// Creates and initializes an BigUint.
+    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;
+        unsafe { v.truncate(new_len); }
+        return BigUint { data: v };
+    }
+
+    /// Creates and initializes an BigUint.
+    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.
+    pub fn from_slice(slice: &[BigDigit]) -> BigUint {
+        return BigUint::new(vec::from_slice(slice));
+    }
+
+    /// Creates and initializes an BigUint.
+    pub fn from_str_radix(s: &str, radix: uint)
+        -> Option<BigUint> {
+        BigUint::parse_bytes(str::to_bytes(s), radix)
+    }
+
+    /// Creates and initializes an BigUint.
+    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) {
+                Some(d) => n += BigUint::from_uint(d) * power,
+                None    => return None
+            }
+            if end <= unit_len {
+                return Some(n);
+            }
+            end -= unit_len;
+            power *= base_num;
+        }
+    }
+
+    fn abs(&self) -> BigUint { copy *self }
+
+    /// Compare two BigUint value.
+    fn cmp(&self, other: &BigUint) -> int {
+        let s_len = self.data.len(), o_len = other.data.len();
+        if s_len < o_len { return -1; }
+        if s_len > o_len { return  1;  }
+
+        for self.data.eachi_reverse |i, elm| {
+            match (*elm, other.data[i]) {
+                (l, r) if l < r => return -1,
+                (l, r) if l > r => return  1,
+                _               => loop
+            };
+        }
+        return 0;
+    }
+
+    fn divmod(&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) {
+            s if s < 0 => return (Zero::zero(), copy *self),
+            0          => return (One::one(), Zero::zero()),
+            _          => {} // 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) = divmod_inner(self << shift, other << shift);
+        return (d, m >> shift);
+
+        fn divmod_inner(a: BigUint, b: BigUint) -> (BigUint, BigUint) {
+            let mut r = a;
+            let mut d = Zero::zero::<BigUint>();
+            let mut n = 1;
+            while r >= b {
+                let mut (d0, d_unit, b_unit) = div_estimate(&r, &b, n);
+                let mut prod = b * d0;
+                while prod > r {
+                    d0   -= d_unit;
+                    prod -= b_unit;
+                }
+                if d0.is_zero() {
+                    n = 2;
+                    loop;
+                }
+                n = 1;
+                d += d0;
+                r -= prod;
+            }
+            return (d, r);
+        }
+
+        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));
+        }
+    }
+
+    fn quot(&self, other: &BigUint) -> BigUint {
+        let (q, _) = self.quotrem(other);
+        return q;
+    }
+    fn rem(&self, other: &BigUint) -> BigUint {
+        let (_, r) = self.quotrem(other);
+        return r;
+    }
+    fn quotrem(&self, other: &BigUint) -> (BigUint, BigUint) {
+        self.divmod(other)
+    }
+
+    fn is_zero(&self) -> bool { self.data.is_empty() }
+    fn is_not_zero(&self) -> bool { !self.data.is_empty() }
+    fn is_positive(&self) -> bool { self.is_not_zero() }
+    fn is_negative(&self) -> bool { false }
+    fn is_nonpositive(&self) -> bool { self.is_zero() }
+    fn is_nonnegative(&self) -> bool { true }
+
+    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
+        }
+    }
+
+    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);
+
+        fn convert_base(n: BigUint, base: uint) -> ~[BigDigit] {
+            let divider    = BigUint::from_uint(base);
+            let mut result = ~[];
+            let mut r      = n;
+            while r > divider {
+                let (d, r0) = r.divmod(&divider);
+                result += [r0.to_uint() as BigDigit];
+                r = d;
+            }
+            if r.is_not_zero() {
+                result += [r.to_uint() as BigDigit];
+            }
+            return result;
+        }
+
+        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()
+        }
+    }
+
+    priv fn shl_unit(self, n_unit: uint) -> BigUint {
+        if n_unit == 0 || self.is_zero() { return self; }
+
+        return BigUint::new(vec::from_elem(n_unit, 0) + self.data);
+    }
+
+    priv fn shl_bits(self, n_bits: uint) -> BigUint {
+        if n_bits == 0 || self.is_zero() { return 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]);
+    }
+
+    priv fn shr_unit(self, n_unit: uint) -> BigUint {
+        if n_unit == 0 { return self; }
+        if self.data.len() < n_unit { return Zero::zero(); }
+        return BigUint::from_slice(
+            vec::slice(self.data, n_unit, self.data.len())
+        );
+    }
+
+    priv fn shr_bits(self, n_bits: uint) -> BigUint {
+        if n_bits == 0 || self.data.is_empty() { return self; }
+
+        let mut borrow = 0;
+        let mut shifted = ~[];
+        for self.data.each_reverse |elem| {
+            shifted = ~[(*elem >> n_bits) | borrow] + shifted;
+            borrow = *elem << (uint::bits - n_bits);
+        }
+        return BigUint::new(shifted);
+    }
+}
+
+#[cfg(target_arch = "x86_64")]
+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")]
+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)]
+pub enum Sign { Minus, Zero, Plus }
+
+impl Ord for Sign {
+    fn lt(&self, other: &Sign) -> bool { self.cmp(other) <  0 }
+    fn le(&self, other: &Sign) -> bool { self.cmp(other) <= 0 }
+    fn ge(&self, other: &Sign) -> bool { self.cmp(other) >= 0 }
+    fn gt(&self, other: &Sign) -> bool { self.cmp(other) >  0 }
+}
+
+pub impl Sign {
+    /// Compare two Sign.
+    fn cmp(&self, other: &Sign) -> int {
+        match (*self, *other) {
+          (Minus, Minus) | (Zero,  Zero) | (Plus, Plus) =>  0,
+          (Minus, Zero)  | (Minus, Plus) | (Zero, Plus) => -1,
+          _                                             =>  1
+        }
+    }
+
+    /// Negate Sign value.
+    fn neg(&self) -> Sign {
+        match *self {
+          Minus => Plus,
+          Zero  => Zero,
+          Plus  => Minus
+        }
+    }
+}
+
+/// A big signed integer type.
+pub struct BigInt {
+    priv sign: Sign,
+    priv data: BigUint
+}
+
+impl Eq for BigInt {
+    fn eq(&self, other: &BigInt) -> bool { self.cmp(other) == 0 }
+    fn ne(&self, other: &BigInt) -> bool { self.cmp(other) != 0 }
+}
+
+impl Ord for BigInt {
+    fn lt(&self, other: &BigInt) -> bool { self.cmp(other) <  0 }
+    fn le(&self, other: &BigInt) -> bool { self.cmp(other) <= 0 }
+    fn ge(&self, other: &BigInt) -> bool { self.cmp(other) >= 0 }
+    fn gt(&self, other: &BigInt) -> bool { self.cmp(other) >  0 }
+}
+
+impl ToStr for BigInt {
+    fn to_str(&self) -> ~str { self.to_str_radix(10) }
+}
+
+impl from_str::FromStr for BigInt {
+    fn from_str(s: &str) -> Option<BigInt> {
+        BigInt::from_str_radix(s, 10)
+    }
+}
+
+impl Shl<uint, BigInt> for BigInt {
+    fn shl(&self, rhs: &uint) -> BigInt {
+        BigInt::from_biguint(self.sign, self.data << *rhs)
+    }
+}
+
+impl Shr<uint, BigInt> for BigInt {
+    fn shr(&self, rhs: &uint) -> BigInt {
+        BigInt::from_biguint(self.sign, self.data >> *rhs)
+    }
+}
+
+impl Zero for BigInt {
+    pub fn zero() -> BigInt {
+        BigInt::from_biguint(Zero, Zero::zero())
+    }
+}
+
+impl One for BigInt {
+    pub fn one() -> BigInt {
+        BigInt::from_biguint(Plus, One::one())
+    }
+}
+
+impl Add<BigInt, BigInt> for BigInt {
+    fn add(&self, other: &BigInt) -> BigInt {
+        match (self.sign, other.sign) {
+            (Zero, _)      => copy *other,
+            (_,    Zero)   => copy *self,
+            (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 {
+    fn sub(&self, other: &BigInt) -> BigInt {
+        match (self.sign, other.sign) {
+            (Zero, _)    => -other,
+            (_,    Zero) => copy *self,
+            (Plus, Plus) => match self.data.cmp(&other.data) {
+                s if s < 0 =>
+                    BigInt::from_biguint(Minus, other.data - self.data),
+                s if s > 0 =>
+                    BigInt::from_biguint(Plus, self.data - other.data),
+                _ =>
+                    Zero::zero()
+            },
+            (Plus, Minus) => self + (-*other),
+            (Minus, Plus) => -((-self) + *other),
+            (Minus, Minus) => (-other) - (-*self)
+        }
+    }
+}
+
+impl Mul<BigInt, BigInt> for BigInt {
+    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 {
+    fn div(&self, other: &BigInt) -> BigInt {
+        let (d, _) = self.divmod(other);
+        return d;
+    }
+}
+
+impl Modulo<BigInt, BigInt> for BigInt {
+    fn modulo(&self, other: &BigInt) -> BigInt {
+        let (_, m) = self.divmod(other);
+        return m;
+    }
+}
+
+impl Neg<BigInt> for BigInt {
+    fn neg(&self) -> BigInt {
+        BigInt::from_biguint(self.sign.neg(), copy self.data)
+    }
+}
+
+impl IntConvertible for BigInt {
+    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
+        }
+    }
+
+    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();
+    }
+}
+
+pub impl BigInt {
+    /// Creates and initializes an BigInt.
+    pub fn new(sign: Sign, v: ~[BigDigit]) -> BigInt {
+        BigInt::from_biguint(sign, BigUint::new(v))
+    }
+
+    /// Creates and initializes an BigInt.
+    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.
+    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.
+    pub fn from_slice(sign: Sign, slice: &[BigDigit]) -> BigInt {
+        BigInt::from_biguint(sign, BigUint::from_slice(slice))
+    }
+
+    /// Creates and initializes an BigInt.
+    pub fn from_str_radix(s: &str, radix: uint)
+        -> Option<BigInt> {
+        BigInt::parse_bytes(str::to_bytes(s), radix)
+    }
+
+    /// Creates and initializes an BigInt.
+    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(|bu| BigInt::from_biguint(sign, *bu));
+    }
+
+    fn abs(&self) -> BigInt {
+        BigInt::from_biguint(Plus, copy self.data)
+    }
+
+    fn cmp(&self, other: &BigInt) -> int {
+        let ss = self.sign, os = other.sign;
+        if ss < os { return -1; }
+        if ss > os { return  1; }
+
+        assert!(ss == os);
+        match ss {
+            Zero  => 0,
+            Plus  => self.data.cmp(&other.data),
+            Minus => self.data.cmp(&other.data).neg(),
+        }
+    }
+
+    fn divmod(&self, other: &BigInt) -> (BigInt, BigInt) {
+        // m.sign == other.sign
+        let (d_ui, m_ui) = self.data.divmod(&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)
+        }
+    }
+
+    fn quot(&self, other: &BigInt) -> BigInt {
+        let (q, _) = self.quotrem(other);
+        return q;
+    }
+    fn rem(&self, other: &BigInt) -> BigInt {
+        let (_, r) = self.quotrem(other);
+        return r;
+    }
+
+    fn quotrem(&self, other: &BigInt) -> (BigInt, BigInt) {
+        // r.sign == self.sign
+        let (q_ui, r_ui) = self.data.quotrem(&other.data);
+        let q = BigInt::from_biguint(Plus, q_ui);
+        let r = BigInt::from_biguint(Plus, r_ui);
+        match (self.sign, other.sign) {
+            (_,    Zero)   => fail!(),
+            (Plus, Plus)  | (Zero, Plus)  => ( q,  r),
+            (Plus, Minus) | (Zero, Minus) => (-q,  r),
+            (Minus, Plus)                 => (-q, -r),
+            (Minus, Minus)                => ( q, -r)
+        }
+    }
+
+    fn is_zero(&self) -> bool { self.sign == Zero }
+    fn is_not_zero(&self) -> bool { self.sign != Zero }
+    fn is_positive(&self) -> bool { self.sign == Plus }
+    fn is_negative(&self) -> bool { self.sign == Minus }
+    fn is_nonpositive(&self) -> bool { self.sign != Plus }
+    fn is_nonnegative(&self) -> bool { self.sign != Minus }
+
+    fn to_uint(&self) -> uint {
+        match self.sign {
+            Plus  => self.data.to_uint(),
+            Zero  => 0,
+            Minus => 0
+        }
+    }
+
+    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)
+        }
+    }
+}
+
+#[cfg(test)]
+mod biguint_tests {
+
+    use core::*;
+    use core::num::{IntConvertible, Zero, One};
+    use super::{BigUint, BigDigit};
+
+    #[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!(ni.cmp(nj) == 0);
+                    assert!(nj.cmp(ni) == 0);
+                    assert!(ni == nj);
+                    assert!(!(ni != nj));
+                    assert!(ni <= nj);
+                    assert!(ni >= nj);
+                    assert!(!(ni < nj));
+                    assert!(!(ni > nj));
+                } else {
+                    assert!(ni.cmp(nj) < 0);
+                    assert!(nj.cmp(ni) > 0);
+
+                    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!(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!(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)]);
+        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!(BigUint::new(~[0, -1]).to_int() == int::max_value);
+        assert!(BigUint::new(~[0, 0, 1]).to_int() == int::max_value);
+        assert!(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!(BigUint::new(~[0, 0, 1]).to_uint()  == uint::max_value);
+        assert!(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 divmod_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 divmod_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_divmod() {
+        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_not_zero() {
+                assert!(c.divmod(&a) == (b, Zero::zero()));
+            }
+            if b.is_not_zero() {
+                assert!(c.divmod(&b) == (a, Zero::zero()));
+            }
+        }
+
+        for divmod_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_not_zero() { assert!(a.divmod(&b) == (c, d)); }
+        }
+    }
+
+    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!(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!(Some(n) == BigUint::from_str_radix(str, radix));
+            }
+        }
+
+        assert!(BigUint::from_str_radix(~"Z", 10) == None);
+        assert!(BigUint::from_str_radix(~"_", 2) == None);
+        assert!(BigUint::from_str_radix(~"-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| {
+                f *= BigUint::from_uint(i);
+            }
+            return f;
+        }
+
+        fn check(n: uint, s: &str) {
+            let n = factor(n);
+            let ans = match BigUint::from_str_radix(s, 10) {
+                Some(x) => x, None => fail!()
+            };
+            assert!(n == ans);
+        }
+
+        check(3, "6");
+        check(10, "3628800");
+        check(20, "2432902008176640000");
+        check(30, "265252859812191058636308480000000");
+    }
+}
+
+#[cfg(test)]
+mod bigint_tests {
+    use super::{BigInt, BigUint, BigDigit, Sign, Minus, Zero, Plus};
+
+    use core::*;
+    use core::num::{IntConvertible, Zero, One};
+
+    #[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!(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!(ni.cmp(nj) == 0);
+                    assert!(nj.cmp(ni) == 0);
+                    assert!(ni == nj);
+                    assert!(!(ni != nj));
+                    assert!(ni <= nj);
+                    assert!(ni >= nj);
+                    assert!(!(ni < nj));
+                    assert!(!(ni > nj));
+                } else {
+                    assert!(ni.cmp(nj) < 0);
+                    assert!(nj.cmp(ni) > 0);
+
+                    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 divmod_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 divmod_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_divmod() {
+        fn check_sub(a: &BigInt, b: &BigInt, ans_d: &BigInt, ans_m: &BigInt) {
+            let (d, m) = a.divmod(b);
+            if m.is_not_zero() {
+                assert!(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_not_zero() { check(&c, &a, &b, &Zero::zero()); }
+            if b.is_not_zero() { check(&c, &b, &a, &Zero::zero()); }
+        }
+
+        for divmod_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_not_zero() {
+                check(&a, &b, &c, &d);
+            }
+        }
+    }
+
+
+    #[test]
+    fn test_quotrem() {
+        fn check_sub(a: &BigInt, b: &BigInt, ans_q: &BigInt, ans_r: &BigInt) {
+            let (q, r) = a.quotrem(b);
+            if r.is_not_zero() {
+                assert!(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_not_zero() { check(&c, &a, &b, &Zero::zero()); }
+            if b.is_not_zero() { check(&c, &b, &a, &Zero::zero()); }
+        }
+
+        for divmod_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_not_zero() {
+                check(&a, &b, &c, &d);
+            }
+        }
+    }
+
+    #[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(n));
+            assert!(BigInt::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!(-Zero::zero::<BigInt>() == Zero::zero::<BigInt>());
+    }
+}
+
diff --git a/src/libstd/num/complex.rs b/src/libstd/num/complex.rs
new file mode 100644
index 00000000000..1e8fc0e6c2b
--- /dev/null
+++ b/src/libstd/num/complex.rs
@@ -0,0 +1,315 @@
+// 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};
+use core::prelude::*;
+
+// 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 + Add<T,T> + Sub<T,T> + Mul<T,T> + Div<T,T> + Neg<T>>
+    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 + Add<T,T> + Sub<T,T> + Mul<T,T> + Div<T,T> + Neg<T>>
+    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 + Add<T,T> + Sub<T,T> + Mul<T,T> + Div<T,T> + Neg<T>>
+    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 + Add<T,T> + Sub<T,T> + Mul<T,T> + Div<T,T> + Neg<T>>
+    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 + Add<T,T> + Sub<T,T> + Mul<T,T> + Div<T,T> + Neg<T>>
+    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 + Add<T,T> + Sub<T,T> + Mul<T,T> + Div<T,T> + Neg<T>>
+    Neg<Cmplx<T>> for Cmplx<T> {
+    #[inline]
+    fn neg(&self) -> Cmplx<T> {
+        Cmplx::new(-self.re, -self.im)
+    }
+}
+
+/* constants */
+impl<T: Copy + Add<T,T> + Sub<T,T> + Mul<T,T> + Div<T,T> + Neg<T> + Zero>
+    Zero for Cmplx<T> {
+    #[inline]
+    fn zero() -> Cmplx<T> {
+        Cmplx::new(Zero::zero(), Zero::zero())
+    }
+}
+
+impl<T: Copy + Add<T,T> + Sub<T,T> + Mul<T,T> + Div<T,T> + Neg<T> + Zero + One>
+    One for Cmplx<T> {
+    #[inline]
+    fn one() -> Cmplx<T> {
+        Cmplx::new(One::one(), Zero::zero())
+    }
+}
+
+/* string conversions */
+impl<T: ToStr + Zero + Ord + Neg<T>> 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 + Zero + Ord + Neg<T>> 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 core::prelude::*;
+    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 super::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/libstd/num/rational.rs b/src/libstd/num/rational.rs
new file mode 100644
index 00000000000..f15b382dcd3
--- /dev/null
+++ b/src/libstd/num/rational.rs
@@ -0,0 +1,511 @@
+// 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 core::to_str::ToStr;
+use core::prelude::*;
+use core::cmp::TotalEq;
+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: Copy + Div<T,T> + Modulo<T,T> + Neg<T> + Zero + One + Ord + Eq>
+    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!(~"divide by 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 mut g : T = gcd(self.numer, self.denom);
+
+        self.numer /= g;
+        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 = copy *self;
+        ret.reduce();
+        ret
+    }
+}
+
+/**
+Compute the greatest common divisor of two numbers, via Euclid's algorithm.
+
+The result can be negative.
+*/
+#[inline]
+pub fn gcd_raw<T: Modulo<T,T> + Zero + Eq>(n: T, m: T) -> T {
+    let mut m = m, n = n;
+    while m != Zero::zero() {
+        let temp = m;
+        m = n % temp;
+        n = temp;
+    }
+    n
+}
+
+/**
+Compute the greatest common divisor of two numbers, via Euclid's algorithm.
+
+The result is always positive.
+*/
+#[inline]
+pub fn gcd<T: Modulo<T,T> + Neg<T> + Zero + Ord + Eq>(n: T, m: T) -> T {
+    let g = gcd_raw(n, m);
+    if g < Zero::zero() { -g }
+    else { g }
+}
+
+/* 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: Copy + Mul<T,T> + Div<T,T> + Modulo<T,T> + Neg<T> + Zero + One + Ord + Eq>
+    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: Copy + Mul<T,T> + Div<T,T> + Modulo<T,T> + Neg<T> + Zero + One + Ord + Eq>
+    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: Copy +
+                Add<T,T> + Sub<T,T> + Mul<T,T> + Div<T,T> + Modulo<T,T> + Neg<T> +
+                Zero + One + Ord + Eq>
+            $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 Modulo, modulo)
+
+impl<T: Copy + Div<T,T> + Modulo<T,T> + Neg<T> + Zero + One + Ord + Eq>
+    Neg<Ratio<T>> for Ratio<T> {
+    #[inline]
+    fn neg(&self) -> Ratio<T> {
+        Ratio::new_raw(-self.numer, self.denom)
+    }
+}
+
+/* Constants */
+impl<T: Copy + Div<T,T> + Modulo<T,T> + Neg<T> + Zero + One + Ord + Eq>
+    Zero for Ratio<T> {
+    #[inline]
+    fn zero() -> Ratio<T> {
+        Ratio::new_raw(Zero::zero(), One::one())
+    }
+}
+
+impl<T: Copy + Div<T,T> + Modulo<T,T> + Neg<T> + Zero + One + Ord + Eq>
+    One for Ratio<T> {
+    #[inline]
+    fn one() -> Ratio<T> {
+        Ratio::new_raw(One::one(), One::one())
+    }
+}
+
+/* Utils */
+impl<T: Copy + Add<T,T> + Sub<T,T> + Mul<T,T> + Div<T,T> + Modulo<T,T> + Neg<T> +
+    Zero + One + Ord + Eq>
+    Round for Ratio<T> {
+    fn round(&self, mode: num::RoundMode) -> Ratio<T> {
+        match mode {
+            num::RoundUp => { self.ceil() }
+            num::RoundDown => { self.floor()}
+            num::RoundToZero => { Ratio::from_integer(self.numer / self.denom) }
+            num::RoundFromZero => {
+                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)
+                }
+            }
+        }
+    }
+
+    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)
+        }
+    }
+    fn fract(&self) -> Ratio<T> {
+        Ratio::new_raw(self.numer % self.denom, self.denom)
+    }
+}
+
+
+/* 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 + Copy + Div<T,T> + Modulo<T,T> + Neg<T> + Zero + One + Ord + Eq>
+    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(split[0]).chain |a| {
+            do FromStr::from_str(split[1]).chain |b| {
+                Some(Ratio::new(a,b))
+            }
+        }
+    }
+}
+impl<T: FromStrRadix + Copy + Div<T,T> + Modulo<T,T> + Neg<T> + Zero + One + Ord + Eq>
+    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(split[0], radix).chain |a| {
+                do FromStrRadix::from_str_radix(split[1], radix).chain |b| {
+                    Some(Ratio::new(a,b))
+                }
+            }
+        }
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use core::prelude::*;
+    use super::*;
+    use core::num::{Zero,One,FromStrRadix};
+    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};
+
+    #[test]
+    fn test_gcd() {
+        assert_eq!(gcd(10,2),2);
+        assert_eq!(gcd(10,3),1);
+        assert_eq!(gcd(0,3),3);
+        assert_eq!(gcd(3,3),3);
+
+        assert_eq!(gcd(3,-3), 3);
+        assert_eq!(gcd(-6,3), 3);
+        assert_eq!(gcd(-4,-2), 2);
+    }
+
+    #[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() {
+            assert_eq!(_1 + _1_2, _3_2);
+            assert_eq!(_1 + _1, _2);
+            assert_eq!(_1_2 + _3_2, _2);
+            assert_eq!(_1_2 + _neg1_2, _0);
+        }
+
+        #[test]
+        fn test_sub() {
+            assert_eq!(_1 - _1_2, _1_2);
+            assert_eq!(_3_2 - _1_2, _1);
+            assert_eq!(_1 - _neg1_2, _3_2);
+        }
+
+        #[test]
+        fn test_mul() {
+            assert_eq!(_1 * _1_2, _1_2);
+            assert_eq!(_1_2 * _3_2, Ratio::new(3,4));
+            assert_eq!(_1_2 * _neg1_2, Ratio::new(-1, 4));
+        }
+
+        #[test]
+        fn test_div() {
+            assert_eq!(_1 / _1_2, _2);
+            assert_eq!(_3_2 / _1_2, _1 + _2);
+            assert_eq!(_1 / _neg1_2, _neg1_2 + _neg1_2 + _neg1_2 + _neg1_2);
+        }
+
+        #[test]
+        fn test_modulo() {
+            assert_eq!(_3_2 % _1, _1_2);
+            assert_eq!(_2 % _neg1_2, _0);
+            assert_eq!(_1_2 % _2,  _1_2);
+        }
+
+        #[test]
+        fn test_neg() {
+            assert_eq!(-_0, _0);
+            assert_eq!(-_1_2, _neg1_2);
+            assert_eq!(-(-_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(num::RoundToZero), _0);
+        assert_eq!(_1_2.round(num::RoundFromZero), _1);
+
+        assert_eq!(_neg1_2.ceil(), _0);
+        assert_eq!(_neg1_2.floor(), -_1);
+        assert_eq!(_neg1_2.round(num::RoundToZero), _0);
+        assert_eq!(_neg1_2.round(num::RoundFromZero), -_1);
+
+        assert_eq!(_1.ceil(), _1);
+        assert_eq!(_1.floor(), _1);
+        assert_eq!(_1.round(num::RoundToZero), _1);
+        assert_eq!(_1.round(num::RoundFromZero), _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_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);
+        }
+    }
+}
\ No newline at end of file