malachite_base/num/arithmetic/
wrapping_pow.rs

1// Copyright © 2025 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::num::arithmetic::traits::{Parity, UnsignedAbs, WrappingPow, WrappingPowAssign};
10use crate::num::basic::signeds::PrimitiveSigned;
11use crate::num::basic::unsigneds::PrimitiveUnsigned;
12use crate::num::conversion::traits::WrappingFrom;
13use crate::num::logic::traits::BitIterable;
14
15fn wrapping_pow_unsigned<T: PrimitiveUnsigned>(x: T, exp: u64) -> T {
16    if exp == 0 {
17        T::ONE
18    } else if x < T::TWO {
19        x
20    } else {
21        let mut power = x;
22        for bit in exp.bits().rev().skip(1) {
23            power.wrapping_square_assign();
24            if bit {
25                power.wrapping_mul_assign(x);
26            }
27        }
28        power
29    }
30}
31
32fn wrapping_pow_signed<
33    U: PrimitiveUnsigned,
34    S: PrimitiveSigned + UnsignedAbs<Output = U> + WrappingFrom<U>,
35>(
36    x: S,
37    exp: u64,
38) -> S {
39    let p_abs = x.unsigned_abs().wrapping_pow(exp);
40    if x >= S::ZERO || exp.even() {
41        S::wrapping_from(p_abs)
42    } else {
43        S::wrapping_from(p_abs).wrapping_neg()
44    }
45}
46
47macro_rules! impl_wrapping_pow_unsigned {
48    ($t:ident) => {
49        impl WrappingPow<u64> for $t {
50            type Output = $t;
51
52            /// This is a wrapper over the `wrapping_pow` functions in the standard library, for
53            /// example [this one](u32::wrapping_pow).
54            #[inline]
55            fn wrapping_pow(self, exp: u64) -> $t {
56                wrapping_pow_unsigned(self, exp)
57            }
58        }
59    };
60}
61apply_to_unsigneds!(impl_wrapping_pow_unsigned);
62
63macro_rules! impl_wrapping_pow_signed {
64    ($t:ident) => {
65        impl WrappingPow<u64> for $t {
66            type Output = $t;
67
68            /// This is a wrapper over the `wrapping_pow` functions in the standard library, for
69            /// example [this one](i32::wrapping_pow).
70            #[inline]
71            fn wrapping_pow(self, exp: u64) -> $t {
72                wrapping_pow_signed(self, exp)
73            }
74        }
75    };
76}
77apply_to_signeds!(impl_wrapping_pow_signed);
78
79macro_rules! impl_wrapping_pow_primitive_int {
80    ($t:ident) => {
81        impl WrappingPowAssign<u64> for $t {
82            /// Raises a number to a power, in place, wrapping around at the boundary of the type.
83            ///
84            /// $x \gets y$, where $y \equiv x^n \mod 2^W$ and $W$ is `Self::WIDTH`.
85            ///
86            /// # Worst-case complexity
87            /// Constant time and additional memory.
88            ///
89            /// # Examples
90            /// See [here](super::wrapping_pow#wrapping_pow_assign).
91            #[inline]
92            fn wrapping_pow_assign(&mut self, exp: u64) {
93                *self = WrappingPow::wrapping_pow(*self, exp);
94            }
95        }
96    };
97}
98apply_to_primitive_ints!(impl_wrapping_pow_primitive_int);
malachite_base/num/arithmetic/wrapping_pow.rs

malachite_base/num/arithmetic/
wrapping_pow.rs
