Skip to main content

xsf/scipy_special/
orthogonal_roots.rs

1//! Translated from `scipy/special/_orthogonal.py` (scipy/scipy@7d279ba)
2//!
3//! - <https://github.com/scipy/scipy/blob/7d279ba/scipy/special/_orthogonal.py>
4//!
5//! The nodes are in ascending order, and the weights sum to the integral of the weight function.
6
7use core::f64::consts::{LN_2, PI, SQRT_2};
8
9use super::orthogonal_eval::{
10    eval_gegenbauer, eval_genlaguerre, eval_hermite_h, eval_hermite_he, eval_jacobi, eval_legendre,
11};
12use crate::ext::ln_gamma;
13use crate::ext::tridiag::eigvals;
14use crate::utils::{SQRT_PI, SQRT_TAU_DOWN};
15use crate::xsf::cephes::consts::MAXLOG;
16use crate::xsf::cephes::dd_real::{DoubleDouble as Dd, LOG2, ldexp_f64, two_sum};
17use crate::xsf::cephes::incbet_lnpow;
18use Nodes::{Plain, Shifted, Symmetric};
19
20/// Corresponds to `_gen_roots_and_weights`: Gauss quadrature by the Golub-Welsch algorithm
21///
22/// The monic orthogonal polynomials satisfy `p_{k+1}(x) = (x - a_k) p_k(x) - b_k^2 p_{k-1}(x)`,
23/// so the roots of `f(n, x)` are the eigenvalues of the tridiagonal matrix with diagonal `a_k` and
24/// off-diagonal `b_k`. They are refined by a Newton step with the derivative `df(n, x)`.
25///
26/// The weights sum to `mu0`, and are proportional to `1 / (sigma(x) df(n, x)^2)` at the roots,
27/// where `sigma f'' + tau f' + lambda f = 0` (DLMF Table 18.8.1). For a root `x + dx` with the
28/// rounding error `dx`, `sigma(x, dx)` is `sigma(x + dx)`, and `df(n, x + dx)` is
29/// `df(n, x) (1 - tau(x) dx / sigma)` to first order, since `f(n, x + dx) = 0`.
30fn gen_roots_and_weights(
31    n: usize,
32    mu0: f64,
33    an: impl Fn(f64) -> f64,
34    bn: impl Fn(f64) -> f64,
35    f: impl Fn(i32, f64) -> f64,
36    df: impl Fn(i32, f64) -> f64,
37    sigma: impl Fn(f64, f64) -> f64,
38    tau: impl Fn(f64) -> f64,
39    nodes: Nodes,
40) -> (Vec<f64>, Vec<f64>) {
41    let d: Vec<f64> = (0..n).map(|k| an(k as f64)).collect();
42    let e: Vec<f64> = (1..n).map(|k| bn(k as f64)).collect();
43    let mut x = eigvals(&d, &e);
44
45    // improve roots by Newton's method
46    //
47    // Unlike in SciPy, which takes one step, at most 4 steps are taken while
48    // `step^2 > eps sigma^2`, i.e. while the error of a step, about `step^2 / sigma`, matters for
49    // `sigma` and thus for the weights. This only happens for a root very close to an endpoint (a
50    // zero of `sigma`), e.g. within 1e-14 of -1 for alpha and beta near -1.
51    //
52    // Unlike in SciPy, a root and its weight where the polynomials overflow (e.g. `L_n` for
53    // n >= 400) are the eigenvalue and 0, instead of NaN for all.
54    let n = i32::try_from(n).expect("n is too large");
55    // the rounding errors of the refined roots
56    let mut dx = vec![0.0; x.len()];
57    for (xi, dxi) in x.iter_mut().zip(&mut dx) {
58        for _ in 0..4 {
59            let step = f(n, *xi) / df(n, *xi);
60            if !step.is_finite() {
61                break;
62            }
63            (*xi, *dxi) = two_sum(*xi, -step);
64            let s = sigma(*xi, *dxi);
65            if step * step <= f64::EPSILON * s * s {
66                break;
67            }
68        }
69    }
70
71    // Unlike in SciPy, the weights are computed from `df` at the refined roots, instead of
72    // `1 / (f(n - 1, x) df(n, x))` with `df` at the eigenvalues, which is more sensitive to the
73    // rounding of `x` (about n^2 times near x = +-1).
74    //
75    // They are `mu0 / sum(1 / r^2) / r^2`, with `r = sqrt(sigma) df` scaled to `r >= 1`, so that
76    // only the weights that are tiny relative to `mu0 / n` underflow. A non-finite `r` is an
77    // overflow, with weight 0.
78    let r: Vec<f64> = x
79        .iter()
80        .zip(&dx)
81        .map(|(&xi, &dxi)| {
82            let s = sigma(xi, dxi);
83            s.sqrt() * df(n, xi) * (1.0 - tau(xi) * dxi / s)
84        })
85        .collect();
86    // A zero `r` is an underflow, with weight NaN, and the others 0 (relatively tiny), instead of
87    // NaN for all.
88    let r_min = r
89        .iter()
90        .map(|ri| ri.abs())
91        .filter(|&ri| ri > 0.0)
92        .fold(f64::INFINITY, f64::min);
93    let r: Vec<f64> = r
94        .iter()
95        .map(|&ri| {
96            if ri.is_finite() {
97                ri / r_min
98            } else {
99                f64::INFINITY
100            }
101        })
102        .collect();
103    let scale = mu0 / r.iter().map(|ri| 1.0 / (ri * ri)).sum::<f64>();
104    let mut w: Vec<f64> = r.iter().map(|ri| scale / ri / ri).collect();
105
106    match nodes {
107        Plain => {},
108        Symmetric => {
109            w = w
110                .iter()
111                .zip(w.iter().rev())
112                .map(|(a, b)| (a + b) / 2.0)
113                .collect();
114            x = x
115                .iter()
116                .zip(x.iter().rev())
117                .map(|(a, b)| (a - b) / 2.0)
118                .collect();
119        },
120        Shifted => {
121            x = x
122                .iter()
123                .zip(&dx)
124                .map(|(xi, dxi)| ((xi + 1.0) + dxi) / 2.0)
125                .collect();
126        },
127    }
128    (x, w)
129}
130
131/// What [`gen_roots_and_weights`] does with the roots
132#[derive(Clone, Copy)]
133enum Nodes {
134    Plain,
135    /// Makes the roots antisymmetric and the weights symmetric
136    Symmetric,
137    /// Shifts the roots `x` to `[0, 1]` as `(x + 1) / 2`, but with their rounding errors, so that
138    /// the ones near 0 have a small relative error
139    Shifted,
140}
141
142/// The rule for `f(x / s)` from the one for `f(x)`
143fn scale((x, w): (Vec<f64>, Vec<f64>), s: f64) -> (Vec<f64>, Vec<f64>) {
144    let x = x.into_iter().map(|xi| xi * s).collect();
145    let w = w.into_iter().map(|wi| wi * s).collect();
146    (x, w)
147}
148
149/// `(m, e)` with `m 2^e = exp(l)`, and `e >= 0` only as large as needed for a finite `m`
150fn exp_scaled(l: Dd) -> (f64, f64) {
151    let e = ((l.hi - MAXLOG) / LN_2).ceil().max(0.0);
152    let r = l - LOG2 * e;
153    (r.hi.exp() * (1.0 + r.lo), e)
154}
155
156/// The rule with the weights multiplied by `2^e`, for weights computed with `mu0 / 2^e`
157fn ldexp_weights((x, w): (Vec<f64>, Vec<f64>), e: f64) -> (Vec<f64>, Vec<f64>) {
158    (x, w.into_iter().map(|wi| ldexp_f64(wi, e as i32)).collect())
159}
160
161/// `1 - (x + dx)^2` for `|dx| <= ulp(x)`, with a small relative error near `x + dx = +-1`
162fn one_minus_x2(x: f64, dx: f64) -> f64 {
163    ((1.0 - x) - dx) * ((1.0 + x) + dx)
164}
165
166/// Panics if `n` is zero, like the `ValueError` in SciPy
167fn check_n(n: usize) {
168    assert!(n >= 1, "n must be a positive integer");
169}
170
171/// Gauss-Jacobi quadrature
172///
173/// Corresponds to [`scipy.special.roots_jacobi`][docs].
174///
175/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_jacobi.html
176///
177/// The nodes are the roots of the Jacobi polynomial $P_n^{(\alpha,\beta)}$, and the rule is exact
178/// for polynomials of degree $2n - 1$ with the weight function $(1 - x)^\alpha (1 + x)^\beta$ on
179/// $[-1, 1]$ (A&S 22.2.1).
180///
181/// # Panics
182/// - if `n` is zero
183/// - if $\alpha \le -1$ or $\beta \le -1$
184///
185/// # See also
186/// - [`eval_jacobi`]: Evaluate Jacobi polynomials, $P_n^{(\alpha,\beta)}$
187#[must_use]
188pub fn roots_jacobi(n: usize, alpha: f64, beta: f64) -> (Vec<f64>, Vec<f64>) {
189    check_jacobi(n, alpha, beta);
190    if alpha == 0.0 && beta == 0.0 {
191        return roots_legendre(n);
192    }
193    // Unlike in SciPy, the rule for alpha == beta < -1/2 isn't the Gauss-Gegenbauer one, which is
194    // less accurate near -1 (see `roots_gegenbauer`).
195    if alpha == beta && alpha >= -0.5 {
196        return roots_gegenbauer(n, alpha + 0.5);
197    }
198
199    let (a, b) = (alpha, beta);
200    // Unlike in SciPy, the weights sum to `m` and are then scaled by `2^e`, with
201    // `m 2^e = mu0 = 2^s B(p, q)` for `s = a + b + 1`, `p = a + 1` and `q = b + 1`, so that they
202    // can be finite where `mu0` overflows. Where `B(p, q)` underflows, `ln(mu0)` is computed by
203    // `incbet_lnpow` (for `p, q >= 13`), instead of `s ln(2) + betaln(p, q)`, which cancels.
204    let (s, p, q) = (a + b + 1.0, a + 1.0, b + 1.0);
205    let beta_pq = crate::beta(p, q);
206    let (m, e) = if beta_pq.is_normal() || p.min(q) < 13.0 {
207        // `2^(s - e) <= 2^1000`, and also `2^(s - e) B(p, q) <= 2^1000` if `B(p, q) > 1`
208        let e = (s - 1000.0 + beta_pq.log2().max(0.0)).ceil().max(0.0);
209        ((s - e).exp2() * beta_pq, e)
210    } else {
211        // `ln(2^-(p + q) / B(p, q))` is symmetric, but `incbet_lnpow` needs `p >= q`
212        exp_scaled(Dd::new(-incbet_lnpow(p.max(q), p.min(q), 0.5, 0.5) - LN_2))
213    };
214    let nodes = if a == b { Symmetric } else { Plain };
215    ldexp_weights(jacobi(n, a, b, m, nodes), e)
216}
217
218/// Panics if `n` is zero, or if `alpha <= -1` or `beta <= -1`, like the `ValueError` in SciPy
219fn check_jacobi(n: usize, alpha: f64, beta: f64) {
220    check_n(n);
221    assert!(
222        alpha > -1.0 && beta > -1.0,
223        "alpha and beta must be greater than -1"
224    );
225}
226
227/// The Gauss-Jacobi rule, with the weights summing to `mu0`
228///
229/// Unlike in SciPy, `2 + a + b` is `(a + 1) + (b + 1)` and `b^2 - a^2` is `(b - a) (b + a)`, which
230/// don't cancel for `a, b` near -1.
231fn jacobi(n: usize, a: f64, b: f64, mu0: f64, nodes: Nodes) -> (Vec<f64>, Vec<f64>) {
232    let ab2 = (a + 1.0) + (b + 1.0);
233    let an = |k: f64| {
234        if k == 0.0 {
235            (b - a) / ab2
236        } else {
237            (b - a) * (b + a) / ((2.0 * k - 2.0 + ab2) * (2.0 * k + ab2))
238        }
239    };
240    let bn = |k: f64| {
241        let r = if k == 1.0 {
242            1.0
243        } else {
244            (k * (k - 2.0 + ab2) / (2.0 * k - 3.0 + ab2)).sqrt()
245        };
246        let s = ((k - 1.0 + (a + 1.0)) * (k - 1.0 + (b + 1.0)) / (2.0 * k - 1.0 + ab2)).sqrt();
247        2.0 / (2.0 * k - 2.0 + ab2) * s * r
248    };
249    let f = |n, x| eval_jacobi(n, a, b, x);
250    let df = |n, x| 0.5 * (f64::from(n) - 1.0 + ab2) * eval_jacobi(n - 1, a + 1.0, b + 1.0, x);
251    gen_roots_and_weights(
252        n,
253        mu0,
254        an,
255        bn,
256        f,
257        df,
258        one_minus_x2,
259        |x| b - a - ab2 * x,
260        nodes,
261    )
262}
263
264/// Gauss-Jacobi (shifted) quadrature
265///
266/// Has no corresponding function in `scipy.special`, see [`roots_gengegenbauer`] instead.
267///
268/// The nodes are the roots of the shifted Jacobi polynomial $P_n^{*(\alpha,\beta)}$, and the rule
269/// is exact for polynomials of degree $2n - 1$ with the weight function
270/// $(1 - x)^\alpha x^\beta$ on $[0, 1]$.
271///
272/// # Panics
273/// - if `n` is zero
274/// - if $\alpha \le -1$ or $\beta \le -1$
275///
276/// # See also
277/// - [`eval_sh_jacobi`](crate::eval_sh_jacobi): Evaluate shifted Jacobi polynomials,
278///   $P_n^{*(\alpha,\beta)}$
279/// - [`roots_jacobi`]: Gauss-Jacobi quadrature
280#[must_use]
281pub fn roots_sh_jacobi(n: usize, alpha: f64, beta: f64) -> (Vec<f64>, Vec<f64>) {
282    check_jacobi(n, alpha, beta);
283    // the weights sum to `B(alpha + 1, beta + 1)`, without the factor `2^(alpha + beta + 1)` of
284    // `roots_jacobi`, which can overflow
285    let mu0 = crate::beta(alpha + 1.0, beta + 1.0);
286    jacobi(n, alpha, beta, mu0, Shifted)
287}
288
289/// Gauss-Jacobi quadrature for the generalized Gegenbauer polynomials
290///
291/// Corresponds to [`scipy.special.roots_sh_jacobi`][docs], which, despite its name, isn't
292/// [`roots_sh_jacobi`] (see [`eval_gengegenbauer`](crate::eval_gengegenbauer)).
293///
294/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_sh_jacobi.html
295///
296/// The nodes are the roots of $G_n^{(p,q)}$, and the rule is exact for polynomials of degree
297/// $2n - 1$ with the weight function $(1 - x)^{p-q} x^{q-1}$ on $[0, 1]$ (A&S 22.2.2).
298///
299/// For small $q$, the nodes and weights have relative errors up to about $2^{-54} / q$, from the
300/// rounding of $q - 1$ (also in SciPy).
301///
302/// # Panics
303/// - if `n` is zero
304/// - if $p - q \le -1$ or $q \le 0$, or if $q - 1$ rounds to $-1$ (for $q < 2^{-54}$)
305///
306/// # See also
307/// - [`eval_gengegenbauer`](crate::eval_gengegenbauer): Evaluate generalized Gegenbauer
308///   polynomials, $G_n^{(p,q)}$
309#[must_use]
310pub fn roots_gengegenbauer(n: usize, p: f64, q: f64) -> (Vec<f64>, Vec<f64>) {
311    assert!(
312        p - q > -1.0 && q > 0.0,
313        "(p - q) must be greater than -1, and q must be greater than 0"
314    );
315    roots_sh_jacobi(n, p - q, q - 1.0)
316}
317
318/// Gauss-Gegenbauer quadrature
319///
320/// Corresponds to [`scipy.special.roots_gegenbauer`][docs].
321///
322/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_gegenbauer.html
323///
324/// The nodes are the roots of the Gegenbauer polynomial $C_n^{(\alpha)}$, and the rule is exact
325/// for polynomials of degree $2n - 1$ with the weight function $(1 - x^2)^{\alpha - 1/2}$ on
326/// $[-1, 1]$ (A&S 22.2.3). For $\alpha = 0$, these are the roots of $T_n$, see
327/// [`roots_chebyshev_t`].
328///
329/// The weights are NaN if $C_n^{(\alpha)}$ overflows at all nodes, e.g. for $n = 150$ and
330/// $\alpha = 10^4$ (also in SciPy). Near $\alpha = -1/2$, they lose accuracy (also in SciPy): for
331/// odd $n$, the relative error is about $n \cdot 10^{-16} / (\alpha + 1/2)$, and within about
332/// $10^{-15}$ of $-1/2$, some can be NaN. [`roots_jacobi`] with $\alpha - 1/2$ for both
333/// parameters doesn't have this problem.
334///
335/// # Panics
336/// - if `n` is zero
337/// - if $\alpha \le -1/2$
338///
339/// # See also
340/// - [`eval_gegenbauer`]: Evaluate Gegenbauer polynomials, $C_n^{(\alpha)}$
341#[must_use]
342pub fn roots_gegenbauer(n: usize, alpha: f64) -> (Vec<f64>, Vec<f64>) {
343    check_n(n);
344    assert!(alpha > -0.5, "alpha must be greater than -0.5");
345    // Unlike in SciPy, a subnormal alpha is treated as 0, where `C_n` at the central root would
346    // underflow.
347    if alpha.abs() < f64::MIN_POSITIVE {
348        // C(n,0,x) == 0 uniformly, however, as alpha->0, C(n,alpha,x)->T(n,x)
349        return roots_chebyshev_t(n);
350    }
351
352    // Unlike in SciPy, `B(1/2, alpha + 1/2)` doesn't overflow, so it needs no approximation for
353    // large alpha.
354    let mu0 = crate::beta(0.5, alpha + 0.5);
355    let an = |_| 0.0;
356    let bn = |k: f64| {
357        if k == 1.0 {
358            // the general case, without the cancelling factors `2 alpha` for small alpha
359            (1.0 / (2.0 * (1.0 + alpha))).sqrt()
360        } else {
361            (k * (k + 2.0 * alpha - 1.0) / (4.0 * (k + alpha) * (k + alpha - 1.0))).sqrt()
362        }
363    };
364    let f = |n, x| eval_gegenbauer(n, alpha, x);
365    let df = |n: i32, x: f64| {
366        let c = f64::from(n);
367        (-c * x * f(n, x) + ((c - 1.0) + 2.0 * alpha) * f(n - 1, x)) / one_minus_x2(x, 0.0)
368    };
369    gen_roots_and_weights(
370        n,
371        mu0,
372        an,
373        bn,
374        f,
375        df,
376        one_minus_x2,
377        |x| -(2.0 * alpha + 1.0) * x,
378        Symmetric,
379    )
380}
381
382/// Gauss-Legendre quadrature
383///
384/// Corresponds to [`scipy.special.roots_legendre`][docs].
385///
386/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_legendre.html
387///
388/// The nodes are the roots of the Legendre polynomial $P_n$, and the rule is exact for
389/// polynomials of degree $2n - 1$ on $[-1, 1]$ (A&S 22.2.10).
390///
391/// # Panics
392/// - if `n` is zero
393///
394/// # See also
395/// - [`eval_legendre`]: Evaluate Legendre polynomials, $P_n$
396#[must_use]
397pub fn roots_legendre(n: usize) -> (Vec<f64>, Vec<f64>) {
398    check_n(n);
399    let an = |_| 0.0;
400    let bn = |k: f64| k * (1.0 / (4.0 * k * k - 1.0)).sqrt();
401    let f = |n, x| eval_legendre(n, x);
402    let df = |n: i32, x: f64| {
403        let c = f64::from(n);
404        (-c * x * f(n, x) + c * f(n - 1, x)) / one_minus_x2(x, 0.0)
405    };
406    gen_roots_and_weights(n, 2.0, an, bn, f, df, one_minus_x2, |x| -2.0 * x, Symmetric)
407}
408
409/// Gauss-Legendre (shifted) quadrature
410///
411/// Corresponds to [`scipy.special.roots_sh_legendre`][docs].
412///
413/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_sh_legendre.html
414///
415/// The nodes are the roots of the shifted Legendre polynomial $P_n^*$, and the rule is exact for
416/// polynomials of degree $2n - 1$ on $[0, 1]$ (A&S 22.2.11).
417///
418/// # Panics
419/// - if `n` is zero
420///
421/// # See also
422/// - [`eval_sh_legendre`](crate::eval_sh_legendre): Evaluate shifted Legendre polynomials, $P_n^*$
423#[must_use]
424pub fn roots_sh_legendre(n: usize) -> (Vec<f64>, Vec<f64>) {
425    // Unlike in SciPy, the nodes near 0 aren't `(x + 1) / 2` with the nodes `x` of
426    // `roots_legendre`, which cancels.
427    roots_sh_jacobi(n, 0.0, 0.0)
428}
429
430/// Gauss-Chebyshev (first kind) quadrature
431///
432/// Corresponds to [`scipy.special.roots_chebyt`][docs].
433///
434/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_chebyt.html
435///
436/// The nodes are the roots of the Chebyshev polynomial $T_n$, and the rule is exact for
437/// polynomials of degree $2n - 1$ with the weight function $1 / \sqrt{1 - x^2}$ on $[-1, 1]$
438/// (A&S 22.2.4).
439///
440/// # Panics
441/// - if `n` is zero
442///
443/// # See also
444/// - [`eval_chebyshev_t`](crate::eval_chebyshev_t): Evaluate Chebyshev polynomials of the first
445///   kind, $T_n$
446#[doc(alias = "roots_chebyt")]
447#[must_use]
448pub fn roots_chebyshev_t(n: usize) -> (Vec<f64>, Vec<f64>) {
449    check_n(n);
450    let m = n as f64;
451    // `sin(pi k / (2n))` for `k = 1 - n, 3 - n, ..., n - 1`
452    let x = (0..n).map(|i| crate::sinpi((2.0 * i as f64 + 1.0 - m) / (2.0 * m)));
453    (x.collect(), vec![PI / m; n])
454}
455
456/// Gauss-Chebyshev (second kind) quadrature
457///
458/// Corresponds to [`scipy.special.roots_chebyu`][docs].
459///
460/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_chebyu.html
461///
462/// The nodes are the roots of the Chebyshev polynomial $U_n$, and the rule is exact for
463/// polynomials of degree $2n - 1$ with the weight function $\sqrt{1 - x^2}$ on $[-1, 1]$
464/// (A&S 22.2.5).
465///
466/// # Panics
467/// - if `n` is zero
468///
469/// # See also
470/// - [`eval_chebyshev_u`](crate::eval_chebyshev_u): Evaluate Chebyshev polynomials of the second
471///   kind, $U_n$
472#[doc(alias = "roots_chebyu")]
473#[must_use]
474pub fn roots_chebyshev_u(n: usize) -> (Vec<f64>, Vec<f64>) {
475    check_n(n);
476    let m = n as f64 + 1.0;
477    // Unlike in SciPy, `cos(t)` and `sin(t)` with `t = pi k / (n + 1)` are `sinpi` of arguments in
478    // `[-1/2, 1/2]`, as in `roots_chebyshev_t`, which is more accurate near `t = 0` and `t = pi`.
479    let rule = (1..=n).rev().map(|k| {
480        let sin = crate::sinpi(k.min(n + 1 - k) as f64 / m);
481        (
482            crate::sinpi((m - 2.0 * k as f64) / (2.0 * m)),
483            PI * sin * sin / m,
484        )
485    });
486    rule.unzip()
487}
488
489/// Gauss-Chebyshev (first kind) quadrature on $[-2, 2]$
490///
491/// Corresponds to [`scipy.special.roots_chebyc`][docs].
492///
493/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_chebyc.html
494///
495/// The nodes are the roots of $C_n(x) = 2 T_n(x / 2)$, and the rule is exact for polynomials of
496/// degree $2n - 1$ with the weight function $1 / \sqrt{1 - (x/2)^2}$ on $[-2, 2]$ (A&S 22.2.6).
497///
498/// # Panics
499/// - if `n` is zero
500///
501/// # See also
502/// - [`eval_chebyshev_c`](crate::eval_chebyshev_c): Evaluate $C_n$
503#[doc(alias = "roots_chebyc")]
504#[must_use]
505pub fn roots_chebyshev_c(n: usize) -> (Vec<f64>, Vec<f64>) {
506    scale(roots_chebyshev_t(n), 2.0)
507}
508
509/// Gauss-Chebyshev (second kind) quadrature on $[-2, 2]$
510///
511/// Corresponds to [`scipy.special.roots_chebys`][docs].
512///
513/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_chebys.html
514///
515/// The nodes are the roots of $S_n(x) = U_n(x / 2)$, and the rule is exact for polynomials of
516/// degree $2n - 1$ with the weight function $\sqrt{1 - (x/2)^2}$ on $[-2, 2]$ (A&S 22.2.7).
517///
518/// # Panics
519/// - if `n` is zero
520///
521/// # See also
522/// - [`eval_chebyshev_s`](crate::eval_chebyshev_s): Evaluate $S_n$
523#[doc(alias = "roots_chebys")]
524#[must_use]
525pub fn roots_chebyshev_s(n: usize) -> (Vec<f64>, Vec<f64>) {
526    scale(roots_chebyshev_u(n), 2.0)
527}
528
529/// Gauss-Chebyshev (first kind, shifted) quadrature
530///
531/// Corresponds to [`scipy.special.roots_sh_chebyt`][docs].
532///
533/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_sh_chebyt.html
534///
535/// The nodes are the roots of $T_n^*(x) = T_n(2x - 1)$, and the rule is exact for polynomials of
536/// degree $2n - 1$ with the weight function $1 / \sqrt{x - x^2}$ on $[0, 1]$ (A&S 22.2.8).
537///
538/// # Panics
539/// - if `n` is zero
540///
541/// # See also
542/// - [`eval_sh_chebyshev_t`](crate::eval_sh_chebyshev_t): Evaluate $T_n^*$
543#[doc(alias = "roots_sh_chebyt")]
544#[must_use]
545pub fn roots_sh_chebyshev_t(n: usize) -> (Vec<f64>, Vec<f64>) {
546    let (_, w) = roots_chebyshev_t(n);
547    let m = n as f64;
548    // Unlike in SciPy, the nodes are `sin(t / 2 + pi / 4)^2` instead of `(1 + sin(t)) / 2`, with
549    // `sin(t)` the nodes of `roots_chebyshev_t`, which cancels near 0.
550    let x = (0..n).map(|i| crate::sinpi((2.0 * i as f64 + 1.0) / (4.0 * m)).powi(2));
551    (x.collect(), w)
552}
553
554/// Gauss-Chebyshev (second kind, shifted) quadrature
555///
556/// Corresponds to [`scipy.special.roots_sh_chebyu`][docs].
557///
558/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_sh_chebyu.html
559///
560/// The nodes are the roots of $U_n^*(x) = U_n(2x - 1)$, and the rule is exact for polynomials of
561/// degree $2n - 1$ with the weight function $\sqrt{x - x^2}$ on $[0, 1]$ (A&S 22.2.9).
562///
563/// # Panics
564/// - if `n` is zero
565///
566/// # See also
567/// - [`eval_sh_chebyshev_u`](crate::eval_sh_chebyshev_u): Evaluate $U_n^*$
568#[doc(alias = "roots_sh_chebyu")]
569#[must_use]
570pub fn roots_sh_chebyshev_u(n: usize) -> (Vec<f64>, Vec<f64>) {
571    let (_, w) = roots_chebyshev_u(n);
572    let m = n as f64 + 1.0;
573    // Unlike in SciPy, the nodes are `cos(t / 2)^2` instead of `(1 + cos(t)) / 2`, with `cos(t)`
574    // the nodes of `roots_chebyshev_u`, which cancels near 0.
575    let x = (1..=n).map(|k| crate::sinpi(k as f64 / (2.0 * m)).powi(2));
576    // the weights sum to `B(3/2, 3/2) = pi/8` instead of `pi/2`
577    (x.collect(), w.into_iter().map(|wi| wi / 4.0).collect())
578}
579
580/// Gauss-generalized Laguerre quadrature
581///
582/// Corresponds to [`scipy.special.roots_genlaguerre`][docs].
583///
584/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_genlaguerre.html
585///
586/// The nodes are the roots of the generalized Laguerre polynomial $L_n^{(\alpha)}$, and the rule
587/// is exact for polynomials of degree $2n - 1$ with the weight function $x^\alpha e^{-x}$ on
588/// $[0, \infty)$ (A&S 22.3.9).
589///
590/// # Panics
591/// - if `n` is zero
592/// - if $\alpha \le -1$
593///
594/// # See also
595/// - [`eval_genlaguerre`]: Evaluate generalized Laguerre polynomials, $L_n^{(\alpha)}$
596#[must_use]
597pub fn roots_genlaguerre(n: usize, alpha: f64) -> (Vec<f64>, Vec<f64>) {
598    check_n(n);
599    assert!(alpha > -1.0, "alpha must be greater than -1");
600
601    let mu0 = crate::gamma(alpha + 1.0);
602    if n == 1 {
603        return (vec![alpha + 1.0], vec![mu0]);
604    }
605
606    let an = |k: f64| 2.0 * k + alpha + 1.0;
607    let bn = |k: f64| -(k * (k + alpha)).sqrt();
608    let f = |n, x| eval_genlaguerre(n, alpha, x);
609    // Unlike in SciPy, the derivative is `-L_{n-1}^(alpha+1)` (DLMF 18.9.23), which doesn't cancel
610    // for alpha near -1.
611    let df = |n: i32, x: f64| -eval_genlaguerre(n - 1, alpha + 1.0, x);
612
613    // Unlike in SciPy, the weights can be finite where `mu0` overflows (alpha > 170.6), with
614    // `ln(mu0)` in double-double.
615    let (mu0, e) = if mu0.is_finite() {
616        (mu0, 0.0)
617    } else {
618        ln_gamma(Dd::new(alpha) + 1.0).map_or((f64::NAN, 0.0), |(l, _, _)| exp_scaled(l))
619    };
620    let rule = gen_roots_and_weights(
621        n,
622        mu0,
623        an,
624        bn,
625        f,
626        df,
627        |x, dx| x + dx,
628        |x| alpha + 1.0 - x,
629        Plain,
630    );
631    ldexp_weights(rule, e)
632}
633
634/// Gauss-Laguerre quadrature
635///
636/// Corresponds to [`scipy.special.roots_laguerre`][docs].
637///
638/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_laguerre.html
639///
640/// The nodes are the roots of the Laguerre polynomial $L_n$, and the rule is exact for
641/// polynomials of degree $2n - 1$ with the weight function $e^{-x}$ on $[0, \infty)$
642/// (A&S 22.2.13).
643///
644/// # Panics
645/// - if `n` is zero
646///
647/// # See also
648/// - [`eval_laguerre`](crate::eval_laguerre): Evaluate Laguerre polynomials, $L_n$
649#[must_use]
650pub fn roots_laguerre(n: usize) -> (Vec<f64>, Vec<f64>) {
651    roots_genlaguerre(n, 0.0)
652}
653
654/// The largest `n` for which the Hermite rules use [`gen_roots_and_weights`] instead of
655/// [`roots_hermite_asy`], like in SciPy
656const HERMITE_GW_MAX: usize = 150;
657
658/// Gauss-Hermite (physicist's) quadrature
659///
660/// Corresponds to [`scipy.special.roots_hermite`][docs].
661///
662/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_hermite.html
663///
664/// The nodes are the roots of the Hermite polynomial $H_n$, and the rule is exact for polynomials
665/// of degree $2n - 1$ with the weight function $e^{-x^2}$ on $(-\infty, \infty)$ (A&S 22.2.14).
666/// For $n > 150$, they are computed by the asymptotic method of Townsend, Trogdon, and Olver
667/// [^TTO].
668///
669/// [^TTO]: A. Townsend, T. Trogdon, and S. Olver, "Fast computation of Gauss quadrature nodes and
670///   weights on the whole real line", IMA J. Numer. Anal. 36 (2016),
671///   <https://arxiv.org/abs/1410.5286>
672///
673/// # Panics
674/// - if `n` is zero
675///
676/// # See also
677/// - [`eval_hermite_h`]: Evaluate physicist's Hermite polynomials, $H_n$
678#[doc(alias = "roots_hermite")]
679#[must_use]
680pub fn roots_hermite_h(n: usize) -> (Vec<f64>, Vec<f64>) {
681    check_n(n);
682    if n > HERMITE_GW_MAX {
683        return roots_hermite_asy(n);
684    }
685    let an = |_| 0.0;
686    let bn = |k: f64| (k / 2.0).sqrt();
687    let f = |n: i32, x| eval_hermite_h(n as u32, x);
688    let df = |n: i32, x| 2.0 * f64::from(n) * f(n - 1, x);
689    let tau = |x: f64| -2.0 * x;
690    gen_roots_and_weights(n, SQRT_PI, an, bn, f, df, |_, _| 1.0, tau, Symmetric)
691}
692
693/// Gauss-Hermite (statistician's) quadrature
694///
695/// Corresponds to [`scipy.special.roots_hermitenorm`][docs].
696///
697/// [docs]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.roots_hermitenorm.html
698///
699/// The nodes are the roots of the Hermite polynomial $He_n$, and the rule is exact for
700/// polynomials of degree $2n - 1$ with the weight function $e^{-x^2/2}$ on $(-\infty, \infty)$
701/// (A&S 22.2.15). For $n > 150$, they are scaled from [`roots_hermite_h`].
702///
703/// # Panics
704/// - if `n` is zero
705///
706/// # See also
707/// - [`eval_hermite_he`]: Evaluate probabilist's Hermite polynomials, $He_n$
708#[doc(alias = "roots_hermitenorm")]
709#[must_use]
710pub fn roots_hermite_he(n: usize) -> (Vec<f64>, Vec<f64>) {
711    check_n(n);
712    if n > HERMITE_GW_MAX {
713        return scale(roots_hermite_asy(n), SQRT_2);
714    }
715    let an = |_| 0.0;
716    let bn = |k: f64| k.sqrt();
717    let f = |n: i32, x| eval_hermite_he(n as u32, x);
718    let df = |n: i32, x| f64::from(n) * f(n - 1, x);
719    gen_roots_and_weights(
720        n,
721        SQRT_TAU_DOWN,
722        an,
723        bn,
724        f,
725        df,
726        |_, _| 1.0,
727        |x| -x,
728        Symmetric,
729    )
730}
731
732/// Corresponds to `_compute_tauk`: the root of `tau - sin(tau) = c` of Lemma 3.1 in [^TTO], by
733/// 5 Newton steps
734///
735/// [^TTO]: see [`roots_hermite_h`]
736fn compute_tauk(n: usize, k: f64) -> f64 {
737    let a = (n % 2) as f64 - 0.5;
738    let h = (n / 2) as f64;
739    let c = (4.0 * h - 4.0 * k + 3.0) * PI / (4.0 * h + 2.0 * a + 2.0);
740    let mut xi = 0.5 * PI;
741    for _ in 0..5 {
742        xi -= (xi - xi.sin() - c) / (1.0 - xi.cos());
743    }
744    xi
745}
746
747/// Corresponds to `_initial_nodes_a`: Tricomi's approximation of the square of the `k`-th
748/// positive root of `H_n` (Lemma 3.1 in [^TTO]), except near `sqrt(2n + 1)`
749///
750/// [^TTO]: see [`roots_hermite_h`]
751fn initial_nodes_a(n: usize, k: f64) -> f64 {
752    let tauk = compute_tauk(n, k);
753    let sigk = (0.5 * tauk).cos().powi(2);
754    let a = (n % 2) as f64 - 0.5;
755    let nu = 4.0 * (n / 2) as f64 + 2.0 * a + 2.0;
756    // Initial approximation of Hermite roots (square)
757    nu * sigk - 1.0 / (3.0 * nu) * (5.0 / (4.0 * (1.0 - sigk).powi(2)) - 1.0 / (1.0 - sigk) - 0.25)
758}
759
760/// Corresponds to `_initial_nodes_b`: Gatteschi's approximation of the square of the `k`-th
761/// positive root of `H_n` from the top (Lemma 3.2 in [^TTO]), given the `k`-th zero `ak` of Ai
762///
763/// [^TTO]: see [`roots_hermite_h`]
764fn initial_nodes_b(n: usize, ak: f64) -> f64 {
765    let a = (n % 2) as f64 - 0.5;
766    let nu = 4.0 * (n / 2) as f64 + 2.0 * a + 2.0;
767    // Initial approximation of Hermite roots (square)
768    nu + 2.0_f64.powf(2.0 / 3.0) * ak * nu.powf(1.0 / 3.0)
769        + 1.0 / 5.0 * 2.0_f64.powf(4.0 / 3.0) * ak.powi(2) * nu.powf(-1.0 / 3.0)
770        + (9.0 / 140.0 - 12.0 / 175.0 * ak.powi(3)) * nu.powi(-1)
771        + (16.0 / 1575.0 * ak + 92.0 / 7875.0 * ak.powi(4))
772            * 2.0_f64.powf(2.0 / 3.0)
773            * nu.powf(-5.0 / 3.0)
774        - (15152.0 / 3031875.0 * ak.powi(5) + 1088.0 / 121275.0 * ak.powi(2))
775            * 2.0_f64.powf(1.0 / 3.0)
776            * nu.powf(-7.0 / 3.0)
777}
778
779/// Corresponds to `_initial_nodes`: approximations of the non-negative roots of `H_n`, by
780/// [`initial_nodes_a`] up to the turnover point, and [`initial_nodes_b`] above it
781fn initial_nodes(n: usize) -> Vec<f64> {
782    // Turnover point
783    // linear polynomial fit to error of 10, 25, 40, ..., 1000 point rules
784    let fit = 0.49082003 * n as f64 - 4.37859653;
785    let turnover = fit.round_ties_even() as usize;
786    let h = n / 2;
787    // the indices `k` of `initial_nodes_b`, from `kmax` down to 1
788    let kmax = h.saturating_sub(turnover + 1);
789    let ak = crate::xsf::airy_ai_zeros_vec(kmax);
790
791    // Central node is always zero
792    let zero = (n % 2 == 1).then_some(0.0);
793    let xa = (1..=h.min(turnover + 1)).map(|k| initial_nodes_a(n, k as f64));
794    let xb = ak.into_iter().rev().map(|ak| initial_nodes_b(n, ak));
795    zero.into_iter()
796        .chain(xa.chain(xb).map(f64::sqrt))
797        .collect()
798}
799
800/// Corresponds to `_pbcf`: the parabolic cylinder function `U(a, x)` (DLMF 12.10.35) and its
801/// derivative (DLMF 12.10.36), with `a = -n - 1/2` and `x = sqrt(2n + 1) cos(theta)`, by its
802/// asymptotic expansion in Airy functions (Sections 3.2 and 3.3 of [^TTO], with one more term)
803///
804/// [^TTO]: see [`roots_hermite_h`]
805#[rustfmt::skip]
806fn pbcf(n: usize, theta: f64) -> (f64, f64) {
807    let (st, ct) = theta.sin_cos();
808    // https://dlmf.nist.gov/12.10#vii
809    let mu = 2.0 * n as f64 + 1.0;
810    // https://dlmf.nist.gov/12.10#E23
811    let eta = 0.5 * theta - 0.5 * st * ct;
812    // https://dlmf.nist.gov/12.10#E39
813    let zeta = -(3.0 * eta / 2.0).powf(2.0 / 3.0);
814    // https://dlmf.nist.gov/12.10#E40
815    let phi = (-zeta / st.powi(2)).powf(0.25);
816    // Coefficients
817    // https://dlmf.nist.gov/12.10#E43
818    let a0 = 1.0;
819    let a1 = 0.10416666666666666667;
820    let a2 = 0.08355034722222222222;
821    let a3 = 0.12822657455632716049;
822    let a4 = 0.29184902646414046425;
823    let a5 = 0.88162726744375765242;
824    let b0 = 1.0;
825    let b1 = -0.14583333333333333333;
826    let b2 = -0.09874131944444444444;
827    let b3 = -0.14331205391589506173;
828    let b4 = -0.31722720267841354810;
829    let b5 = -0.94242914795712024914;
830    // Polynomials
831    // https://dlmf.nist.gov/12.10#E9
832    // https://dlmf.nist.gov/12.10#E10
833    let ctp = |k: i32| ct.powi(k);
834    let u0 = 1.0;
835    let u1 = (1.0 * ctp(3) - 6.0 * ct) / 24.0;
836    let u2 = (-9.0 * ctp(4) + 249.0 * ctp(2) + 145.0) / 1152.0;
837    let u3 = (-4042.0 * ctp(9) + 18189.0 * ctp(7) - 28287.0 * ctp(5)
838        - 151995.0 * ctp(3) - 259290.0 * ct) / 414720.0;
839    let u4 = (72756.0 * ctp(10) - 321339.0 * ctp(8) - 154982.0 * ctp(6)
840        + 50938215.0 * ctp(4) + 122602962.0 * ctp(2) + 12773113.0) / 39813120.0;
841    let u5 = (82393456.0 * ctp(15) - 617950920.0 * ctp(13) + 1994971575.0 * ctp(11)
842        - 3630137104.0 * ctp(9) + 4433574213.0 * ctp(7) - 37370295816.0 * ctp(5)
843        - 119582875013.0 * ctp(3) - 34009066266.0 * ct) / 6688604160.0;
844    let v0 = 1.0;
845    let v1 = (1.0 * ctp(3) + 6.0 * ct) / 24.0;
846    let v2 = (15.0 * ctp(4) - 327.0 * ctp(2) - 143.0) / 1152.0;
847    let v3 = (-4042.0 * ctp(9) + 18189.0 * ctp(7) - 36387.0 * ctp(5)
848        + 238425.0 * ctp(3) + 259290.0 * ct) / 414720.0;
849    let v4 = (-121260.0 * ctp(10) + 551733.0 * ctp(8) - 151958.0 * ctp(6)
850        - 57484425.0 * ctp(4) - 132752238.0 * ctp(2) - 12118727.0) / 39813120.0;
851    let v5 = (82393456.0 * ctp(15) - 617950920.0 * ctp(13) + 2025529095.0 * ctp(11)
852        - 3750839308.0 * ctp(9) + 3832454253.0 * ctp(7) + 35213253348.0 * ctp(5)
853        + 130919230435.0 * ctp(3) + 34009066266.0 * ct) / 6688604160.0;
854    // Airy Evaluation (Bi and Bip unused)
855    let [ai, aip, _, _] = crate::airy(mu.powf(4.0 / 6.0) * zeta);
856    // Prefactor for U
857    let p = 2.0 * SQRT_PI * mu.powf(1.0 / 6.0) * phi;
858    // Terms for U
859    // https://dlmf.nist.gov/12.10#E42
860    let phip = |k: i32| phi.powi(6 * k);
861    let a_0 = b0 * u0;
862    let a_1 = (b2 * u0 + phip(1) * b1 * u1 + phip(2) * b0 * u2) / zeta.powi(3);
863    let a_2 = (b4 * u0 + phip(1) * b3 * u1 + phip(2) * b2 * u2 + phip(3) * b1 * u3
864        + phip(4) * b0 * u4) / zeta.powi(6);
865    let b_0 = -(a1 * u0 + phip(1) * a0 * u1) / zeta.powi(2);
866    let b_1 = -(a3 * u0 + phip(1) * a2 * u1 + phip(2) * a1 * u2 + phip(3) * a0 * u3)
867        / zeta.powi(5);
868    let b_2 = -(a5 * u0 + phip(1) * a4 * u1 + phip(2) * a3 * u2 + phip(3) * a2 * u3
869        + phip(4) * a1 * u4 + phip(5) * a0 * u5) / zeta.powi(8);
870    // U
871    // https://dlmf.nist.gov/12.10#E35
872    let u = p * (ai * (a_0 + a_1 / mu.powi(2) + a_2 / mu.powi(4))
873        + aip * (b_0 + b_1 / mu.powi(2) + b_2 / mu.powi(4)) / mu.powf(8.0 / 6.0));
874    // Prefactor for derivative of U
875    let pd = SQRT_TAU_DOWN * mu.powf(2.0 / 6.0) / phi;
876    // Terms for derivative of U
877    // https://dlmf.nist.gov/12.10#E46
878    let c_0 = -(b1 * v0 + phip(1) * b0 * v1) / zeta;
879    let c_1 = -(b3 * v0 + phip(1) * b2 * v1 + phip(2) * b1 * v2 + phip(3) * b0 * v3)
880        / zeta.powi(4);
881    let c_2 = -(b5 * v0 + phip(1) * b4 * v1 + phip(2) * b3 * v2 + phip(3) * b2 * v3
882        + phip(4) * b1 * v4 + phip(5) * b0 * v5) / zeta.powi(7);
883    let d_0 = a0 * v0;
884    let d_1 = (a2 * v0 + phip(1) * a1 * v1 + phip(2) * a0 * v2) / zeta.powi(3);
885    let d_2 = (a4 * v0 + phip(1) * a3 * v1 + phip(2) * a2 * v2 + phip(3) * a1 * v3
886        + phip(4) * a0 * v4) / zeta.powi(6);
887    // Derivative of U
888    // https://dlmf.nist.gov/12.10#E36
889    let ud = pd * (ai * (c_0 + c_1 / mu.powi(2) + c_2 / mu.powi(4)) / mu.powf(4.0 / 6.0)
890        + aip * (d_0 + d_1 / mu.powi(2) + d_2 / mu.powi(4)));
891    (u, ud)
892}
893
894/// Corresponds to `_newton`: at most 5 Newton steps in `theta` (see [`pbcf`]) from the
895/// approximate non-negative roots `x` of `H_n`, and the weights of those roots
896fn newton(n: usize, x: &[f64]) -> (Vec<f64>, Vec<f64>) {
897    // Variable transformation
898    let mu = (2.0 * n as f64 + 1.0).sqrt();
899    let mut theta: Vec<f64> = x.iter().map(|xi| (xi / mu).acos()).collect();
900    let mut ud = Vec::new();
901    // Newton iteration
902    for _ in 0..5 {
903        let (u, d): (Vec<f64>, Vec<f64>) = theta.iter().map(|&t| pbcf(n, t)).unzip();
904        let mut max = 0.0_f64;
905        for ((t, ui), udi) in theta.iter_mut().zip(u).zip(&d) {
906            let dtheta = ui / (SQRT_2 * mu * t.sin() * udi);
907            *t += dtheta;
908            max = max.max(dtheta.abs());
909        }
910        ud = d;
911        if max < 1e-14 {
912            break;
913        }
914    }
915    // Undo variable transformation
916    let mut x: Vec<f64> = theta.iter().map(|t| mu * t.cos()).collect();
917    // Central node is always zero
918    if n % 2 == 1 {
919        x[0] = 0.0;
920    }
921    // Compute weights
922    let w: Vec<f64> = x
923        .iter()
924        .zip(ud)
925        .map(|(xi, udi)| (-xi * xi).exp() / (2.0 * udi * udi))
926        .collect();
927    (x, w)
928}
929
930/// Corresponds to `_roots_hermite_asy`: [`roots_hermite_h`] for large `n`, in linear time
931fn roots_hermite_asy(n: usize) -> (Vec<f64>, Vec<f64>) {
932    let (nodes, weights) = newton(n, &initial_nodes(n));
933    // Combine with negative parts (without the central zero of odd n)
934    let skip = n % 2;
935    let x = nodes
936        .iter()
937        .skip(skip)
938        .rev()
939        .map(|x| -x)
940        .chain(nodes.iter().copied());
941    let w: Vec<f64> = weights
942        .iter()
943        .skip(skip)
944        .rev()
945        .chain(&weights)
946        .copied()
947        .collect();
948    // Scale weights
949    let scale = SQRT_PI / w.iter().sum::<f64>();
950    (x.collect(), w.into_iter().map(|wi| wi * scale).collect())
951}