1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
// Copyright © 2026 Mikhail Hogrefe
//
// This file is part of Malachite.
//
// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
use crate::natural::Natural;
use crate::natural_polynomial::NaturalPolynomial;
use crate::platform::Limb;
use crate::test_util::natural_polynomial::arithmetic::mul::{
mul_naive, natural_generated_coefficients,
};
use alloc::vec::Vec;
use malachite_base::num::arithmetic::traits::Mod;
use malachite_base::num::basic::integers::PrimitiveInt;
use malachite_base::num::logic::traits::SignificantBits;
use malachite_base::polynomial::Polynomial;
// Multiplies by schoolbook multiplication and then reduces the product's coefficients modulo `m`.
pub fn mod_mul_naive(
p: &NaturalPolynomial,
q: &NaturalPolynomial,
m: &Natural,
) -> NaturalPolynomial {
NaturalPolynomial::from_coefficients_asc(
mul_naive(p, q)
.coefficients_asc()
.iter()
.map(|x| x.mod_op(m))
.collect(),
)
}
// `len` coefficients reduced modulo `m`, for exercising the multiplication algorithms at chosen
// lengths and moduli: $2^{k + \text{W}} - (i + 1)$ reduced, where $k$ is the number of bits of $m$,
// so that they are all different and most are large.
pub fn natural_mod_generated_coefficients(len: usize, m: &Natural) -> Vec<Natural> {
natural_generated_coefficients(len, m.significant_bits() + Limb::WIDTH)
.into_iter()
.map(|x| x.mod_op(m))
.collect()
}
// Moduli for exercising the multiplication algorithms: small ones, ones near the size of a limb,
// and ones too large for a limb.
pub fn natural_test_moduli() -> Vec<Natural> {
[1u32, 2, 3, 7, 1000]
.into_iter()
.map(Natural::from)
.chain([
Natural::from(Limb::MAX >> 1),
Natural::from((Limb::MAX >> 1) + 2),
Natural::from(Limb::MAX - 1),
Natural::from(Limb::MAX),
])
.collect()
}