mathverse_complex/
polynomial.rs1use crate::Complex;
4use mathverse_core::traits::RealFull;
5
6pub 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
16pub 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 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 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 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 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 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}