malachite_base/num/arithmetic/
overflowing_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::{OverflowingPow, OverflowingPowAssign, Parity, UnsignedAbs};
10use crate::num::basic::signeds::PrimitiveSigned;
11use crate::num::basic::unsigneds::PrimitiveUnsigned;
12use crate::num::conversion::traits::OverflowingFrom;
13use crate::num::logic::traits::BitIterable;
14
15fn overflowing_pow_unsigned<T: PrimitiveUnsigned>(x: T, exp: u64) -> (T, bool) {
16    if exp == 0 {
17        (T::ONE, false)
18    } else if x < T::TWO {
19        (x, false)
20    } else {
21        let (mut power, mut overflow) = (x, false);
22        for bit in exp.bits().rev().skip(1) {
23            overflow |= power.overflowing_square_assign();
24            if bit {
25                overflow |= power.overflowing_mul_assign(x);
26            }
27        }
28        (power, overflow)
29    }
30}
31
32fn overflowing_unsigned_to_signed_neg<
33    U: PrimitiveUnsigned,
34    S: OverflowingFrom<U> + PrimitiveSigned,
35>(
36    x: U,
37) -> (S, bool) {
38    let (signed_x, overflow) = S::overflowing_from(x);
39    if signed_x == S::MIN {
40        (signed_x, false)
41    } else {
42        (signed_x.wrapping_neg(), overflow)
43    }
44}
45
46fn overflowing_pow_signed<
47    U: PrimitiveUnsigned,
48    S: OverflowingFrom<U> + PrimitiveSigned + UnsignedAbs<Output = U>,
49>(
50    x: S,
51    exp: u64,
52) -> (S, bool) {
53    let (p_abs, overflow) = OverflowingPow::overflowing_pow(x.unsigned_abs(), exp);
54    let (p, overflow_2) = if x >= S::ZERO || exp.even() {
55        S::overflowing_from(p_abs)
56    } else {
57        overflowing_unsigned_to_signed_neg(p_abs)
58    };
59    (p, overflow || overflow_2)
60}
61
62macro_rules! impl_overflowing_pow_unsigned {
63    ($t:ident) => {
64        impl OverflowingPow<u64> for $t {
65            type Output = $t;
66
67            /// This is a wrapper over the `overflowing_pow` functions in the standard library, for
68            /// example [this one](u32::overflowing_pow).
69            #[inline]
70            fn overflowing_pow(self, exp: u64) -> ($t, bool) {
71                overflowing_pow_unsigned(self, exp)
72            }
73        }
74    };
75}
76apply_to_unsigneds!(impl_overflowing_pow_unsigned);
77
78macro_rules! impl_overflowing_pow_signed {
79    ($t:ident) => {
80        impl OverflowingPow<u64> for $t {
81            type Output = $t;
82
83            /// This is a wrapper over the `overflowing_pow` functions in the standard library, for
84            /// example [this one](i32::overflowing_pow).
85            #[inline]
86            fn overflowing_pow(self, exp: u64) -> ($t, bool) {
87                overflowing_pow_signed(self, exp)
88            }
89        }
90    };
91}
92apply_to_signeds!(impl_overflowing_pow_signed);
93
94macro_rules! impl_overflowing_pow_primitive_int {
95    ($t:ident) => {
96        impl OverflowingPowAssign<u64> for $t {
97            /// Raises a number to a power, in place.
98            ///
99            /// Returns a boolean indicating whether an arithmetic overflow occurred. If an overflow
100            /// occurred, then the wrapped value is assigned.
101            ///
102            /// # Worst-case complexity
103            /// $T(n) = O(n)$
104            ///
105            /// $M(n) = O(1)$
106            ///
107            /// where $T$ is time, $M$ is additional memory, and $n$ is `exp.significant_bits()`.
108            ///
109            /// # Examples
110            /// See [here](super::overflowing_pow#overflowing_pow_assign).
111            #[inline]
112            fn overflowing_pow_assign(&mut self, exp: u64) -> bool {
113                let overflow;
114                (*self, overflow) = OverflowingPow::overflowing_pow(*self, exp);
115                overflow
116            }
117        }
118    };
119}
120apply_to_primitive_ints!(impl_overflowing_pow_primitive_int);
malachite_base/num/arithmetic/overflowing_pow.rs

malachite_base/num/arithmetic/
overflowing_pow.rs
