auto merge of #6092 : gifnksm/rust/impl-integer-bigint, r=graydon

This is a follow-up commit for #6041 (and depending on #6048).
Also adding `#[inline(always)]` for almost every methods in `std::bigint`.

1 files changed, 383 insertions, 144 deletions

diff --git a/src/libstd/num/bigint.rs b/src/libstd/num/bigint.rs
index 214bb0be0ed..3ea94eababb 100644
--- a/src/libstd/num/bigint.rs
+++ b/src/libstd/num/bigint.rs
@@ -53,15 +53,19 @@ pub mod BigDigit {
     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)
     }
@@ -78,32 +82,40 @@ pub struct BigUint {
 }
 
 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; }
@@ -121,16 +133,19 @@ impl TotalOrd for BigUint {
 }
 
 impl ToStr for BigUint {
+    #[inline(always)]
     fn to_str(&self) -> ~str { self.to_str_radix(10) }
 }
 
 impl from_str::FromStr for BigUint {
+    #[inline(always)]
     fn from_str(s: &str) -> Option<BigUint> {
         FromStrRadix::from_str_radix(s, 10)
     }
 }
 
 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;
@@ -139,6 +154,7 @@ impl Shl<uint, BigUint> for BigUint {
 }
 
 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;
@@ -147,18 +163,22 @@ impl Shr<uint, BigUint> for BigUint {
 }
 
 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());
 
@@ -178,6 +198,7 @@ impl Add<BigUint, BigUint> for BigUint {
 }
 
 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());
 
@@ -233,6 +254,7 @@ impl Mul<BigUint, BigUint> for BigUint {
 
         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; }
