malachite_base/num/arithmetic/
mod_product.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::ModProduct;
16use crate::num::basic::unsigneds::PrimitiveUnsigned;
17
18// The data for multiplying modulo `m` is computed once and reused for every factor. Once the
19// partial product is zero it stays zero, so the factors after the one that made it zero are not
20// examined. Starting from 1 reduced modulo `m` makes the product of no numbers correct even when
21// `m` is 1.
22fn mod_product<T: PrimitiveUnsigned, I: Iterator<Item = T>>(xs: I, m: T) -> T {
23    assert_ne!(m, T::ZERO, "m cannot be zero");
24    let data = T::precompute_mod_mul_data(&m);
25    let mut product = if m == T::ONE { T::ZERO } else { T::ONE };
26    for x in xs {
27        assert!(x < m, "x must be reduced mod m, but {x} >= {m}");
28        product.mod_mul_precomputed_assign(x, m, &data);
29        if product == T::ZERO {
30            break;
31        }
32    }
33    product
34}
35
36macro_rules! impl_mod_product {
37    ($t:ident) => {
38        impl ModProduct for $t {
39            /// Multiplies together all the numbers in an iterator, modulo another number $m$. Every
40            /// number must be already reduced modulo $m$.
41            ///
42            /// The product of no numbers is 1 reduced modulo $m$, which is 0 when $m = 1$.
43            ///
44            /// $f((x_i)_ {i=0}^{n-1}, m) = y$, where $y < m$ and $\prod_ {i=0}^{n-1} x_i \equiv y
45            /// \mod m$.
46            ///
47            /// # Worst-case complexity
48            /// $T(n) = O(n)$
49            ///
50            /// $M(n) = O(1)$
51            ///
52            /// where $T$ is time, $M$ is additional memory, and $n$ is `xs.count()`.
53            ///
54            /// # Panics
55            /// Panics if `m` is zero or if any number is greater than or equal to `m`. As soon as
56            /// the partial product is zero, the remaining numbers are not examined, so an unreduced
57            /// number after that point is not detected.
58            ///
59            /// # Examples
60            /// See [here](super::mod_product#mod_product).
61            #[inline]
62            fn mod_product<I: Iterator<Item = $t>>(xs: I, m: $t) -> $t {
63                mod_product(xs, m)
64            }
65        }
66
67        impl<'a> ModProduct<&'a $t, $t> for $t {
68            /// Multiplies together all the numbers in an iterator of references, modulo another
69            /// number $m$. Every number must be already reduced modulo $m$.
70            ///
71            /// The product of no numbers is 1 reduced modulo $m$, which is 0 when $m = 1$.
72            ///
73            /// $f((x_i)_ {i=0}^{n-1}, m) = y$, where $y < m$ and $\prod_ {i=0}^{n-1} x_i \equiv y
74            /// \mod m$.
75            ///
76            /// # Worst-case complexity
77            /// $T(n) = O(n)$
78            ///
79            /// $M(n) = O(1)$
80            ///
81            /// where $T$ is time, $M$ is additional memory, and $n$ is `xs.count()`.
82            ///
83            /// # Panics
84            /// Panics if `m` is zero or if any number is greater than or equal to `m`. As soon as
85            /// the partial product is zero, the remaining numbers are not examined, so an unreduced
86            /// number after that point is not detected.
87            ///
88            /// # Examples
89            /// See [here](super::mod_product#mod_product).
90            #[inline]
91            fn mod_product<I: Iterator<Item = &'a $t>>(xs: I, m: $t) -> $t {
92                mod_product(xs.copied(), m)
93            }
94        }
95    };
96}
97apply_to_unsigneds!(impl_mod_product);
malachite_base/num/arithmetic/mod_product.rs

malachite_base/num/arithmetic/
mod_product.rs
