Skip to main content

xsf/ext/
hahn.rs

1//! Hahn polynomials (DLMF 18.19-18.26)
2//!
3//! With `a1 = alpha + 1` and `b1 = beta + 1`, which don't cancel for alpha and beta near -1.
4
5use crate::utils::{neg_one_pow, pow2};
6
7/// The `|q|` above which [`recurrence`] rescales, so that its products stay finite
8const BIG: f64 = pow2(512);
9
10/// `q_n` of `q_{k+1} = (u q_k - v q_{k-1}) / w`, where `(u, v, w) = coef(k)`
11///
12/// The values are rescaled by powers of 2, so that the result only overflows if `q_n` does.
13fn recurrence(n: u32, mut q0: f64, mut q1: f64, coef: impl Fn(f64) -> (f64, f64, f64)) -> f64 {
14    if n == 0 {
15        return q0;
16    }
17    let mut scale = 0;
18    for k in 1..n {
19        let (u, v, w) = coef(f64::from(k));
20        (q0, q1) = (q1, (u * q1 - v * q0) / w);
21        if q1.abs() > BIG {
22            (q0, q1, scale) = (q0 / BIG, q1 / BIG, scale + 1);
23        }
24    }
25    (0..scale).fold(q1, |q, _| q * BIG)
26}
27
28/// `(A_k, C_k)` of the recurrence in `n` (DLMF 18.22.3), for `k >= 1`
29fn hahn_a_c(k: f64, a1: f64, b1: f64, big_n: f64) -> (f64, f64) {
30    let (ab2, j) = (a1 + b1, k - 1.0);
31    let t = 2.0 * j + ab2; // 2k + alpha + beta
32    let a = (j + ab2) * (k + a1) * (big_n - k) / ((t + 1.0) * (t + 2.0));
33    let c = k * (j + ab2 + big_n) * (j + b1) / (t * (t + 1.0));
34    (a, c)
35}
36
37/// `Q_n(x)` by the recurrence in `n` (DLMF 18.22.2-3)
38fn hahn_q_n(n: u32, a1: f64, b1: f64, big_n: f64, x: f64) -> f64 {
39    let q1 = 1.0 - (a1 + b1) * x / (a1 * big_n);
40    recurrence(n, 1.0, q1, |k| {
41        let (a, c) = hahn_a_c(k, a1, b1, big_n);
42        (a + c - x, c, a)
43    })
44}
45
46/// `Q_n(x)` for integer `x` by the difference equation in `x` (DLMF 18.22.10-11), from
47/// `Q_n(0) = q0`
48fn hahn_q_x(n: u32, a1: f64, b1: f64, big_n: f64, x: u32, q0: f64) -> f64 {
49    let n = f64::from(n);
50    let lambda = n * (n - 1.0 + a1 + b1);
51    let q1 = q0 * (1.0 - lambda / (a1 * big_n));
52    recurrence(x, q0, q1, |k| {
53        let (a, c) = ((k + a1) * (k - big_n), k * (k - b1 - big_n));
54        (lambda + a + c, c, a)
55    })
56}
57
58/// `t0 Q_n(x)` for `x < 1` by its 3F2 sum (DLMF 18.20.5), whose terms after the first all have the
59/// sign of `-t0 x`
60fn hahn_q_sum(n: u32, a1: f64, b1: f64, big_n: f64, x: f64, mut t: f64) -> f64 {
61    // For subnormal x, the terms after the first (which are proportional to x, since `k - x = k`
62    // for `k >= 1`) are scaled by 2^52, so that they stay normal.
63    if x != 0.0 && x.abs() < f64::MIN_POSITIVE {
64        let scale = pow2(52);
65        let s = hahn_q_sum(n, a1, b1, big_n, x * scale, t);
66        return t + (s - t) / scale;
67    }
68    let n = f64::from(n);
69    let mut s = t;
70    let mut k = 0.0;
71    while k < n {
72        // `k - x` last, so that a tiny x doesn't underflow
73        t *= (n - k) / (k + 1.0) * ((n + k - 1.0 + a1 + b1) / (k + a1)) / (big_n - k) * (k - x);
74        s += t;
75        k += 1.0;
76    }
77    s
78}
79
80/// `Q_n(N) = (-1)^n (beta + 1)_n / (alpha + 1)_n`, the factor of the reflection
81/// `Q_n(x; alpha, beta, N) = Q_n(N) Q_n(N - x; beta, alpha, N)` (by the symmetry of the weight in
82/// DLMF Table 18.19.1)
83fn hahn_q_big_n(n: u32, a1: f64, b1: f64) -> f64 {
84    let sign = neg_one_pow(n);
85    (0..n).fold(sign, |q, j| q * ((b1 + f64::from(j)) / (a1 + f64::from(j))))
86}
87
88/// Evaluate the Hahn polynomial $Q_n(x; \alpha, \beta, N)$ at a point.
89///
90/// Not in SciPy.
91///
92/// # Definition
93///
94/// $$
95/// Q_n(x; \alpha, \beta, N) =
96///   \hyp{3}{2}{-n,\enspace n+\alpha+\beta+1,\enspace -x}{\alpha+1,\enspace -N}{1}
97/// $$
98///
99/// where $n = 0, 1, \ldots, N$, see [DLMF 18.20.5]. For $\alpha, \beta > -1$ these are
100/// orthogonal on $x \in \\{0, 1, \ldots, N\\}$, see [DLMF Table 18.19.1]. The result is NaN if
101/// `n > N`, or if `alpha` or `beta` isn't greater than -1.
102///
103/// As $N \to \infty$, they tend to the Jacobi polynomials ([DLMF 18.21.5]):
104///
105/// $$
106/// \lim_{N \to \infty} Q_n(Nx; \alpha, \beta, N) =
107///   \frac{P_n^{(\alpha, \beta)}(1 - 2x)}{P_n^{(\alpha, \beta)}(1)}
108/// $$
109///
110/// so for $\alpha = \beta = 0$ to the Legendre polynomials $P_n(1 - 2x)$.
111///
112/// [DLMF 18.20.5]: https://dlmf.nist.gov/18.20.E5
113/// [DLMF Table 18.19.1]: https://dlmf.nist.gov/18.19.T1
114/// [DLMF 18.21.5]: https://dlmf.nist.gov/18.21.E5
115///
116/// # Algorithm
117///
118/// - $1 \le x \le N - 1$: the three-term recurrence in $n$ ([DLMF 18.22.2]), since the sum
119///   cancels catastrophically. For integer $x$ and $n > \min(x, N - x)$, where that recurrence
120///   can be unstable, the difference equation in $x$ ([DLMF 18.22.10]) from $Q_n(0) = 1$ or
121///   $Q_n(N) = (-1)^n (\beta+1)\_n / (\alpha+1)\_n$, whichever is on the same side of
122///   $A_{n-1} + C_{n-1}$ ([DLMF 18.22.3]) as $x$.
123/// - $x < 1$, and $x > N - 1$ (reflected to $N - x < 1$): the sum, whose terms after the first
124///   then all have the same sign.
125///
126/// [DLMF 18.22.2]: https://dlmf.nist.gov/18.22.E2
127/// [DLMF 18.22.10]: https://dlmf.nist.gov/18.22.E10
128/// [DLMF 18.22.3]: https://dlmf.nist.gov/18.22.E3
129///
130/// # See also
131/// - [`eval_jacobi`](crate::eval_jacobi): Jacobi polynomials $P_n^{(\alpha, \beta)}$
132/// - [`legendre_p`](crate::legendre_p): Legendre polynomials of the first kind $P_n$
133/// - [`hyp3f2`](crate::hyp3f2): Generalized hypergeometric function $_3F_2$
134#[must_use]
135#[allow(non_snake_case)]
136pub fn eval_hahn(n: u32, N: u32, alpha: f64, beta: f64, x: f64) -> f64 {
137    if !(alpha > -1.0 && beta > -1.0 && n <= N) {
138        return f64::NAN;
139    }
140    let (a1, b1, nf, big_nf) = (alpha + 1.0, beta + 1.0, f64::from(n), f64::from(N));
141    if x < 1.0 {
142        hahn_q_sum(n, a1, b1, big_nf, x, 1.0)
143    } else if x > big_nf - 1.0 {
144        hahn_q_sum(n, b1, a1, big_nf, big_nf - x, hahn_q_big_n(n, a1, b1))
145    } else if x.fract() == 0.0 && nf > x.min(big_nf - x) {
146        // At integer x, Q_n(x) is a minimal solution of the recurrence in n for large n and x near
147        // 0 or N. By the duality DLMF 18.21.1, the difference equation in x is stable there, if
148        // it starts on the same side of the center A + C of the oscillatory region in x (where
149        // the characteristic roots of the recurrence in n at n - 1 are complex).
150        let (a, c) = hahn_a_c(nf - 1.0, a1, b1, big_nf);
151        if x <= a + c {
152            hahn_q_x(n, a1, b1, big_nf, x as u32, 1.0)
153        } else {
154            let q_big_n = hahn_q_big_n(n, a1, b1);
155            hahn_q_x(n, b1, a1, big_nf, (big_nf - x) as u32, q_big_n)
156        }
157    } else {
158        hahn_q_n(n, a1, b1, big_nf, x)
159    }
160}