| 1 |
use crate::{CheckedMul, One}; |
| 2 |
use core::num::Wrapping; |
| 3 |
use core::ops::Mul; |
| 4 |
|
| 5 |
/// Binary operator for raising a value to a power. |
| 6 |
pub trait Pow<RHS> { |
| 7 |
/// The result after applying the operator. |
| 8 |
type Output; |
| 9 |
|
| 10 |
/// Returns `self` to the power `rhs`. |
| 11 |
/// |
| 12 |
/// # Examples |
| 13 |
/// |
| 14 |
/// ``` |
| 15 |
/// use num_traits::Pow; |
| 16 |
/// assert_eq!(Pow::pow(10u32, 2u32), 100); |
| 17 |
/// ``` |
| 18 |
fn pow(self, rhs: RHS) -> Self::Output; |
| 19 |
} |
| 20 |
|
| 21 |
macro_rules! pow_impl { |
| 22 |
($t:ty) => { |
| 23 |
pow_impl!($t, u8); |
| 24 |
pow_impl!($t, usize); |
| 25 |
|
| 26 |
// FIXME: these should be possible |
| 27 |
// pow_impl!($t, u16); |
| 28 |
// pow_impl!($t, u32); |
| 29 |
// pow_impl!($t, u64); |
| 30 |
}; |
| 31 |
($t:ty, $rhs:ty) => { |
| 32 |
pow_impl!($t, $rhs, usize, pow); |
| 33 |
}; |
| 34 |
($t:ty, $rhs:ty, $desired_rhs:ty, $method:expr) => { |
| 35 |
impl Pow<$rhs> for $t { |
| 36 |
type Output = $t; |
| 37 |
#[inline] |
| 38 |
fn pow(self, rhs: $rhs) -> $t { |
| 39 |
($method)(self, <$desired_rhs>::from(rhs)) |
| 40 |
} |
| 41 |
} |
| 42 |
|
| 43 |
impl<'a> Pow<&'a $rhs> for $t { |
| 44 |
type Output = $t; |
| 45 |
#[inline] |
| 46 |
fn pow(self, rhs: &'a $rhs) -> $t { |
| 47 |
($method)(self, <$desired_rhs>::from(*rhs)) |
| 48 |
} |
| 49 |
} |
| 50 |
|
| 51 |
impl<'a> Pow<$rhs> for &'a $t { |
| 52 |
type Output = $t; |
| 53 |
#[inline] |
| 54 |
fn pow(self, rhs: $rhs) -> $t { |
| 55 |
($method)(*self, <$desired_rhs>::from(rhs)) |
| 56 |
} |
| 57 |
} |
| 58 |
|
| 59 |
impl<'a, 'b> Pow<&'a $rhs> for &'b $t { |
| 60 |
type Output = $t; |
| 61 |
#[inline] |
| 62 |
fn pow(self, rhs: &'a $rhs) -> $t { |
| 63 |
($method)(*self, <$desired_rhs>::from(*rhs)) |
| 64 |
} |
| 65 |
} |
| 66 |
}; |
| 67 |
} |
| 68 |
|
| 69 |
pow_impl!(u8, u8, u32, u8::pow); |
| 70 |
pow_impl!(u8, u16, u32, u8::pow); |
| 71 |
pow_impl!(u8, u32, u32, u8::pow); |
| 72 |
pow_impl!(u8, usize); |
| 73 |
pow_impl!(i8, u8, u32, i8::pow); |
| 74 |
pow_impl!(i8, u16, u32, i8::pow); |
| 75 |
pow_impl!(i8, u32, u32, i8::pow); |
| 76 |
pow_impl!(i8, usize); |
| 77 |
pow_impl!(u16, u8, u32, u16::pow); |
| 78 |
pow_impl!(u16, u16, u32, u16::pow); |
| 79 |
pow_impl!(u16, u32, u32, u16::pow); |
| 80 |
pow_impl!(u16, usize); |
| 81 |
pow_impl!(i16, u8, u32, i16::pow); |
| 82 |
pow_impl!(i16, u16, u32, i16::pow); |
| 83 |
pow_impl!(i16, u32, u32, i16::pow); |
| 84 |
pow_impl!(i16, usize); |
| 85 |
pow_impl!(u32, u8, u32, u32::pow); |
| 86 |
pow_impl!(u32, u16, u32, u32::pow); |
| 87 |
pow_impl!(u32, u32, u32, u32::pow); |
| 88 |
pow_impl!(u32, usize); |
| 89 |
pow_impl!(i32, u8, u32, i32::pow); |
| 90 |
pow_impl!(i32, u16, u32, i32::pow); |
| 91 |
pow_impl!(i32, u32, u32, i32::pow); |
| 92 |
pow_impl!(i32, usize); |
| 93 |
pow_impl!(u64, u8, u32, u64::pow); |
| 94 |
pow_impl!(u64, u16, u32, u64::pow); |
| 95 |
pow_impl!(u64, u32, u32, u64::pow); |
| 96 |
pow_impl!(u64, usize); |
| 97 |
pow_impl!(i64, u8, u32, i64::pow); |
| 98 |
pow_impl!(i64, u16, u32, i64::pow); |
| 99 |
pow_impl!(i64, u32, u32, i64::pow); |
| 100 |
pow_impl!(i64, usize); |
| 101 |
|
| 102 |
pow_impl!(u128, u8, u32, u128::pow); |
| 103 |
pow_impl!(u128, u16, u32, u128::pow); |
| 104 |
pow_impl!(u128, u32, u32, u128::pow); |
| 105 |
pow_impl!(u128, usize); |
| 106 |
|
| 107 |
pow_impl!(i128, u8, u32, i128::pow); |
| 108 |
pow_impl!(i128, u16, u32, i128::pow); |
| 109 |
pow_impl!(i128, u32, u32, i128::pow); |
| 110 |
pow_impl!(i128, usize); |
| 111 |
|
| 112 |
pow_impl!(usize, u8, u32, usize::pow); |
| 113 |
pow_impl!(usize, u16, u32, usize::pow); |
| 114 |
pow_impl!(usize, u32, u32, usize::pow); |
| 115 |
pow_impl!(usize, usize); |
| 116 |
pow_impl!(isize, u8, u32, isize::pow); |
| 117 |
pow_impl!(isize, u16, u32, isize::pow); |
| 118 |
pow_impl!(isize, u32, u32, isize::pow); |
| 119 |
pow_impl!(isize, usize); |
| 120 |
pow_impl!(Wrapping<u8>); |
| 121 |
pow_impl!(Wrapping<i8>); |
| 122 |
pow_impl!(Wrapping<u16>); |
| 123 |
pow_impl!(Wrapping<i16>); |
| 124 |
pow_impl!(Wrapping<u32>); |
| 125 |
pow_impl!(Wrapping<i32>); |
| 126 |
pow_impl!(Wrapping<u64>); |
| 127 |
pow_impl!(Wrapping<i64>); |
| 128 |
pow_impl!(Wrapping<u128>); |
| 129 |
pow_impl!(Wrapping<i128>); |
| 130 |
pow_impl!(Wrapping<usize>); |
| 131 |
pow_impl!(Wrapping<isize>); |
| 132 |
|
| 133 |
// FIXME: these should be possible |
| 134 |
// pow_impl!(u8, u64); |
| 135 |
// pow_impl!(i16, u64); |
| 136 |
// pow_impl!(i8, u64); |
| 137 |
// pow_impl!(u16, u64); |
| 138 |
// pow_impl!(u32, u64); |
| 139 |
// pow_impl!(i32, u64); |
| 140 |
// pow_impl!(u64, u64); |
| 141 |
// pow_impl!(i64, u64); |
| 142 |
// pow_impl!(usize, u64); |
| 143 |
// pow_impl!(isize, u64); |
| 144 |
|
| 145 |
#[cfg(any(feature = "std", feature = "libm"))] |
| 146 |
mod float_impls { |
| 147 |
use super::Pow; |
| 148 |
use crate::Float; |
| 149 |
|
| 150 |
pow_impl!(f32, i8, i32, <f32 as Float>::powi); |
| 151 |
pow_impl!(f32, u8, i32, <f32 as Float>::powi); |
| 152 |
pow_impl!(f32, i16, i32, <f32 as Float>::powi); |
| 153 |
pow_impl!(f32, u16, i32, <f32 as Float>::powi); |
| 154 |
pow_impl!(f32, i32, i32, <f32 as Float>::powi); |
| 155 |
pow_impl!(f64, i8, i32, <f64 as Float>::powi); |
| 156 |
pow_impl!(f64, u8, i32, <f64 as Float>::powi); |
| 157 |
pow_impl!(f64, i16, i32, <f64 as Float>::powi); |
| 158 |
pow_impl!(f64, u16, i32, <f64 as Float>::powi); |
| 159 |
pow_impl!(f64, i32, i32, <f64 as Float>::powi); |
| 160 |
pow_impl!(f32, f32, f32, <f32 as Float>::powf); |
| 161 |
pow_impl!(f64, f32, f64, <f64 as Float>::powf); |
| 162 |
pow_impl!(f64, f64, f64, <f64 as Float>::powf); |
| 163 |
} |
| 164 |
|
| 165 |
/// Raises a value to the power of exp, using exponentiation by squaring. |
| 166 |
/// |
| 167 |
/// Note that `0⁰` (`pow(0, 0)`) returns `1`. Mathematically this is undefined. |
| 168 |
/// |
| 169 |
/// # Example |
| 170 |
/// |
| 171 |
/// ```rust |
| 172 |
/// use num_traits::pow; |
| 173 |
/// |
| 174 |
/// assert_eq!(pow(2i8, 4), 16); |
| 175 |
/// assert_eq!(pow(6u8, 3), 216); |
| 176 |
/// assert_eq!(pow(0u8, 0), 1); // Be aware if this case affects you |
| 177 |
/// ``` |
| 178 |
#[inline] |
| 179 |
pub fn pow<T: Clone + One + Mul<T, Output = T>>(mut base: T, mut exp: usize) -> T { |
| 180 |
if exp == 0 { |
| 181 |
return T::one(); |
| 182 |
} |
| 183 |
|
| 184 |
while exp & 1 == 0 { |
| 185 |
base = base.clone() * base; |
| 186 |
exp >>= 1; |
| 187 |
} |
| 188 |
if exp == 1 { |
| 189 |
return base; |
| 190 |
} |
| 191 |
|
| 192 |
let mut acc = base.clone(); |
| 193 |
while exp > 1 { |
| 194 |
exp >>= 1; |
| 195 |
base = base.clone() * base; |
| 196 |
if exp & 1 == 1 { |
| 197 |
acc = acc * base.clone(); |
| 198 |
} |
| 199 |
} |
| 200 |
acc |
| 201 |
} |
| 202 |
|
| 203 |
/// Raises a value to the power of exp, returning `None` if an overflow occurred. |
| 204 |
/// |
| 205 |
/// Note that `0⁰` (`checked_pow(0, 0)`) returns `Some(1)`. Mathematically this is undefined. |
| 206 |
/// |
| 207 |
/// Otherwise same as the `pow` function. |
| 208 |
/// |
| 209 |
/// # Example |
| 210 |
/// |
| 211 |
/// ```rust |
| 212 |
/// use num_traits::checked_pow; |
| 213 |
/// |
| 214 |
/// assert_eq!(checked_pow(2i8, 4), Some(16)); |
| 215 |
/// assert_eq!(checked_pow(7i8, 8), None); |
| 216 |
/// assert_eq!(checked_pow(7u32, 8), Some(5_764_801)); |
| 217 |
/// assert_eq!(checked_pow(0u32, 0), Some(1)); // Be aware if this case affect you |
| 218 |
/// ``` |
| 219 |
#[inline] |
| 220 |
pub fn checked_pow<T: Clone + One + CheckedMul>(mut base: T, mut exp: usize) -> Option<T> { |
| 221 |
if exp == 0 { |
| 222 |
return Some(T::one()); |
| 223 |
} |
| 224 |
|
| 225 |
while exp & 1 == 0 { |
| 226 |
base = base.checked_mul(&base)?; |
| 227 |
exp >>= 1; |
| 228 |
} |
| 229 |
if exp == 1 { |
| 230 |
return Some(base); |
| 231 |
} |
| 232 |
|
| 233 |
let mut acc = base.clone(); |
| 234 |
while exp > 1 { |
| 235 |
exp >>= 1; |
| 236 |
base = base.checked_mul(&base)?; |
| 237 |
if exp & 1 == 1 { |
| 238 |
acc = acc.checked_mul(&base)?; |
| 239 |
} |
| 240 |
} |
| 241 |
Some(acc) |
| 242 |
} |