malachite_base/num/arithmetic/
mod_power_of_2_inverse.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::ModPowerOf2Inverse;
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11
12// Uses Newton's method, as described by Colin Plumb in
13// https://groups.google.com/g/sci.crypt/c/UI-UMbUnYGk/m/hX2-wQVyE3oJ.
14pub_test! {mod_power_of_2_inverse_fast<T: PrimitiveUnsigned>(x: T, pow: u64) -> Option<T> {
15    assert_ne!(x, T::ZERO);
16    assert!(pow <= T::WIDTH);
17    assert!(x.significant_bits() <= pow, "x must be reduced mod 2^pow, but {x} >= 2^{pow}");
18    if x.even() {
19        return None;
20    } else if x == T::ONE {
21        return Some(T::ONE);
22    }
23    let mut small_pow = 2;
24    let mut inverse = x.mod_power_of_2(2);
25    while small_pow < pow {
26        small_pow <<= 1;
27        if small_pow > pow {
28            small_pow = pow;
29        }
30        // inverse <- inverse * (2 - inverse * x) mod 2^small_pow
31        inverse.mod_power_of_2_mul_assign(
32            T::TWO.mod_power_of_2_sub(
33                inverse.mod_power_of_2_mul(x.mod_power_of_2(small_pow), small_pow),
34                small_pow,
35            ),
36            small_pow,
37        );
38    }
39    Some(inverse)
40}}
41
42macro_rules! impl_mod_power_of_2_inverse {
43    ($u:ident) => {
44        impl ModPowerOf2Inverse for $u {
45            type Output = $u;
46
47            /// Computes the multiplicative inverse of a number modulo $2^k$. The input must be
48            /// already reduced modulo $2^k$.
49            ///
50            /// Returns `None` if $x$ is even.
51            ///
52            /// $f(x, k) = y$, where $x, y < 2^k$, $x$ is odd, and $xy \equiv 1 \mod 2^k$.
53            ///
54            /// # Worst-case complexity
55            /// $T(n) = O(n)$
56            ///
57            /// $M(n) = O(1)$
58            ///
59            /// where $T$ is time, $M$ is additional memory, and $n$ is `pow`.
60            ///
61            /// # Panics
62            /// Panics if `pow` is greater than `Self::WIDTH`, if `self` is zero, or if `self` is
63            /// greater than or equal to $2^k$.
64            ///
65            /// # Examples
66            /// See [here](super::mod_power_of_2_inverse#mod_power_of_2_inverse).
67            #[inline]
68            fn mod_power_of_2_inverse(self, pow: u64) -> Option<$u> {
69                mod_power_of_2_inverse_fast(self, pow)
70            }
71        }
72    };
73}
74apply_to_unsigneds!(impl_mod_power_of_2_inverse);
malachite_base/num/arithmetic/mod_power_of_2_inverse.rs

malachite_base/num/arithmetic/
mod_power_of_2_inverse.rs
