auto merge of #11503 : FlaPer87/rust/master, r=huonw

The patch adds the missing pow method for all the implementations of the
Integer trait. This is a small addition that will most likely be
improved by the work happening in #10387.

Fixes #11499

6 files changed, 71 insertions, 43 deletions

diff --git a/src/libstd/num/f32.rs b/src/libstd/num/f32.rs
index a8eaa895650..e77348268c7 100644
--- a/src/libstd/num/f32.rs
+++ b/src/libstd/num/f32.rs
@@ -409,7 +409,7 @@ impl Real for f32 {
     fn recip(&self) -> f32 { 1.0 / *self }
 
     #[inline]
-    fn pow(&self, n: &f32) -> f32 { pow(*self, *n) }
+    fn powf(&self, n: &f32) -> f32 { pow(*self, *n) }
 
     #[inline]
     fn sqrt(&self) -> f32 { sqrt(*self) }
@@ -1265,7 +1265,7 @@ mod tests {
     fn test_integer_decode() {
         assert_eq!(3.14159265359f32.integer_decode(), (13176795u64, -22i16, 1i8));
         assert_eq!((-8573.5918555f32).integer_decode(), (8779358u64, -10i16, -1i8));
-        assert_eq!(2f32.pow(&100.0).integer_decode(), (8388608u64, 77i16, 1i8));
+        assert_eq!(2f32.powf(&100.0).integer_decode(), (8388608u64, 77i16, 1i8));
         assert_eq!(0f32.integer_decode(), (0u64, -150i16, 1i8));
         assert_eq!((-0f32).integer_decode(), (0u64, -150i16, -1i8));
         assert_eq!(INFINITY.integer_decode(), (8388608u64, 105i16, 1i8));
diff --git a/src/libstd/num/f64.rs b/src/libstd/num/f64.rs
index fe51cb07646..7a06ef2e1af 100644
--- a/src/libstd/num/f64.rs
+++ b/src/libstd/num/f64.rs
@@ -411,7 +411,7 @@ impl Real for f64 {
     fn recip(&self) -> f64 { 1.0 / *self }
 
     #[inline]
-    fn pow(&self, n: &f64) -> f64 { pow(*self, *n) }
+    fn powf(&self, n: &f64) -> f64 { pow(*self, *n) }
 
     #[inline]
     fn sqrt(&self) -> f64 { sqrt(*self) }
@@ -1269,7 +1269,7 @@ mod tests {
     fn test_integer_decode() {
         assert_eq!(3.14159265359f64.integer_decode(), (7074237752028906u64, -51i16, 1i8));
         assert_eq!((-8573.5918555f64).integer_decode(), (4713381968463931u64, -39i16, -1i8));
-        assert_eq!(2f64.pow(&100.0).integer_decode(), (4503599627370496u64, 48i16, 1i8));
+        assert_eq!(2f64.powf(&100.0).integer_decode(), (4503599627370496u64, 48i16, 1i8));
         assert_eq!(0f64.integer_decode(), (0u64, -1075i16, 1i8));
         assert_eq!((-0f64).integer_decode(), (0u64, -1075i16, -1i8));
         assert_eq!(INFINITY.integer_decode(), (4503599627370496u64, 972i16, 1i8));
diff --git a/src/libstd/num/int.rs b/src/libstd/num/int.rs
index 8068d4a74cb..dbc7c67d97b 100644
--- a/src/libstd/num/int.rs
+++ b/src/libstd/num/int.rs
@@ -121,38 +121,6 @@ impl CheckedMul for int {
     }
 }
 
-/// Returns `base` raised to the power of `exponent`
-pub fn pow(base: int, exponent: uint) -> int {
-    if exponent == 0u {
-        //Not mathemtically true if ~[base == 0]
-        return 1;
-    }
-    if base == 0 { return 0; }
-    let mut my_pow  = exponent;
-    let mut acc     = 1;
-    let mut multiplier = base;
-    while(my_pow > 0u) {
-        if my_pow % 2u == 1u {
-            acc *= multiplier;
-        }
-        my_pow     /= 2u;
-        multiplier *= multiplier;
-    }
-    return acc;
-}
-
-#[test]
-fn test_pow() {
-    assert!((pow(0, 0u) == 1));
-    assert!((pow(0, 1u) == 0));
-    assert!((pow(0, 2u) == 0));
-    assert!((pow(-1, 0u) == 1));
-    assert!((pow(1, 0u) == 1));
-    assert!((pow(-3, 2u) == 9));
-    assert!((pow(-3, 3u) == -27));
-    assert!((pow(4, 9u) == 262144));
-}
-
 #[test]
 fn test_overflows() {
     assert!((::int::max_value > 0));
diff --git a/src/libstd/num/mod.rs b/src/libstd/num/mod.rs
index 05f21c7d448..bcc95d6c48d 100644
--- a/src/libstd/num/mod.rs
+++ b/src/libstd/num/mod.rs
@@ -185,9 +185,9 @@ pub trait Real: Signed
     fn recip(&self) -> Self;
 
     // Algebraic functions
-
     /// Raise a number to a power.
-    fn pow(&self, n: &Self) -> Self;
+    fn powf(&self, n: &Self) -> Self;
+
     /// Take the square root of a number.
     fn sqrt(&self) -> Self;
     /// Take the reciprocal (inverse) square root of a number, `1/sqrt(x)`.
@@ -263,6 +263,50 @@ pub trait Real: Signed
     fn to_radians(&self) -> Self;
 }
 
+/// Raises a value to the power of exp, using
+/// exponentiation by squaring.
+///
+/// # Example
+///
+/// ```rust
+/// use std::num;
+///
+/// let sixteen = num::pow(2, 4u);
+/// assert_eq!(sixteen, 16);
+/// ```
+#[inline]
+pub fn pow<T: Clone+One+Mul<T, T>>(num: T, exp: uint) -> T {
+    let one: uint = One::one();
+    let num_one: T = One::one();
+
+    if exp.is_zero() { return num_one; }
+    if exp == one { return num.clone(); }
+
+    let mut i: uint = exp;
+    let mut v: T;
+    let mut r: T = num_one;
+
+    // This if is to avoid cloning self.
+    if (i & one) == one {
+        r = r * num;
+        i = i - one;
+    }
+
+    i = i >> one;
+    v = num * num;
+
+    while !i.is_zero() {
+        if (i & one) == one {
+            r = r * v;
+            i = i - one;
+        }
+        i = i >> one;
+        v = v * v;
+    }
+
+    r
+}
+
 /// Raise a number to a power.
 ///
 /// # Example
@@ -270,10 +314,10 @@ pub trait Real: Signed
 /// ```rust
 /// use std::num;
 ///
-/// let sixteen: f64 = num::pow(2.0, 4.0);
+/// let sixteen: f64 = num::powf(2.0, 4.0);
 /// assert_eq!(sixteen, 16.0);
 /// ```
-#[inline(always)] pub fn pow<T: Real>(value: T, n: T) -> T { value.pow(&n) }
+#[inline(always)] pub fn powf<T: Real>(value: T, n: T) -> T { value.powf(&n) }
 /// Take the square root of a number.
 #[inline(always)] pub fn sqrt<T: Real>(value: T) -> T { value.sqrt() }
 /// Take the reciprocal (inverse) square root of a number, `1/sqrt(x)`.
@@ -1074,6 +1118,7 @@ pub fn test_num<T:Num + NumCast>(ten: T, two: T) {
 mod tests {
     use prelude::*;
     use super::*;
+    use num;
     use i8;
     use i16;
     use i32;
@@ -1634,4 +1679,19 @@ mod tests {
         assert_eq!(from_f32(5f32), Some(Value { x: 5 }));
         assert_eq!(from_f64(5f64), Some(Value { x: 5 }));
     }
+
+    #[test]
+    fn test_pow() {
+        fn assert_pow<T: Eq+Clone+One+Mul<T, T>>(num: T, exp: uint) -> () {
+            assert_eq!(num::pow(num.clone(), exp),
+                       range(1u, exp).fold(num.clone(), |acc, _| acc * num));
+        }
+
+        assert_eq!(num::pow(3, 0), 1);
+        assert_eq!(num::pow(5, 1), 5);
+        assert_pow(-4, 2);
+        assert_pow(8, 3);
+        assert_pow(8, 5);
+        assert_pow(2u64, 50);
+    }
 }
diff --git a/src/libstd/rand/distributions/gamma.rs b/src/libstd/rand/distributions/gamma.rs
index 38644f84707..2f1890b0233 100644
--- a/src/libstd/rand/distributions/gamma.rs
+++ b/src/libstd/rand/distributions/gamma.rs
@@ -144,7 +144,7 @@ impl IndependentSample<f64> for GammaSmallShape {
     fn ind_sample<R: Rng>(&self, rng: &mut R) -> f64 {
         let Open01(u) = rng.gen::<Open01<f64>>();
 
-        self.large_shape.ind_sample(rng) * num::pow(u, self.inv_shape)
+        self.large_shape.ind_sample(rng) * num::powf(u, self.inv_shape)
     }
 }
 impl IndependentSample<f64> for GammaLargeShape {
diff --git a/src/libstd/sync/mpmc_bounded_queue.rs b/src/libstd/sync/mpmc_bounded_queue.rs
index 18d17eed885..bf02bf204a5 100644
--- a/src/libstd/sync/mpmc_bounded_queue.rs
+++ b/src/libstd/sync/mpmc_bounded_queue.rs
@@ -31,10 +31,10 @@
 
 use clone::Clone;
 use kinds::Send;
-use num::{Real, Round};
 use option::{Option, Some, None};
 use sync::arc::UnsafeArc;
 use sync::atomics::{AtomicUint,Relaxed,Release,Acquire};
+use uint;
 use vec;
 
 struct Node<T> {
@@ -64,7 +64,7 @@ impl<T: Send> State<T> {
                 2u
             } else {
                 // use next power of 2 as capacity
-                2f64.pow(&((capacity as f64).log2().ceil())) as uint
+                uint::next_power_of_two(capacity)
             }
         } else {
             capacity