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
// 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 alloc::vec::Vec;
use malachite_base::num::arithmetic::traits::{ModPowerOf2, Pow};
use malachite_base::num::basic::traits::Zero;
use malachite_base::num::conversion::traits::ExactFrom;
// Evaluates a polynomial term by term, as the sum of $c_i x^i$, with each power of $x$ computed
// from scratch. This shares nothing with Horner's rule or the divide-and-conquer scheme, so it can
// check both.
pub fn evaluate_naive(p: &NaturalPolynomial, x: &Natural) -> Natural {
let mut sum = Natural::ZERO;
for (i, c) in p.coefficients_asc().iter().enumerate() {
sum += c * x.pow(u64::exact_from(i));
}
sum
}
// Evaluates a polynomial at x in full and then reduces the value modulo 2^pow. The modular
// evaluation never forms the full value, so this checks it independently.
pub fn mod_power_of_2_evaluate_naive(p: &NaturalPolynomial, x: &Natural, pow: u64) -> Natural {
evaluate_naive(p, x).mod_power_of_2(pow)
}
// Evaluates a polynomial at x in full and then reduces the value modulo m.
pub fn mod_evaluate_naive(p: &NaturalPolynomial, x: &Natural, m: &Natural) -> Natural {
evaluate_naive(p, x) % m
}
// Evaluates a polynomial at each of `xs` with `evaluate_naive`.
pub fn evaluate_many_naive(p: &NaturalPolynomial, xs: &[Natural]) -> Vec<Natural> {
xs.iter().map(|x| evaluate_naive(p, x)).collect()
}
// Evaluates a polynomial at each of `xs` modulo `m` with `mod_evaluate_naive`.
pub fn mod_evaluate_many_naive(p: &NaturalPolynomial, xs: &[Natural], m: &Natural) -> Vec<Natural> {
xs.iter().map(|x| mod_evaluate_naive(p, x, m)).collect()
}