malachite_base/unsigned_vector/arithmetic/
mod_mul.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, ModMul, ModMulAssign};
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11use crate::unsigned_vector::UnsignedVector;
12use alloc::vec::Vec;
13
14fn assert_reduced<T: PrimitiveUnsigned>(v: &UnsignedVector<T>, c: T, m: T) {
15    assert!(
16        v.mod_is_reduced(&m),
17        "self must be reduced mod m, but {v} has an element >= {m}"
18    );
19    assert!(
20        c.mod_is_reduced(&m),
21        "c must be reduced mod m, but {c} >= {m}"
22    );
23}
24
25// Multiplies every element by `c` modulo `m`, which the elements and `c` are already reduced
26// modulo. The data for multiplying modulo `m` is computed once and shared by all the elements.
27pub(crate) fn mod_mul_assign_unchecked<T: PrimitiveUnsigned>(xs: &mut [T], c: T, m: T) {
28    let data = T::precompute_mod_mul_data(&m);
29    for x in xs {
30        x.mod_mul_precomputed_assign(c, m, &data);
31    }
32}
33
34// The elements multiplied by `c` modulo `m`, as `mod_mul_assign_unchecked` computes them.
35pub(crate) fn mod_mul_unchecked<T: PrimitiveUnsigned>(xs: &[T], c: T, m: T) -> Vec<T> {
36    let data = T::precompute_mod_mul_data(&m);
37    xs.iter()
38        .map(|&x| x.mod_mul_precomputed(c, m, &data))
39        .collect()
40}
41
42impl<T: PrimitiveUnsigned> ModMul<T, T> for UnsignedVector<T> {
43    type Output = Self;
44
45    /// Multiplies every element of an [`UnsignedVector`] by a scalar modulo $m$, taking the vector
46    /// by value. The elements and the scalar must already be reduced modulo $m$.
47    ///
48    /// Each product is reduced modulo $m$, and the result has the same dimension as the vector. The
49    /// data for multiplying modulo $m$ is precomputed once and shared by all the elements.
50    ///
51    /// $$
52    /// f(v, c, m) = cv \bmod m.
53    /// $$
54    ///
55    /// # Worst-case complexity
56    /// $T(n) = O(n)$
57    ///
58    /// $M(n) = O(1)$
59    ///
60    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
61    ///
62    /// # Panics
63    /// Panics if `m` is zero, or if any element of `self`, or `c`, is greater than or equal to `m`.
64    ///
65    /// # Examples
66    /// ```
67    /// use core::str::FromStr;
68    /// use malachite_base::num::arithmetic::traits::ModMul;
69    /// use malachite_base::unsigned_vector::UnsignedVector;
70    ///
71    /// let v = UnsignedVector::<u8>::from_str("(5, 1, 3)").unwrap();
72    /// assert_eq!(v.mod_mul(3, 7).to_string(), "(1, 3, 2)");
73    /// ```
74    #[inline]
75    fn mod_mul(mut self, c: T, m: T) -> Self {
76        self.mod_mul_assign(c, m);
77        self
78    }
79}
80
81impl<T: PrimitiveUnsigned> ModMul<T, T> for &UnsignedVector<T> {
82    type Output = UnsignedVector<T>;
83
84    /// Multiplies every element of an [`UnsignedVector`] by a scalar modulo $m$, taking the vector
85    /// by reference. The elements and the scalar must already be reduced modulo $m$.
86    ///
87    /// See the documentation for the [`ModMul`] implementation that takes the vector by value for
88    /// details.
89    ///
90    /// # Worst-case complexity
91    /// $T(n) = O(n)$
92    ///
93    /// $M(n) = O(n)$
94    ///
95    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
96    ///
97    /// # Panics
98    /// Panics if `m` is zero, or if any element of `self`, or `c`, is greater than or equal to `m`.
99    ///
100    /// # Examples
101    /// ```
102    /// use core::str::FromStr;
103    /// use malachite_base::num::arithmetic::traits::ModMul;
104    /// use malachite_base::unsigned_vector::UnsignedVector;
105    ///
106    /// let v = UnsignedVector::<u8>::from_str("(5, 1, 3)").unwrap();
107    /// assert_eq!((&v).mod_mul(3, 7).to_string(), "(1, 3, 2)");
108    /// ```
109    fn mod_mul(self, c: T, m: T) -> UnsignedVector<T> {
110        assert_reduced(self, c, m);
111        UnsignedVector {
112            elements: mod_mul_unchecked(&self.elements, c, m),
113        }
114    }
115}
116
117impl<T: PrimitiveUnsigned> ModMulAssign<T, T> for UnsignedVector<T> {
118    /// Multiplies every element of an [`UnsignedVector`] by a scalar modulo $m$, in place. The
119    /// elements and the scalar must already be reduced modulo $m$.
120    ///
121    /// See the documentation for the [`ModMul`] implementation that takes the vector by value for
122    /// details.
123    ///
124    /// # Worst-case complexity
125    /// $T(n) = O(n)$
126    ///
127    /// $M(n) = O(1)$
128    ///
129    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
130    ///
131    /// # Panics
132    /// Panics if `m` is zero, or if any element of `self`, or `c`, is greater than or equal to `m`.
133    ///
134    /// # Examples
135    /// ```
136    /// use core::str::FromStr;
137    /// use malachite_base::num::arithmetic::traits::ModMulAssign;
138    /// use malachite_base::unsigned_vector::UnsignedVector;
139    ///
140    /// let mut v = UnsignedVector::<u8>::from_str("(5, 1, 3)").unwrap();
141    /// v.mod_mul_assign(3, 7);
142    /// assert_eq!(v.to_string(), "(1, 3, 2)");
143    /// ```
144    fn mod_mul_assign(&mut self, c: T, m: T) {
145        assert_reduced(self, c, m);
146        mod_mul_assign_unchecked(&mut self.elements, c, m);
147    }
148}
malachite_base/unsigned_vector/arithmetic/mod_mul.rs

malachite_base/unsigned_vector/arithmetic/
mod_mul.rs
