malachite_base/num/arithmetic/
mod_power_of_2_sum.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::ModPowerOf2Sum;
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11
12// Since $2^k$ divides $2^W$, where $W$ is the width of `T`, wrapping addition followed by a single
13// reduction gives the sum modulo $2^k$.
14fn mod_power_of_2_sum<T: PrimitiveUnsigned, I: Iterator<Item = T>>(xs: I, pow: u64) -> T {
15    assert!(pow <= T::WIDTH);
16    xs.fold(T::ZERO, |s, x| {
17        assert!(
18            x.significant_bits() <= pow,
19            "x must be reduced mod 2^pow, but {x} >= 2^{pow}"
20        );
21        s.wrapping_add(x)
22    })
23    .mod_power_of_2(pow)
24}
25
26macro_rules! impl_mod_power_of_2_sum {
27    ($t:ident) => {
28        impl ModPowerOf2Sum for $t {
29            /// Adds up all the numbers in an iterator, modulo $2^k$. Every number must be already
30            /// reduced modulo $2^k$.
31            ///
32            /// $f((x_i)_ {i=0}^{n-1}, k) = y$, where $y < 2^k$ and $\sum_ {i=0}^{n-1} x_i \equiv y
33            /// \mod 2^k$.
34            ///
35            /// # Worst-case complexity
36            /// $T(n) = O(n)$
37            ///
38            /// $M(n) = O(1)$
39            ///
40            /// where $T$ is time, $M$ is additional memory, and $n$ is `xs.count()`.
41            ///
42            /// # Panics
43            /// Panics if `pow` is greater than `Self::WIDTH` or if any number is greater than or
44            /// equal to $2^k$.
45            ///
46            /// # Examples
47            /// See [here](super::mod_power_of_2_sum#mod_power_of_2_sum).
48            #[inline]
49            fn mod_power_of_2_sum<I: Iterator<Item = $t>>(xs: I, pow: u64) -> $t {
50                mod_power_of_2_sum(xs, pow)
51            }
52        }
53
54        impl<'a> ModPowerOf2Sum<&'a $t> for $t {
55            /// Adds up all the numbers in an iterator of references, modulo $2^k$. Every number
56            /// must be already reduced modulo $2^k$.
57            ///
58            /// $f((x_i)_ {i=0}^{n-1}, k) = y$, where $y < 2^k$ and $\sum_ {i=0}^{n-1} x_i \equiv y
59            /// \mod 2^k$.
60            ///
61            /// # Worst-case complexity
62            /// $T(n) = O(n)$
63            ///
64            /// $M(n) = O(1)$
65            ///
66            /// where $T$ is time, $M$ is additional memory, and $n$ is `xs.count()`.
67            ///
68            /// # Panics
69            /// Panics if `pow` is greater than `Self::WIDTH` or if any number is greater than or
70            /// equal to $2^k$.
71            ///
72            /// # Examples
73            /// See [here](super::mod_power_of_2_sum#mod_power_of_2_sum).
74            #[inline]
75            fn mod_power_of_2_sum<I: Iterator<Item = &'a $t>>(xs: I, pow: u64) -> $t {
76                mod_power_of_2_sum(xs.copied(), pow)
77            }
78        }
79    };
80}
81apply_to_unsigneds!(impl_mod_power_of_2_sum);
malachite_base/num/arithmetic/mod_power_of_2_sum.rs

malachite_base/num/arithmetic/
mod_power_of_2_sum.rs
