Skip to main content

mathverse_complex/
polynomial.rs

1//! Polynomial evaluation and root finding.
2
3use crate::Complex;
4use mathverse_core::traits::RealFull;
5
6/// Evaluate a polynomial at `z` via Horner's scheme.
7///
8/// `coeffs[0] + coeffs[1]·z + coeffs[2]·z² + …`
9pub fn eval_polynomial<T: RealFull>(coeffs: &[Complex<T>], z: Complex<T>) -> Complex<T> {
10    coeffs
11        .iter()
12        .rev()
13        .fold(Complex::<T>::zero(), |acc, &c| acc * z + c)
14}
15
16/// Find all roots of a polynomial using the Durand–Kerner (Weierstrass)
17/// method. `coeffs` are ordered `coeffs[0] + coeffs[1]·z + …`, and the
18/// leading coefficient must be non-zero.
19///
20/// Iterates until every root update is below `tol` or `max_iterations` is
21/// reached (returns the best estimate either way).
22///
23/// ```
24/// use mathverse_complex::{polynomial::polynomial_roots, Complex};
25/// // z² + 1 = 0  →  ±i
26/// let roots = polynomial_roots(&[Complex::one(), Complex::zero(), Complex::one()], 1000, 1e-12);
27/// let to_i = |r: &Complex| (*r - Complex::i()).norm();
28/// let to_neg_i = |r: &Complex| (*r + Complex::i()).norm();
29/// assert!(roots.iter().map(to_i).fold(f64::MAX, f64::min) < 1e-8);
30/// assert!(roots.iter().map(to_neg_i).fold(f64::MAX, f64::min) < 1e-8);
31/// ```
32pub fn polynomial_roots<T: RealFull>(
33    coeffs: &[Complex<T>],
34    max_iterations: usize,
35    tol: T,
36) -> Vec<Complex<T>> {
37    let n = coeffs.len().saturating_sub(1);
38    if n == 0 {
39        return Vec::new();
40    }
41    let tol_f = tol.to_f64();
42    let two_pi = T::from_f64(core::f64::consts::TAU);
43    let n_t = T::from_f64(n as f64);
44    // Distinct starting points spread around a small circle (0.4·e^(2πik/n)).
45    let mut roots: Vec<Complex<T>> = (0..n)
46        .map(|i| Complex::<T>::polar(T::from_f64(0.4), two_pi * T::from_f64(i as f64) / n_t))
47        .collect();
48
49    for _ in 0..max_iterations {
50        let prev = roots.clone();
51        let mut converged = true;
52        for i in 0..n {
53            let mut denom = Complex::<T>::one();
54            for (j, rj) in prev.iter().enumerate() {
55                if j != i {
56                    denom = denom * (prev[i] - *rj);
57                }
58            }
59            roots[i] = prev[i] - eval_polynomial(coeffs, prev[i]) / denom;
60            if (roots[i] - prev[i]).norm().to_f64() > tol_f {
61                converged = false;
62            }
63        }
64        if converged {
65            break;
66        }
67    }
68    roots
69}
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74
75    #[test]
76    fn eval_horner() {
77        // 1 + 2z + 3z² at z = 2 → 1 + 4 + 12 = 17
78        let coeffs = [Complex::one(), Complex::real(2.0), Complex::real(3.0)];
79        assert_eq!(
80            eval_polynomial(&coeffs, Complex::real(2.0)),
81            Complex::real(17.0)
82        );
83        assert_eq!(eval_polynomial(&coeffs, Complex::zero()), Complex::one());
84    }
85
86    #[test]
87    fn roots_quadratic() {
88        // z² - 1 → ±1
89        let roots = polynomial_roots(
90            &[Complex::real(-1.0), Complex::zero(), Complex::one()],
91            1000,
92            1e-12,
93        );
94        let to_one = |r: &Complex| (*r - Complex::one()).norm();
95        let to_neg_one = |r: &Complex| (*r + Complex::one()).norm();
96        assert!(roots.iter().map(to_one).fold(f64::MAX, f64::min) < 1e-8);
97        assert!(roots.iter().map(to_neg_one).fold(f64::MAX, f64::min) < 1e-8);
98    }
99
100    #[test]
101    fn roots_imaginary_unit() {
102        // z² + 1 → ±i
103        let roots = polynomial_roots(
104            &[Complex::one(), Complex::zero(), Complex::one()],
105            1000,
106            1e-12,
107        );
108        let to_i = |r: &Complex| (*r - Complex::i()).norm();
109        let to_neg_i = |r: &Complex| (*r + Complex::i()).norm();
110        assert!(roots.iter().map(to_i).fold(f64::MAX, f64::min) < 1e-8);
111        assert!(roots.iter().map(to_neg_i).fold(f64::MAX, f64::min) < 1e-8);
112    }
113
114    #[test]
115    fn roots_cubic() {
116        // (z-1)(z-2)(z+1) = z³ - 2z² - z + 2
117        let coeffs = [
118            Complex::real(2.0),
119            Complex::real(-1.0),
120            Complex::real(-2.0),
121            Complex::one(),
122        ];
123        let roots = polynomial_roots(&coeffs, 2000, 1e-12);
124        let expected = [1.0, 2.0, -1.0];
125        for e in expected {
126            let d = roots
127                .iter()
128                .map(|r| (*r - Complex::real(e)).norm())
129                .fold(f64::MAX, f64::min);
130            assert!(d < 1e-6, "root {e} not found, got {roots:?}");
131        }
132    }
133}