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}