malachite_base/num/arithmetic/
mod_add_mul_shl.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::{ModAddMulShl, ModAddMulShlAssign, ModShl};
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11
12fn assert_reduced<T: PrimitiveUnsigned>(x: T, y: T, z: T, m: T) {
13    assert!(x < m, "x must be reduced mod m, but {x} >= {m}");
14    assert!(y < m, "y must be reduced mod m, but {y} >= {m}");
15    assert!(z < m, "z must be reduced mod m, but {z} >= {m}");
16}
17
18fn mod_add_mul_shl<T: PrimitiveUnsigned + ModShl<u64, T, Output = T>>(
19    x: T,
20    y: T,
21    z: T,
22    bits: u64,
23    m: T,
24) -> T {
25    assert_reduced(x, y, z, m);
26    x.mod_add(y.mod_mul(z, m).mod_shl(bits, m), m)
27}
28
29macro_rules! impl_mod_add_mul_shl {
30    ($t:ident) => {
31        impl ModAddMulShl<$t> for $t {
32            type Output = $t;
33
34            /// Adds a number and the product of two other numbers, shifted left by `bits`, modulo a
35            /// fourth number $m$. All three inputs must be already reduced modulo $m$.
36            ///
37            /// $f(x, y, z, b, m) = w$, where $x, y, z, w < m$ and $x + yz2^b \equiv w \mod m$.
38            ///
39            /// # Worst-case complexity
40            /// $T(n) = O(n)$
41            ///
42            /// $M(n) = O(1)$
43            ///
44            /// where $T$ is time, $M$ is additional memory, and $n$ is `bits.significant_bits()`.
45            ///
46            /// # Panics
47            /// Panics if `self`, `y`, or `z` are greater than or equal to `m`.
48            ///
49            /// # Examples
50            /// See [here](super::mod_add_mul_shl#mod_add_mul_shl).
51            #[inline]
52            fn mod_add_mul_shl(self, y: $t, z: $t, bits: u64, m: $t) -> $t {
53                mod_add_mul_shl(self, y, z, bits, m)
54            }
55        }
56
57        impl ModAddMulShlAssign<$t> for $t {
58            /// Adds the product of two numbers, shifted left by `bits`, to a third number modulo a
59            /// fourth number $m$, in place. All three inputs must be already reduced modulo $m$.
60            ///
61            /// $x \gets w$, where $x, y, z, w < m$ and $x + yz2^b \equiv w \mod m$.
62            ///
63            /// # Worst-case complexity
64            /// $T(n) = O(n)$
65            ///
66            /// $M(n) = O(1)$
67            ///
68            /// where $T$ is time, $M$ is additional memory, and $n$ is `bits.significant_bits()`.
69            ///
70            /// # Panics
71            /// Panics if `self`, `y`, or `z` are greater than or equal to `m`.
72            ///
73            /// # Examples
74            /// See [here](super::mod_add_mul_shl#mod_add_mul_shl_assign).
75            #[inline]
76            fn mod_add_mul_shl_assign(&mut self, y: $t, z: $t, bits: u64, m: $t) {
77                *self = mod_add_mul_shl(*self, y, z, bits, m);
78            }
79        }
80    };
81}
82apply_to_unsigneds!(impl_mod_add_mul_shl);
malachite_base/num/arithmetic/mod_add_mul_shl.rs

malachite_base/num/arithmetic/
mod_add_mul_shl.rs
