malachite_base/num/arithmetic/
mod_sum.rs

1// Copyright © 2026 Mikhail Hogrefe
2//
3// Uses code adopted from the FLINT Library.
4//
5//      Copyright © 2010 William Hart
6//
7//      Copyright © 2021 Fredrik Johansson
8//
9// This file is part of Malachite.
10//
11// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
12// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
13// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
14
15use crate::num::arithmetic::traits::ModSum;
16use crate::num::basic::unsigneds::PrimitiveUnsigned;
17
18fn mod_sum<T: PrimitiveUnsigned, I: Iterator<Item = T>>(xs: I, m: T) -> T {
19    assert_ne!(m, T::ZERO, "m cannot be zero");
20    xs.fold(T::ZERO, |s, x| {
21        assert!(x < m, "x must be reduced mod m, but {x} >= {m}");
22        s.mod_add(x, m)
23    })
24}
25
26macro_rules! impl_mod_sum {
27    ($t:ident) => {
28        impl ModSum for $t {
29            /// Adds up all the numbers in an iterator, modulo another number $m$. Every number must
30            /// be already reduced modulo $m$.
31            ///
32            /// $f((x_i)_ {i=0}^{n-1}, m) = y$, where $y < m$ and $\sum_ {i=0}^{n-1} x_i \equiv y
33            /// \mod m$.
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 `m` is zero or if any number is greater than or equal to `m`.
44            ///
45            /// # Examples
46            /// See [here](super::mod_sum#mod_sum).
47            #[inline]
48            fn mod_sum<I: Iterator<Item = $t>>(xs: I, m: $t) -> $t {
49                mod_sum(xs, m)
50            }
51        }
52
53        impl<'a> ModSum<&'a $t, $t> for $t {
54            /// Adds up all the numbers in an iterator of references, modulo another number $m$.
55            /// Every number must be already reduced modulo $m$.
56            ///
57            /// $f((x_i)_ {i=0}^{n-1}, m) = y$, where $y < m$ and $\sum_ {i=0}^{n-1} x_i \equiv y
58            /// \mod m$.
59            ///
60            /// # Worst-case complexity
61            /// $T(n) = O(n)$
62            ///
63            /// $M(n) = O(1)$
64            ///
65            /// where $T$ is time, $M$ is additional memory, and $n$ is `xs.count()`.
66            ///
67            /// # Panics
68            /// Panics if `m` is zero or if any number is greater than or equal to `m`.
69            ///
70            /// # Examples
71            /// See [here](super::mod_sum#mod_sum).
72            #[inline]
73            fn mod_sum<I: Iterator<Item = &'a $t>>(xs: I, m: $t) -> $t {
74                mod_sum(xs.copied(), m)
75            }
76        }
77    };
78}
79apply_to_unsigneds!(impl_mod_sum);
malachite_base/num/arithmetic/mod_sum.rs

malachite_base/num/arithmetic/
mod_sum.rs
