use crate::anm::Branch;
use crate::gcr::recip;
use crate::prec::nan_max;
use multidouble::dd::DD;
use multidouble::precision::Precision;
use multidouble::simd::Native;
pub struct Cx<P: Precision<Native>> {
pub re: P::Scalar,
pub im: P::Scalar,
}
impl<P: Precision<Native>> Clone for Cx<P> {
fn clone(&self) -> Self {
*self
}
}
impl<P: Precision<Native>> Copy for Cx<P> {}
impl<P: Precision<Native>> Cx<P> {
pub fn new(re: P::Scalar, im: P::Scalar) -> Self {
Cx { re, im }
}
pub fn from_f64(re: f64, im: f64) -> Self {
Cx::new(P::from_dd(DD::from_f64(re)), P::from_dd(DD::from_f64(im)))
}
pub fn real(re: P::Scalar) -> Self {
Cx::new(re, P::ZERO)
}
pub fn scale(self, s: P::Scalar) -> Self {
Cx::new(self.re * s, self.im * s)
}
pub fn inv(self) -> Self {
let m = P::to_dd(self.re).hi.abs().max(P::to_dd(self.im).hi.abs());
let sc = if m > 0.0 && m.is_finite() {
P::from_dd(DD::from_f64(2f64.powi(-(m.log2().floor() as i32).clamp(-1000, 1000))))
} else {
P::ONE
};
let (re, im) = (self.re * sc, self.im * sc);
let d = recip::<P>(re * re + im * im) * sc;
Cx::new(re * d, -(im * d))
}
pub fn to_f64(self) -> (f64, f64) {
(P::to_dd(self.re).hi, P::to_dd(self.im).hi)
}
pub fn abs(self) -> f64 {
let (re, im) = self.to_f64();
re.hypot(im)
}
}
impl<P: Precision<Native>> std::ops::Add for Cx<P> {
type Output = Self;
fn add(self, b: Self) -> Self {
Cx::new(self.re + b.re, self.im + b.im)
}
}
impl<P: Precision<Native>> std::ops::Sub for Cx<P> {
type Output = Self;
fn sub(self, b: Self) -> Self {
Cx::new(self.re - b.re, self.im - b.im)
}
}
impl<P: Precision<Native>> std::ops::Mul for Cx<P> {
type Output = Self;
fn mul(self, b: Self) -> Self {
Cx::new(self.re * b.re - self.im * b.im, self.re * b.im + self.im * b.re)
}
}
impl<P: Precision<Native>> std::ops::Div for Cx<P> {
type Output = Self;
#[allow(clippy::suspicious_arithmetic_impl)]
fn div(self, b: Self) -> Self {
self * b.inv()
}
}
fn horner<P: Precision<Native>>(a: &[P::Scalar], x: Cx<P>) -> (Cx<P>, Cx<P>) {
let mut p = Cx::real(a[a.len() - 1]);
let mut dp = Cx::real(P::ZERO);
for &c in a[..a.len() - 1].iter().rev() {
dp = dp * x + p;
p = p * x + Cx::real(c);
}
(p, dp)
}
fn unit<P: Precision<Native>>() -> f64 {
0.5f64.powi(52 * P::PARTS as i32)
}
pub fn roots<P: Precision<Native>>(a: &[P::Scalar]) -> Vec<Cx<P>> {
let mut a = a.to_vec();
while a.len() > 1 && P::to_dd(a[a.len() - 1]).hi == 0.0 {
a.pop();
}
let n = a.len() - 1;
if n == 0 {
return Vec::new();
}
let lead = P::to_dd(a[n]).hi.abs();
let bound = (0..n)
.map(|k| {
let r = P::to_dd(a[k]).hi.abs() / lead / if k == 0 { 2.0 } else { 1.0 };
r.powf(1.0 / (n - k) as f64)
})
.fold(0.0, nan_max);
let r = if bound > 0.0 && bound.is_finite() { bound } else { 1.0 };
let mut z: Vec<Cx<P>> = (0..n)
.map(|k| {
let t = 2.0 * std::f64::consts::PI * k as f64 / n as f64 + 0.4;
Cx::from_f64(r * t.cos(), r * t.sin())
})
.collect();
let tol = 16.0 * unit::<P>();
for _ in 0..500 {
let mut worst = 0.0f64;
for k in 0..n {
let (p, dp) = horner::<P>(&a, z[k]);
if p.abs() == 0.0 {
continue;
}
let ratio = p / dp;
let mut sum = Cx::real(P::ZERO);
for (j, &zj) in z.iter().enumerate() {
if j != k {
sum = sum + (z[k] - zj).inv();
}
}
let w = ratio / (Cx::real(P::ONE) - ratio * sum);
if !w.abs().is_finite() {
continue;
}
z[k] = z[k] - w;
worst = worst.max(w.abs() / z[k].abs().max(f64::MIN_POSITIVE));
}
if worst <= tol {
break;
}
}
z
}
#[allow(clippy::type_complexity)]
pub fn pade<P: Precision<Native>>(g: &[P::Scalar], m: usize) -> Option<(Vec<P::Scalar>, Vec<P::Scalar>)> {
if g.is_empty() || m > g.len() - 1 {
return None;
}
let l = g.len() - 1 - m;
let at = |i: isize| if i >= 0 { g[i as usize] } else { P::ZERO };
let mut a: Vec<Vec<P::Scalar>> = (1..=m)
.map(|i| (1..=m).map(|j| at(l as isize + i as isize - j as isize)).collect())
.collect();
let mut b: Vec<P::Scalar> = (1..=m).map(|i| -at((l + i) as isize)).collect();
for c in 0..m {
let piv = (c..m).max_by(|&x, &y| P::to_dd(a[x][c]).hi.abs().total_cmp(&P::to_dd(a[y][c]).hi.abs()))?;
let pv = P::to_dd(a[piv][c]).hi;
if pv == 0.0 || !pv.is_finite() {
return None;
}
a.swap(c, piv);
b.swap(c, piv);
let inv = recip::<P>(a[c][c]);
for r in c + 1..m {
let f = a[r][c] * inv;
let (top, bot) = a.split_at_mut(r);
for (x, &y) in bot[0][c..].iter_mut().zip(&top[c][c..]) {
*x = *x - f * y;
}
b[r] = b[r] - f * b[c];
}
}
let mut q = vec![P::ZERO; m + 1];
q[0] = P::ONE;
for c in (0..m).rev() {
let s = (c + 1..m).fold(b[c], |s, j| s - a[c][j] * q[j + 1]);
q[c + 1] = s * recip::<P>(a[c][c]);
}
let p = (0..=l)
.map(|i| (0..=i.min(m)).fold(P::ZERO, |t, j| t + q[j] * g[i - j]))
.collect();
Some((p, q))
}
#[derive(Clone, Debug)]
pub struct PoleOpts {
pub ms: Vec<usize>,
pub doublet: Option<f64>,
pub cluster: f64,
pub min_count: usize,
pub inside: f64,
pub r_max: f64,
}
impl Default for PoleOpts {
fn default() -> Self {
PoleOpts {
ms: (2..=10).collect(),
doublet: None,
cluster: 0.05,
min_count: 3,
inside: 0.85,
r_max: 8.0,
}
}
}
#[derive(Clone, Debug)]
pub struct Pole {
pub s: (f64, f64),
pub abs: f64,
pub arg: f64,
pub ms: Vec<usize>,
pub spread: f64,
}
struct Cluster {
seed: (f64, f64),
ms: Vec<usize>,
pts: Vec<(f64, f64)>,
}
fn median(mut v: Vec<f64>) -> f64 {
v.sort_by(f64::total_cmp);
let n = v.len();
if n % 2 == 1 {
v[n / 2]
} else {
(v[n / 2 - 1] + v[n / 2]) / 2.0
}
}
pub fn stable_poles<P: Precision<Native>>(c: &[P::Scalar], opts: &PoleOpts) -> Vec<Pole> {
let c64: Vec<f64> = c.iter().map(|&v| P::to_dd(v).hi).collect();
let r_min = opts.inside * root_radius(&c64, None);
let doublet = opts.doublet.unwrap_or(0.5f64.powi(26 * P::PARTS as i32));
let mut cand: Vec<(usize, (f64, f64))> = Vec::new();
for &m in &opts.ms {
let Some((p, q)) = pade::<P>(c, m) else {
continue;
};
let zeros = roots::<P>(&p);
for s in roots::<P>(&q) {
let (re, im) = s.to_f64();
let a = re.hypot(im);
if !a.is_finite() || im < -1e-12 * a || a > opts.r_max || a < r_min {
continue;
}
if zeros.iter().any(|&z| (s - z).abs() <= doublet * a) {
continue;
}
cand.push((m, (re, im.abs())));
}
}
cand.sort_by(|x, y| x.1 .0.hypot(x.1 .1).total_cmp(&y.1 .0.hypot(y.1 .1)));
let mut clusters: Vec<Cluster> = Vec::new();
for (m, s) in cand {
let near = clusters.iter_mut().find(|cl| {
(s.0 - cl.seed.0).hypot(s.1 - cl.seed.1) <= opts.cluster * cl.seed.0.hypot(cl.seed.1) && !cl.ms.contains(&m)
});
match near {
Some(cl) => {
cl.ms.push(m);
cl.pts.push(s);
}
None => clusters.push(Cluster {
seed: s,
ms: vec![m],
pts: vec![s],
}),
}
}
let mut out: Vec<Pole> = clusters
.into_iter()
.filter(|cl| cl.ms.len() >= opts.min_count)
.map(|Cluster { mut ms, pts, .. }| {
let s = (
median(pts.iter().map(|p| p.0).collect()),
median(pts.iter().map(|p| p.1).collect()),
);
let abs = s.0.hypot(s.1);
let spread = pts.iter().map(|p| (p.0 - s.0).hypot(p.1 - s.1)).fold(0.0, nan_max) / abs;
ms.sort_unstable();
Pole {
s,
abs,
arg: s.1.atan2(s.0),
ms,
spread,
}
})
.collect();
out.sort_by(|x, y| x.abs.total_cmp(&y.abs));
out
}
pub fn root_radius(c: &[f64], from: Option<usize>) -> f64 {
let n = c.len();
let k0 = from.unwrap_or(n / 2).max(1);
let pts: Vec<(f64, f64)> = (1..=n)
.filter(|&k| k >= k0)
.filter_map(|k| {
let env = c[k.saturating_sub(2)..(k + 1).min(n)]
.iter()
.map(|v| v.abs())
.fold(0.0, nan_max);
(env > 0.0).then(|| (k as f64, env.ln()))
})
.collect();
match line(&pts) {
Some((_, slope)) => (-slope).exp(),
None => f64::NAN,
}
}
fn line(pts: &[(f64, f64)]) -> Option<(f64, f64)> {
let n = pts.len() as f64;
if pts.len() < 2 {
return None;
}
let mx = pts.iter().map(|p| p.0).sum::<f64>() / n;
let my = pts.iter().map(|p| p.1).sum::<f64>() / n;
let sxx: f64 = pts.iter().map(|p| (p.0 - mx) * (p.0 - mx)).sum();
let sxy: f64 = pts.iter().map(|p| (p.0 - mx) * (p.1 - my)).sum();
if sxx == 0.0 {
return None;
}
let b = sxy / sxx;
Some((my - b * mx, b))
}
pub fn domb_sykes(c: &[f64]) -> Option<(f64, f64)> {
let r: Vec<(f64, f64)> = (2..=c.len())
.filter(|&k| c[k - 2] != 0.0)
.map(|k| (1.0 / k as f64, c[k - 1] / c[k - 2]))
.collect();
let tail = &r[r.len() / 2..];
if tail.len() < 3 {
return None;
}
let (ic, slope) = line(tail)?;
if ic == 0.0 {
return None;
}
Some((1.0 / ic, 1.0 + slope / ic))
}
#[derive(Clone, Debug)]
pub struct Recurrence {
pub windows: Vec<(usize, (f64, f64))>,
pub s: Option<(f64, f64)>,
pub spread: f64,
}
pub fn recurrence(c: &[f64], from: usize, w: usize) -> Recurrence {
let n = c.len();
let mut windows = Vec::new();
for k0 in 3..(n + 2).saturating_sub(w) {
let ks = k0..k0 + w;
let sc = ks
.clone()
.flat_map(|k| [c[k - 2].abs(), c[k - 3].abs()])
.fold(0.0, nan_max);
if sc == 0.0 || !sc.is_finite() {
continue;
}
let a1: Vec<f64> = ks.clone().map(|k| c[k - 2] / sc).collect();
let a2: Vec<f64> = ks.clone().map(|k| c[k - 3] / sc).collect();
let b: Vec<f64> = ks.map(|k| c[k - 1] / sc).collect();
let dot = |x: &[f64], y: &[f64]| x.iter().zip(y).map(|(a, b)| a * b).sum::<f64>();
let r11 = dot(&a1, &a1).sqrt();
if r11 == 0.0 {
continue;
}
let q1: Vec<f64> = a1.iter().map(|v| v / r11).collect();
let r12 = dot(&q1, &a2);
let v2: Vec<f64> = a2.iter().zip(&q1).map(|(a, q)| a - r12 * q).collect();
let r22 = dot(&v2, &v2).sqrt();
if r22 == 0.0 {
continue;
}
let q2: Vec<f64> = v2.iter().map(|v| v / r22).collect();
let (y1, y2) = (dot(&q1, &b), dot(&q2, &b));
let q = y2 / r22;
let p = (y1 - r12 * q) / r11;
let disc = p * p + 4.0 * q;
let x = if disc >= 0.0 {
let r = disc.sqrt();
let (x1, x2) = ((p + r) / 2.0, (p - r) / 2.0);
if x1.abs() >= x2.abs() {
(x1, 0.0)
} else {
(x2, 0.0)
}
} else {
(p / 2.0, (-disc).sqrt() / 2.0)
};
let m2 = x.0 * x.0 + x.1 * x.1;
if m2 == 0.0 {
continue;
}
windows.push((k0, (x.0 / m2, (x.1 / m2).abs())));
}
let sel: Vec<(f64, f64)> = windows.iter().filter(|(k0, _)| *k0 >= from).map(|w| w.1).collect();
if sel.is_empty() {
return Recurrence {
windows,
s: None,
spread: f64::NAN,
};
}
let s = (
median(sel.iter().map(|v| v.0).collect()),
median(sel.iter().map(|v| v.1).collect()),
);
let spread = sel.iter().map(|v| (v.0 - s.0).hypot(v.1 - s.1)).fold(0.0, nan_max) / s.0.hypot(s.1);
Recurrence {
windows,
s: Some(s),
spread,
}
}
pub fn component<P: Precision<Native>>(br: &Branch<P>, i: usize) -> Vec<P::Scalar> {
br.z[1..].iter().map(|zk| zk[i]).collect()
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{Double, Quad};
fn root_err<P: Precision<Native>>(got: &[Cx<P>], want: &[(f64, f64)]) -> f64 {
want.iter()
.map(|&w| {
got.iter()
.map(|&g| (g - Cx::from_f64(w.0, w.1)).abs())
.fold(f64::INFINITY, f64::min)
})
.fold(0.0, nan_max)
}
fn moved<P: Precision<Native>>(r: &[Cx<P>], eps: f64) -> Vec<Cx<P>> {
let mut r = r.to_vec();
r[0] = r[0] + Cx::from_f64(eps, 0.0);
r
}
#[test]
fn roots_of_a_known_polynomial() {
let a = [6.0, -7.0, 6.0, -6.0, 0.0, 1.0];
let want = [(1.0, 0.0), (2.0, 0.0), (-3.0, 0.0), (0.0, 1.0), (0.0, -1.0)];
let d: Vec<DD> = a.iter().map(|&v| DD::from_f64(v)).collect();
let rd = roots::<Double>(&d);
let e = root_err::<Double>(&rd, &want);
let q: Vec<_> = a
.iter()
.map(|&v| <Quad as Precision<Native>>::from_dd(DD::from_f64(v)))
.collect();
let rq = roots::<Quad>(&q);
let eq = root_err::<Quad>(&rq, &want);
assert!(e <= 1e-25 && eq <= 1e-55, "{e:e} {eq:e}");
assert!(
root_err::<Double>(&moved(&rd, 1e-20), &want) > 1e-25,
"double-double control did not fire"
);
assert!(
root_err::<Quad>(&moved(&rq, 1e-50), &want) > 1e-55,
"quad-double control did not fire"
);
let mut bad = d.clone();
bad[2] = DD::from_f64(6.0 + 1e-6);
assert!(
root_err::<Double>(&roots::<Double>(&bad), &want) > 1e-9,
"control did not fire"
);
}
#[test]
fn pade_of_a_rational_function() {
let pole = |s: f64| {
let g = [
DD::from_f64(4.0),
DD::ONE / DD::from_f64(s),
DD::ONE / DD::from_f64(s * s),
];
let (_, q) = pade::<Double>(&g, 1).unwrap();
roots::<Double>(&q)
};
let p = pole(2.0);
assert!(root_err::<Double>(&p, &[(2.0, 0.0)]) <= 1e-28, "{:?}", p[0].to_f64());
assert!(
root_err::<Double>(&moved(&p, 1e-20), &[(2.0, 0.0)]) > 1e-28,
"control did not fire"
);
assert!(
root_err::<Double>(&pole(2.1), &[(2.0, 0.0)]) > 0.05,
"control did not fire"
);
}
}