malachite_base/num/factorization/
remove_power.rs

1// Copyright © 2026 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};
10use crate::num::basic::signeds::PrimitiveSigned;
11use crate::num::basic::unsigneds::PrimitiveUnsigned;
12use crate::num::conversion::traits::WrappingFrom;
13use crate::num::factorization::traits::{RemovePower, RemovePowerAssign};
14
15fn remove_power_unsigned<T: PrimitiveUnsigned>(mut x: T, y: T) -> (T, u64) {
16    assert!(y > T::ONE, "Cannot remove powers of {y}");
17    if x == T::ZERO {
18        // every power of `y` divides zero, so, as GMP does, leave it alone
19        return (x, 0);
20    }
21    if y == T::TWO {
22        // the exponent is just the number of trailing zeros, which beats dividing repeatedly; GMP
23        // special-cases a factor of 2 the same way
24        let k = x.trailing_zeros();
25        return (x >> k, k);
26    }
27    let mut k = 0;
28    loop {
29        let (q, r) = x.div_mod(y);
30        if r != T::ZERO {
31            return (x, k);
32        }
33        x = q;
34        k += 1;
35    }
36}
37
38fn remove_power_signed<T: PrimitiveSigned + WrappingFrom<<T as UnsignedAbs>::Output>>(
39    x: T,
40    y: T,
41) -> (T, u64)
42where
43    <T as UnsignedAbs>::Output: PrimitiveUnsigned,
44{
45    assert!(
46        y > T::ONE || y < T::NEGATIVE_ONE,
47        "Cannot remove powers of {y}"
48    );
49    let (abs, k) = remove_power_unsigned(x.unsigned_abs(), y.unsigned_abs());
50    // The quotient is the exact division by the signed power: negative when the value is, and
51    // negated again when the factor is negative and the power is odd. Only the negative case can
52    // reach the magnitude of `T::MIN`, and there it is representable, so the wrapping conversion is
53    // exact.
54    let q = T::wrapping_from(abs);
55    (
56        if (x < T::ZERO) == (y < T::ZERO && k.odd()) {
57            q
58        } else {
59            q.wrapping_neg()
60        },
61        k,
62    )
63}
64
65macro_rules! impl_remove_power {
66    ($t:ident, $f:ident) => {
67        impl RemovePower<$t> for $t {
68            type Output = $t;
69
70            /// Removes the largest power of a factor from a number, returning the reduced number
71            /// together with the exponent of that power.
72            ///
73            /// If $f^k$ is the largest power of `other` that divides `self`, this returns
74            /// $(\text{self}/f^k, k)$. The factor need not be prime. Zero is left alone, with an
75            /// exponent of 0, since every power of the factor divides it.
76            ///
77            /// For signed types the quotient is the exact division by the signed power, so a
78            /// negative factor raised to an odd power flips its sign.
79            ///
80            /// # Worst-case complexity
81            /// $T(n) = O(n)$
82            ///
83            /// $M(n) = O(1)$
84            ///
85            /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`:
86            /// each division by `other`, which is at least 2, removes at least one bit.
87            ///
88            /// # Panics
89            /// Panics if `other` is 0 or 1, or, for signed types, -1: no largest power exists in
90            /// those cases.
91            ///
92            /// # Examples
93            /// See [here](super::remove_power#remove_power).
94            #[inline]
95            fn remove_power(self, other: $t) -> ($t, u64) {
96                $f(self, other)
97            }
98        }
99
100        impl RemovePowerAssign<$t> for $t {
101            /// Divides a number by the largest power of a factor that divides it, in place,
102            /// returning the exponent of that power.
103            ///
104            /// The factor need not be prime. Zero is left alone, with an exponent of 0.
105            ///
106            /// # Worst-case complexity
107            /// $T(n) = O(n)$
108            ///
109            /// $M(n) = O(1)$
110            ///
111            /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`:
112            /// each division by `other`, which is at least 2, removes at least one bit.
113            ///
114            /// # Panics
115            /// Panics if `other` is 0 or 1, or, for signed types, -1.
116            ///
117            /// # Examples
118            /// See [here](super::remove_power#remove_power_assign).
119            #[inline]
120            fn remove_power_assign(&mut self, other: $t) -> u64 {
121                let (q, k) = $f(*self, other);
122                *self = q;
123                k
124            }
125        }
126    };
127}
128macro_rules! impl_remove_power_unsigned {
129    ($t:ident) => {
130        impl_remove_power!($t, remove_power_unsigned);
131    };
132}
133macro_rules! impl_remove_power_signed {
134    ($t:ident) => {
135        impl_remove_power!($t, remove_power_signed);
136    };
137}
138apply_to_unsigneds!(impl_remove_power_unsigned);
139apply_to_signeds!(impl_remove_power_signed);
malachite_base/num/factorization/remove_power.rs

malachite_base/num/factorization/
remove_power.rs
