1 use core::num::Wrapping;
2 use core::ops::Mul;
3 use {CheckedMul, One};
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     /// ```
pow(self, rhs: RHS) -> Self::Output18     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 #[cfg(has_i128)]
103 pow_impl!(u128, u8, u32, u128::pow);
104 #[cfg(has_i128)]
105 pow_impl!(u128, u16, u32, u128::pow);
106 #[cfg(has_i128)]
107 pow_impl!(u128, u32, u32, u128::pow);
108 #[cfg(has_i128)]
109 pow_impl!(u128, usize);
110 
111 #[cfg(has_i128)]
112 pow_impl!(i128, u8, u32, i128::pow);
113 #[cfg(has_i128)]
114 pow_impl!(i128, u16, u32, i128::pow);
115 #[cfg(has_i128)]
116 pow_impl!(i128, u32, u32, i128::pow);
117 #[cfg(has_i128)]
118 pow_impl!(i128, usize);
119 
120 pow_impl!(usize, u8, u32, usize::pow);
121 pow_impl!(usize, u16, u32, usize::pow);
122 pow_impl!(usize, u32, u32, usize::pow);
123 pow_impl!(usize, usize);
124 pow_impl!(isize, u8, u32, isize::pow);
125 pow_impl!(isize, u16, u32, isize::pow);
126 pow_impl!(isize, u32, u32, isize::pow);
127 pow_impl!(isize, usize);
128 pow_impl!(Wrapping<u8>);
129 pow_impl!(Wrapping<i8>);
130 pow_impl!(Wrapping<u16>);
131 pow_impl!(Wrapping<i16>);
132 pow_impl!(Wrapping<u32>);
133 pow_impl!(Wrapping<i32>);
134 pow_impl!(Wrapping<u64>);
135 pow_impl!(Wrapping<i64>);
136 #[cfg(has_i128)]
137 pow_impl!(Wrapping<u128>);
138 #[cfg(has_i128)]
139 pow_impl!(Wrapping<i128>);
140 pow_impl!(Wrapping<usize>);
141 pow_impl!(Wrapping<isize>);
142 
143 // FIXME: these should be possible
144 // pow_impl!(u8, u64);
145 // pow_impl!(i16, u64);
146 // pow_impl!(i8, u64);
147 // pow_impl!(u16, u64);
148 // pow_impl!(u32, u64);
149 // pow_impl!(i32, u64);
150 // pow_impl!(u64, u64);
151 // pow_impl!(i64, u64);
152 // pow_impl!(usize, u64);
153 // pow_impl!(isize, u64);
154 
155 #[cfg(any(feature = "std", feature = "libm"))]
156 mod float_impls {
157     use super::Pow;
158     use Float;
159 
160     pow_impl!(f32, i8, i32, <f32 as Float>::powi);
161     pow_impl!(f32, u8, i32, <f32 as Float>::powi);
162     pow_impl!(f32, i16, i32, <f32 as Float>::powi);
163     pow_impl!(f32, u16, i32, <f32 as Float>::powi);
164     pow_impl!(f32, i32, i32, <f32 as Float>::powi);
165     pow_impl!(f64, i8, i32, <f64 as Float>::powi);
166     pow_impl!(f64, u8, i32, <f64 as Float>::powi);
167     pow_impl!(f64, i16, i32, <f64 as Float>::powi);
168     pow_impl!(f64, u16, i32, <f64 as Float>::powi);
169     pow_impl!(f64, i32, i32, <f64 as Float>::powi);
170     pow_impl!(f32, f32, f32, <f32 as Float>::powf);
171     pow_impl!(f64, f32, f64, <f64 as Float>::powf);
172     pow_impl!(f64, f64, f64, <f64 as Float>::powf);
173 }
174 
175 /// Raises a value to the power of exp, using exponentiation by squaring.
176 ///
177 /// Note that `0⁰` (`pow(0, 0)`) returns `1`. Mathematically this is undefined.
178 ///
179 /// # Example
180 ///
181 /// ```rust
182 /// use num_traits::pow;
183 ///
184 /// assert_eq!(pow(2i8, 4), 16);
185 /// assert_eq!(pow(6u8, 3), 216);
186 /// assert_eq!(pow(0u8, 0), 1); // Be aware if this case affects you
187 /// ```
188 #[inline]
pow<T: Clone + One + Mul<T, Output = T>>(mut base: T, mut exp: usize) -> T189 pub fn pow<T: Clone + One + Mul<T, Output = T>>(mut base: T, mut exp: usize) -> T {
190     if exp == 0 {
191         return T::one();
192     }
193 
194     while exp & 1 == 0 {
195         base = base.clone() * base;
196         exp >>= 1;
197     }
198     if exp == 1 {
199         return base;
200     }
201 
202     let mut acc = base.clone();
203     while exp > 1 {
204         exp >>= 1;
205         base = base.clone() * base;
206         if exp & 1 == 1 {
207             acc = acc * base.clone();
208         }
209     }
210     acc
211 }
212 
213 /// Raises a value to the power of exp, returning `None` if an overflow occurred.
214 ///
215 /// Note that `0⁰` (`checked_pow(0, 0)`) returns `Some(1)`. Mathematically this is undefined.
216 ///
217 /// Otherwise same as the `pow` function.
218 ///
219 /// # Example
220 ///
221 /// ```rust
222 /// use num_traits::checked_pow;
223 ///
224 /// assert_eq!(checked_pow(2i8, 4), Some(16));
225 /// assert_eq!(checked_pow(7i8, 8), None);
226 /// assert_eq!(checked_pow(7u32, 8), Some(5_764_801));
227 /// assert_eq!(checked_pow(0u32, 0), Some(1)); // Be aware if this case affect you
228 /// ```
229 #[inline]
checked_pow<T: Clone + One + CheckedMul>(mut base: T, mut exp: usize) -> Option<T>230 pub fn checked_pow<T: Clone + One + CheckedMul>(mut base: T, mut exp: usize) -> Option<T> {
231     if exp == 0 {
232         return Some(T::one());
233     }
234 
235     macro_rules! optry {
236         ($expr:expr) => {
237             if let Some(val) = $expr {
238                 val
239             } else {
240                 return None;
241             }
242         };
243     }
244 
245     while exp & 1 == 0 {
246         base = optry!(base.checked_mul(&base));
247         exp >>= 1;
248     }
249     if exp == 1 {
250         return Some(base);
251     }
252 
253     let mut acc = base.clone();
254     while exp > 1 {
255         exp >>= 1;
256         base = optry!(base.checked_mul(&base));
257         if exp & 1 == 1 {
258             acc = optry!(acc.checked_mul(&base));
259         }
260     }
261     Some(acc)
262 }
263