@@ -249,6 +271,7 @@ impl Mul<BigUint, BigUint> for BigUint {
             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,
@@ -256,6 +279,7 @@ impl Mul<BigUint, BigUint> for BigUint {
                     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),
@@ -267,6 +291,7 @@ impl Mul<BigUint, BigUint> for BigUint {
 }
 
 impl Quot<BigUint, BigUint> for BigUint {
+    #[inline(always)]
     fn quot(&self, other: &BigUint) -> BigUint {
         let (q, _) = self.quot_rem(other);
         return q;
@@ -274,6 +299,7 @@ impl Quot<BigUint, BigUint> for BigUint {
 }
 
 impl Rem<BigUint, BigUint> for BigUint {
+    #[inline(always)]
     fn rem(&self, other: &BigUint) -> BigUint {
         let (_, r) = self.quot_rem(other);
         return r;
@@ -281,20 +307,159 @@ impl Rem<BigUint, BigUint> for BigUint {
 }
 
 impl Neg<BigUint> for BigUint {
+    #[inline(always)]
     fn neg(&self) -> BigUint { fail!() }
 }
 
+impl Integer for BigUint {
+    #[inline(always)]
+    fn div(&self, other: &BigUint) -> BigUint {
+        let (d, _) = self.div_mod(other);
+        return d;
+    }
+
+    #[inline(always)]
+    fn modulo(&self, other: &BigUint) -> BigUint {
+        let (_, m) = self.div_mod(other);
+        return m;
+    }
+
+    #[inline(always)]
+    fn div_mod(&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_inner(self << shift, other << shift);
+        return (d, m >> shift);
+
+        #[inline(always)]
+        fn div_mod_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 {
+                    d0   -= d_unit;
+                    prod -= b_unit;
+                }
+                if d0.is_zero() {
+                    n = 2;
+                    loop;
+                }
+                n = 1;
+                d += d0;
+                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));
+        }
+    }
+
+    #[inline(always)]
+    fn quot_rem(&self, other: &BigUint) -> (BigUint, BigUint) {
+        self.div_mod(other)
+    }
+
+    /**
+     * 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 = *self, n = *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 divisible_by(&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.last().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);
@@ -303,6 +468,7 @@ impl ToStrRadix for BigUint {
         }
         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 = ~[];
@@ -318,6 +484,7 @@ impl ToStrRadix for BigUint {
             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| {
@@ -331,14 +498,16 @@ impl ToStrRadix for BigUint {
 
 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)
     }
 }
 
-pub impl BigUint {
+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);
@@ -350,6 +519,7 @@ pub impl BigUint {
     }
 
     /// Creates and initializes an BigUint.
+    #[inline(always)]
     pub fn from_uint(n: uint) -> BigUint {
         match BigDigit::from_uint(n) {
             (0,  0)  => Zero::zero(),
@@ -359,11 +529,13 @@ pub impl BigUint {
     }
 
     /// Creates and initializes an BigUint.
+    #[inline(always)]
     pub fn from_slice(slice: &[BigDigit]) -> BigUint {
         return BigUint::new(vec::from_slice(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);
@@ -386,93 +558,8 @@ pub impl BigUint {
         }
     }
 
-    fn abs(&self) -> BigUint { copy *self }
-
-    fn div(&self, other: &BigUint) -> BigUint {
-        let (d, _) = self.div_mod(other);
-        return d;
-    }
-    fn modulo(&self, other: &BigUint) -> BigUint {
-        let (_, m) = self.div_mod(other);
-        return m;
-    }
-
-    fn div_mod(&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_inner(self << shift, other << shift);
-        return (d, m >> shift);
-
-        fn div_mod_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 {
-                    d0   -= d_unit;
-                    prod -= b_unit;
-                }
-                if d0.is_zero() {
-                    n = 2;
-                    loop;
-                }
-                n = 1;
-                d += d0;
-                m -= prod;
-            }
-            return (d, m);
-        }
-
-        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_rem(&self, other: &BigUint) -> (BigUint, BigUint) {
-        self.div_mod(other)
-    }
-
-    fn to_uint(&self) -> uint {
+    #[inline(always)]
+    pub fn to_uint(&self) -> uint {
         match self.data.len() {
             0 => 0,
             1 => self.data[0] as uint,
@@ -481,12 +568,14 @@ pub impl BigUint {
         }
     }
 
+    #[inline(always)]
     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);
     }
 
+    #[inline(always)]
     priv fn shl_bits(self, n_bits: uint) -> BigUint {
         if n_bits == 0 || self.is_zero() { return self; }
 
@@ -502,6 +591,7 @@ pub impl BigUint {
         return BigUint::new(shifted + [carry]);
     }
 
+    #[inline(always)]
     priv fn shr_unit(self, n_unit: uint) -> BigUint {
         if n_unit == 0 { return self; }
         if self.data.len() < n_unit { return Zero::zero(); }
@@ -510,6 +600,7 @@ pub impl BigUint {
         );
     }
 
+    #[inline(always)]
     priv fn shr_bits(self, n_bits: uint) -> BigUint {
         if n_bits == 0 || self.data.is_empty() { return self; }
 
@@ -524,6 +615,7 @@ pub impl BigUint {
 }
 
 #[cfg(target_arch = "x86_64")]
+#[inline(always)]
 priv fn get_radix_base(radix: uint) -> (uint, uint) {
     assert!(1 < radix && radix <= 16);
     match radix {
@@ -549,6 +641,7 @@ priv fn get_radix_base(radix: uint) -> (uint, uint) {
 #[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 {
@@ -576,21 +669,26 @@ priv fn get_radix_base(radix: uint) -> (uint, uint) {
 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,
@@ -602,6 +700,7 @@ impl TotalOrd for Sign {
 
 impl Neg<Sign> for Sign {
     /// Negate Sign value.
+    #[inline(always)]
     fn neg(&self) -> Sign {
         match *self {
           Minus => Plus,
@@ -618,32 +717,40 @@ pub struct BigInt {
 }
 
 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; }
@@ -657,42 +764,50 @@ impl TotalOrd for BigInt {
 }
 
 impl ToStr for BigInt {
+    #[inline(always)]
     fn to_str(&self) -> ~str { self.to_str_radix(10) }
 }
 
 impl from_str::FromStr for BigInt {
+    #[inline(always)]
     fn from_str(s: &str) -> Option<BigInt> {
         FromStrRadix::from_str_radix(s, 10)
     }
 }
 
 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 {
-    pub fn zero() -> 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 {
-    pub fn one() -> 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 => copy *self,
@@ -700,6 +815,7 @@ impl Signed for BigInt {
         }
     }
 
+    #[inline(always)]
     fn signum(&self) -> BigInt {
         match self.sign {
             Plus  => BigInt::from_biguint(Plus, One::one()),
@@ -708,12 +824,15 @@ impl Signed for BigInt {
         }
     }
 
+    #[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, _)      => copy *other,
@@ -728,6 +847,7 @@ impl Add<BigInt, BigInt> for BigInt {
 }
 
 impl Sub<BigInt, BigInt> for BigInt {
+    #[inline(always)]
     fn sub(&self, other: &BigInt) -> BigInt {
         match (self.sign, other.sign) {
             (Zero, _)    => -other,
@@ -745,6 +865,7 @@ impl Sub<BigInt, BigInt> for BigInt {
 }
 
 impl Mul<BigInt, BigInt> for BigInt {
+    #[inline(always)]
     fn mul(&self, other: &BigInt) -> BigInt {
         match (self.sign, other.sign) {
             (Zero, _)     | (_,     Zero)  => Zero::zero(),
@@ -759,6 +880,7 @@ impl Mul<BigInt, BigInt> for BigInt {
 }
 
 impl Quot<BigInt, BigInt> for BigInt {
+    #[inline(always)]
     fn quot(&self, other: &BigInt) -> BigInt {
         let (q, _) = self.quot_rem(other);
         return q;
@@ -766,6 +888,7 @@ impl Quot<BigInt, BigInt> for BigInt {
 }
 
 impl Rem<BigInt, BigInt> for BigInt {
+    #[inline(always)]
     fn rem(&self, other: &BigInt) -> BigInt {
         let (_, r) = self.quot_rem(other);
         return r;
@@ -773,12 +896,96 @@ impl Rem<BigInt, BigInt> for BigInt {
 }
 
 impl Neg<BigInt> for BigInt {
+    #[inline(always)]
     fn neg(&self) -> BigInt {
         BigInt::from_biguint(self.sign.neg(), copy self.data)
     }
 }
 
+impl Integer for BigInt {
+    #[inline(always)]
+    fn div(&self, other: &BigInt) -> BigInt {
+        let (d, _) = self.div_mod(other);
+        return d;
+    }
+
+    #[inline(always)]
+    fn modulo(&self, other: &BigInt) -> BigInt {
+        let (_, m) = self.div_mod(other);
+        return m;
+    }
+
+    #[inline(always)]
+    fn div_mod(&self, other: &BigInt) -> (BigInt, BigInt) {
+        // m.sign == other.sign
+        let (d_ui, m_ui) = self.data.quot_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)
+        }
+    }
+
+    #[inline(always)]
+    fn quot_rem(&self, other: &BigInt) -> (BigInt, BigInt) {
+        // r.sign == self.sign
+        let (q_ui, r_ui) = self.data.div_mod(&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)
+        }
+    }
+
+    /**
+     * 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 divisible_by(&self, other: &BigInt) -> bool { self.data.divisible_by(&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,
@@ -788,6 +995,7 @@ impl IntConvertible for BigInt {
         }
     }
 
+    #[inline(always)]
     fn from_int(n: int) -> BigInt {
         if n > 0 {
            return BigInt::from_biguint(Plus,  BigUint::from_uint(n as uint));
@@ -802,6 +1010,7 @@ impl IntConvertible for BigInt {
 }
 
 impl ToStrRadix for BigInt {
+    #[inline(always)]
     fn to_str_radix(&self, radix: uint) -> ~str {
         match self.sign {
             Plus  => self.data.to_str_radix(radix),
@@ -813,7 +1022,8 @@ impl ToStrRadix for BigInt {
 
 impl FromStrRadix for BigInt {
     /// Creates and initializes an BigInt.
-    pub fn from_str_radix(s: &str, radix: uint)
+    #[inline(always)]
+    fn from_str_radix(s: &str, radix: uint)
         -> Option<BigInt> {
         BigInt::parse_bytes(str::to_bytes(s), radix)
     }
@@ -821,11 +1031,13 @@ impl FromStrRadix for BigInt {
 
 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() };
@@ -834,17 +1046,20 @@ pub impl BigInt {
     }
 
     /// 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; }
@@ -858,57 +1073,7 @@ pub impl BigInt {
             .map(|bu| BigInt::from_biguint(sign, *bu));
     }
 
-    fn abs(&self) -> BigInt {
-        BigInt::from_biguint(Plus, copy self.data)
-    }
-
-    fn div(&self, other: &BigInt) -> BigInt {
-        let (d, _) = self.div_mod(other);
-        return d;
-    }
-    fn modulo(&self, other: &BigInt) -> BigInt {
-        let (_, m) = self.div_mod(other);
-        return m;
-    }
-
-    fn div_mod(&self, other: &BigInt) -> (BigInt, BigInt) {
-        // m.sign == other.sign
-        let (d_ui, m_ui) = self.data.quot_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)
-        }
-    }
-
-    fn quot_rem(&self, other: &BigInt) -> (BigInt, BigInt) {
-        // r.sign == self.sign
-        let (q_ui, r_ui) = self.data.div_mod(&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 }
-
+    #[inline(always)]
     fn to_uint(&self) -> uint {
         match self.sign {
             Plus  => self.data.to_uint(),
@@ -1229,6 +1394,41 @@ mod biguint_tests {
         }
     }
 
+    #[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);
+    }
+
     fn to_str_pairs() -> ~[ (BigUint, ~[(uint, ~str)]) ] {
         let bits = BigDigit::bits;
         ~[( Zero::zero(), ~[
@@ -1665,10 +1865,49 @@ mod bigint_tests {
     }
 
     #[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_to_str_radix() {
         fn check(n: int, ans: &str) {
-            assert!(ans == IntConvertible::from_int::<BigInt>(
-                n).to_str_radix(10));
+            assert!(ans == IntConvertible::from_int::<BigInt>(n).to_str_radix(10));
         }
         check(10, "10");
         check(1, "1");