From cf56624a4ad7703c8f3fc327b8c385da0a803ea5 Mon Sep 17 00:00:00 2001 From: Brendan Zabarauskas Date: Sat, 18 Jan 2014 17:08:23 +1100 Subject: Add operator trait constraints to std::num::{Zero, One} and document their appropriate use Zero and One have precise definitions in mathematics. Documentation has been added to describe the appropriate uses for these traits and the laws that they should satisfy. For more information regarding these identities, see the following wikipedia pages: - http://wikipedia.org/wiki/Additive_identity - http://wikipedia.org/wiki/Multiplicative_identity --- src/libstd/bool.rs | 7 ------ src/libstd/char.rs | 10 --------- src/libstd/iter.rs | 6 +++++ src/libstd/num/mod.rs | 62 ++++++++++++++++++++++++++++++++++++++------------- src/libstd/tuple.rs | 13 ----------- src/libstd/unit.rs | 10 --------- 6 files changed, 52 insertions(+), 56 deletions(-) (limited to 'src/libstd') diff --git a/src/libstd/bool.rs b/src/libstd/bool.rs index d080262ccc7..af745f94fb5 100644 --- a/src/libstd/bool.rs +++ b/src/libstd/bool.rs @@ -40,7 +40,6 @@ use num::FromPrimitive; #[cfg(not(test))] use cmp::{Eq, Ord, TotalOrd, Ordering}; #[cfg(not(test))] use ops::{Not, BitAnd, BitOr, BitXor}; #[cfg(not(test))] use default::Default; -#[cfg(not(test))] use num::Zero; ///////////////////////////////////////////////////////////////////////////// // Freestanding functions @@ -309,12 +308,6 @@ impl Default for bool { fn default() -> bool { false } } -#[cfg(not(test))] -impl Zero for bool { - fn zero() -> bool { false } - fn is_zero(&self) -> bool { *self == false } -} - #[cfg(test)] mod tests { use prelude::*; diff --git a/src/libstd/char.rs b/src/libstd/char.rs index 4e9c72de618..71a297d7176 100644 --- a/src/libstd/char.rs +++ b/src/libstd/char.rs @@ -22,7 +22,6 @@ use str; #[cfg(not(test))] use cmp::{Eq, Ord}; #[cfg(not(test))] use default::Default; -#[cfg(not(test))] use num::Zero; // UTF-8 ranges and tags for encoding characters static TAG_CONT: uint = 128u; @@ -449,15 +448,6 @@ impl Default for char { fn default() -> char { '\x00' } } -#[cfg(not(test))] -impl Zero for char { - #[inline] - fn zero() -> char { '\x00' } - - #[inline] - fn is_zero(&self) -> bool { *self == '\x00' } -} - #[test] fn test_is_lowercase() { assert!('a'.is_lowercase()); diff --git a/src/libstd/iter.rs b/src/libstd/iter.rs index fcf0f4f2444..8081c6ed8db 100644 --- a/src/libstd/iter.rs +++ b/src/libstd/iter.rs @@ -2872,6 +2872,12 @@ mod tests { } } + impl Mul for Foo { + fn mul(&self, _: &Foo) -> Foo { + Foo + } + } + impl num::One for Foo { fn one() -> Foo { Foo diff --git a/src/libstd/num/mod.rs b/src/libstd/num/mod.rs index c374d6c2157..23a852cc357 100644 --- a/src/libstd/num/mod.rs +++ b/src/libstd/num/mod.rs @@ -50,19 +50,59 @@ pub trait Orderable: Ord { /// Returns the number constrained within the range `mn <= self <= mx`. #[inline(always)] pub fn clamp(value: T, mn: T, mx: T) -> T { value.clamp(&mn, &mx) } -pub trait Zero { - fn zero() -> Self; // FIXME (#5527): This should be an associated constant +/// Defines an additive identity element for `Self`. +/// +/// # Deriving +/// +/// This trait can be automatically be derived using `#[deriving(Zero)]` +/// attribute. If you choose to use this, make sure that the laws outlined in +/// the documentation for `Zero::zero` still hold. +pub trait Zero: Add { + /// Returns the additive identity element of `Self`, `0`. + /// + /// # Laws + /// + /// ~~~ + /// a + 0 = a ∀ a ∈ Self + /// 0 + a = a ∀ a ∈ Self + /// ~~~ + /// + /// # Purity + /// + /// This function should return the same result at all times regardless of + /// external mutable state, for example values stored in TLS or in + /// `static mut`s. + // FIXME (#5527): This should be an associated constant + fn zero() -> Self; + + /// Returns `true` if `self` is equal to the additive identity. fn is_zero(&self) -> bool; } -/// Returns `0` of appropriate type. +/// Returns the additive identity, `0`. #[inline(always)] pub fn zero() -> T { Zero::zero() } -pub trait One { - fn one() -> Self; // FIXME (#5527): This should be an associated constant +/// Defines a multiplicative identity element for `Self`. +pub trait One: Mul { + /// Returns the multiplicative identity element of `Self`, `1`. + /// + /// # Laws + /// + /// ~~~ + /// a * 1 = a ∀ a ∈ Self + /// 1 * a = a ∀ a ∈ Self + /// ~~~ + /// + /// # Purity + /// + /// This function should return the same result at all times regardless of + /// external mutable state, for example values stored in TLS or in + /// `static mut`s. + // FIXME (#5527): This should be an associated constant + fn one() -> Self; } -/// Returns `1` of appropriate type. +/// Returns the multiplicative identity, `1`. #[inline(always)] pub fn one() -> T { One::one() } pub trait Signed: Num @@ -993,16 +1033,6 @@ pub fn from_str_radix(str: &str, radix: uint) -> Option { FromStrRadix::from_str_radix(str, radix) } -impl Zero for @T { - fn zero() -> @T { @Zero::zero() } - fn is_zero(&self) -> bool { (**self).is_zero() } -} - -impl Zero for ~T { - fn zero() -> ~T { ~Zero::zero() } - fn is_zero(&self) -> bool { (**self).is_zero() } -} - /// Saturating math operations pub trait Saturating { /// Saturating addition operator. diff --git a/src/libstd/tuple.rs b/src/libstd/tuple.rs index 313fd9c79b4..8e278aeb2ea 100644 --- a/src/libstd/tuple.rs +++ b/src/libstd/tuple.rs @@ -15,7 +15,6 @@ use clone::Clone; #[cfg(not(test))] use cmp::*; #[cfg(not(test))] use default::Default; -#[cfg(not(test))] use num::Zero; /// Method extensions to pairs where both types satisfy the `Clone` bound pub trait CopyableTuple { @@ -177,18 +176,6 @@ macro_rules! tuple_impls { ($({ let x: $T = Default::default(); x},)+) } } - - #[cfg(not(test))] - impl<$($T:Zero),+> Zero for ($($T,)+) { - #[inline] - fn zero() -> ($($T,)+) { - ($({ let x: $T = Zero::zero(); x},)+) - } - #[inline] - fn is_zero(&self) -> bool { - $(self.$get_ref_fn().is_zero())&&+ - } - } )+ } } diff --git a/src/libstd/unit.rs b/src/libstd/unit.rs index c27f6e3d086..786a7f42bb3 100644 --- a/src/libstd/unit.rs +++ b/src/libstd/unit.rs @@ -12,8 +12,6 @@ #[cfg(not(test))] use prelude::*; -#[cfg(not(test))] -use num::Zero; #[cfg(not(test))] impl Eq for () { @@ -46,11 +44,3 @@ impl Default for () { #[inline] fn default() -> () { () } } - -#[cfg(not(test))] -impl Zero for () { - #[inline] - fn zero() -> () { () } - #[inline] - fn is_zero(&self) -> bool { true } -} -- cgit 1.4.1-3-g733a5 From 509283d149bb81cad728b2c1b81f7ab8ceb206e1 Mon Sep 17 00:00:00 2001 From: Brendan Zabarauskas Date: Mon, 20 Jan 2014 00:39:05 +1100 Subject: Improve std::num::pow implementation The implementation has been made more succinct and no longer requires Clone. The coverage of the associated unit test has also been increased to check more combinations of bases, exponents, and expected results. --- src/libstd/num/mod.rs | 72 +++++++++++++++++++++------------------------------ 1 file changed, 30 insertions(+), 42 deletions(-) (limited to 'src/libstd') diff --git a/src/libstd/num/mod.rs b/src/libstd/num/mod.rs index 23a852cc357..34dd313d442 100644 --- a/src/libstd/num/mod.rs +++ b/src/libstd/num/mod.rs @@ -304,48 +304,29 @@ pub trait Real: Signed fn to_radians(&self) -> Self; } -/// Raises a value to the power of exp, using -/// exponentiation by squaring. +/// 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); +/// assert_eq!(num::pow(2, 4), 16); /// ``` #[inline] -pub fn pow>(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; +pub fn pow>(mut base: T, mut exp: uint) -> T { + if exp == 1 { base } + else { + let mut acc = one::(); + while exp > 0 { + if (exp & 1) == 1 { + acc = acc * base; + } + base = base * base; + exp = exp >> 1; } - i = i >> one; - v = v * v; + acc } - - r } /// Raise a number to a power. @@ -1670,17 +1651,24 @@ mod tests { #[test] fn test_pow() { - fn assert_pow>(num: T, exp: uint) -> () { - assert_eq!(num::pow(num.clone(), exp), - range(1u, exp).fold(num.clone(), |acc, _| acc * num)); + fn naive_pow>(base: T, exp: uint) -> T { + range(0, exp).fold(one::(), |acc, _| acc * base) } - - 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); + macro_rules! assert_pow( + (($num:expr, $exp:expr) => $expected:expr) => {{ + let result = pow($num, $exp); + assert_eq!(result, $expected); + assert_eq!(result, naive_pow($num, $exp)); + }} + ) + assert_pow!((3, 0 ) => 1); + assert_pow!((5, 1 ) => 5); + assert_pow!((-4, 2 ) => 16); + assert_pow!((0.5, 5 ) => 0.03125); + assert_pow!((8, 3 ) => 512); + assert_pow!((8.0, 5 ) => 32768.0); + assert_pow!((8.5, 5 ) => 44370.53125); + assert_pow!((2u64, 50) => 1125899906842624); } } -- cgit 1.4.1-3-g733a5