malachite_base/unsigned_vector/arithmetic/
mod_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::{ModIsReduced, ModSum};
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11use crate::unsigned_vector::UnsignedVector;
12use core::borrow::Borrow;
13
14fn assert_reduced<T: PrimitiveUnsigned>(v: &UnsignedVector<T>, m: T) {
15    assert!(
16        v.mod_is_reduced(&m),
17        "every vector must be reduced mod m, but {v} has an element >= {m}"
18    );
19}
20
21// The first vector fixes the dimension, and the others are added to it entry by entry with
22// `mod_add`. (Wrapping additions would not give the sum modulo `m` unless `m` divided $2^W$.)
23fn mod_sum<T: PrimitiveUnsigned, B: Borrow<UnsignedVector<T>>, I: Iterator<Item = B>>(
24    mut xs: I,
25    m: T,
26) -> UnsignedVector<T> {
27    let first = xs
28        .next()
29        .expect("cannot sum an empty iterator of vectors: the dimension is unknown");
30    let first = first.borrow();
31    assert_reduced(first, m);
32    let mut sum = first.clone();
33    for v in xs {
34        let v = v.borrow();
35        assert_eq!(
36            v.elements.len(),
37            sum.elements.len(),
38            "cannot sum vectors of different dimensions"
39        );
40        assert_reduced(v, m);
41        for (s, &x) in sum.elements.iter_mut().zip(&v.elements) {
42            s.mod_add_assign(x, m);
43        }
44    }
45    sum
46}
47
48impl<T: PrimitiveUnsigned> ModSum<Self, T> for UnsignedVector<T> {
49    /// Adds up all the [`UnsignedVector`]s in an iterator, entry by entry, modulo another number
50    /// $m$. The vectors must all have the same dimension, and their elements must already be
51    /// reduced modulo $m$.
52    ///
53    /// $f((v_i)_ {i=0}^{n-1}, m) = w$, where every element of $w$ is less than $m$ and $\sum_
54    /// {i=0}^{n-1} v_i \equiv w \mod m$, entry by entry.
55    ///
56    /// # Worst-case complexity
57    /// $T(n) = O(n)$
58    ///
59    /// $M(m) = O(m)$
60    ///
61    /// where $T$ is time, $M$ is additional memory, $n$ is the total number of elements of all the
62    /// vectors, and $m$ is the dimension of the vectors.
63    ///
64    /// # Panics
65    /// Panics if the iterator is empty, if the vectors do not all have the same dimension, or if
66    /// any element is greater than or equal to `m`.
67    ///
68    /// # Examples
69    /// ```
70    /// use core::str::FromStr;
71    /// use malachite_base::num::arithmetic::traits::ModSum;
72    /// use malachite_base::unsigned_vector::UnsignedVector;
73    ///
74    /// let vs = ["(5, 1, 3)", "(2, 6, 4)", "(6, 2, 5)"]
75    ///     .map(|s| UnsignedVector::<u8>::from_str(s).unwrap());
76    /// assert_eq!(
77    ///     UnsignedVector::mod_sum(vs.into_iter(), 7).to_string(),
78    ///     "(6, 2, 5)"
79    /// );
80    /// ```
81    #[inline]
82    fn mod_sum<I: Iterator<Item = Self>>(xs: I, m: T) -> Self {
83        mod_sum(xs, m)
84    }
85}
86
87impl<'a, T: PrimitiveUnsigned> ModSum<&'a Self, T> for UnsignedVector<T> {
88    /// Adds up all the [`UnsignedVector`]s in an iterator of references, entry by entry, modulo
89    /// another number $m$. The vectors must all have the same dimension, and their elements must
90    /// already be reduced modulo $m$.
91    ///
92    /// $f((v_i)_ {i=0}^{n-1}, m) = w$, where every element of $w$ is less than $m$ and $\sum_
93    /// {i=0}^{n-1} v_i \equiv w \mod m$, entry by entry.
94    ///
95    /// # Worst-case complexity
96    /// $T(n) = O(n)$
97    ///
98    /// $M(m) = O(m)$
99    ///
100    /// where $T$ is time, $M$ is additional memory, $n$ is the total number of elements of all the
101    /// vectors, and $m$ is the dimension of the vectors.
102    ///
103    /// # Panics
104    /// Panics if the iterator is empty, if the vectors do not all have the same dimension, or if
105    /// any element is greater than or equal to `m`.
106    ///
107    /// # Examples
108    /// ```
109    /// use core::str::FromStr;
110    /// use malachite_base::num::arithmetic::traits::ModSum;
111    /// use malachite_base::unsigned_vector::UnsignedVector;
112    ///
113    /// let vs = ["(5, 1, 3)", "(2, 6, 4)", "(6, 2, 5)"]
114    ///     .map(|s| UnsignedVector::<u8>::from_str(s).unwrap());
115    /// assert_eq!(
116    ///     UnsignedVector::mod_sum(vs.iter(), 7).to_string(),
117    ///     "(6, 2, 5)"
118    /// );
119    /// ```
120    #[inline]
121    fn mod_sum<I: Iterator<Item = &'a Self>>(xs: I, m: T) -> Self {
122        mod_sum(xs, m)
123    }
124}
malachite_base/unsigned_vector/arithmetic/mod_sum.rs

malachite_base/unsigned_vector/arithmetic/
mod_sum.rs
