xsf/xsf/binom.rs
1//! Translated into pure Rust from `xsf/binom.h` (scipy/xsf@a985488).
2//!
3//! Original authors: Pauli Virtanen, Eric Moore
4
5use crate::utils::neg_one_pow;
6use crate::xsf::cephes::{beta, gamma, gammasgn, lbeta, poch};
7use crate::xsf::trig::{cephes_sinpi, sinpi_sub};
8
9use core::f64::consts::PI;
10
11/// Binomial coefficient considered as a function of two real variables
12///
13/// For real arguments, the binomial coefficient is defined as
14///
15/// $$
16/// \begin{align*}
17/// \binom{n}{k}
18/// &= {\Gamma(n+1) \over \Gamma(k+1) \\ \Gamma(n-k+1) } \\\\
19/// &= {1 \over (n+1) \\ \Beta(k+1,\\, n-k+1)}
20/// \end{align*}
21/// $$
22///
23/// Where $\Gamma$ is the Gamma function ([`gamma`](crate::gamma)) and $\Beta$ the Beta function
24/// ([`beta`](crate::beta)).
25///
26/// Corresponds to [`scipy.special.binom`][binom].
27///
28/// [binom]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.binom.html
29///
30/// # See also
31/// - [`comb`](crate::comb) integer version "$n$ choose $k$"
32#[must_use]
33#[inline]
34pub fn binom(n: f64, k: f64) -> f64 {
35 let mut kx;
36 let mut nx;
37 let mut num;
38 let mut den;
39
40 if n < 0.0 {
41 nx = n.floor();
42 if n == nx {
43 // Undefined
44 return f64::NAN;
45 }
46 }
47
48 kx = k.floor();
49 if k == kx && (n.abs() > 1e-8 || n == 0.0) {
50 /* Integer case: use multiplication formula for less rounding
51 * error for cases where the result is an integer.
52 *
53 * This cannot be used for small nonzero n due to loss of
54 * precision. */
55 nx = n.floor();
56 if nx == n && kx > nx / 2.0 && nx > 0.0 {
57 // Reduce kx by symmetry
58 kx = nx - kx;
59 }
60 if kx < 0.0 && kx.is_finite() {
61 // Unlike in xsf, 1 / Gamma(1 + kx) = 0 is not lost to the rounding of 1 + k or 1 + n - k
62 // for |k| >= 2^53
63 return 0.0;
64 }
65
66 if (0.0..20.0).contains(&kx) {
67 num = 1.0;
68 den = 1.0;
69 for i in 1..=kx as i32 {
70 num *= f64::from(i) + n - kx;
71 den *= f64::from(i);
72 if num.abs() > 1e50 {
73 num /= den;
74 den = 1.0;
75 }
76 }
77 return num / den;
78 }
79 }
80
81 // general case
82 if n >= 1e10 * k && k > 0.0 {
83 // avoid under/overflows intermediate results
84 return (-lbeta(1.0 + n - k, 1.0 + k) - (n + 1.0).ln()).exp();
85 }
86 if k > 1e8 * n.abs() {
87 // avoid loss of precision (DLMF 5.11.13)
88 num = gamma(1.0 + n) / k.abs() * (1.0 + n * (n + 1.0) / (2.0 * k)); // + ...
89 // split k^n, which can overflow when the result doesn't
90 den = k.abs().powf(n / 2.0);
91 num = num / (PI * den) / den;
92 // Unlike in xsf, the unreachable `k <= 0` branch is omitted
93 kx = k.floor();
94 let dk = k - kx;
95 let sgn = neg_one_pow(kx);
96 return num * cephes_sinpi(dk - n) * sgn;
97 }
98 if k.is_finite() && k.abs() > 2e4 && n.abs() < 170.0 {
99 // Unlike in xsf (scipy/xsf#352), the reflection formula is used for large |k|
100 return binom_reflection(n, k);
101 }
102 let a = 1.0 + n - k;
103 if a < 0.0 && n.fract() != 0.0 {
104 // Unlike in xsf (scipy/xsf#352), Gamma(1 + n) and Gamma(1 + n - k) are reflected, without
105 // the rounding error of `a`, which Gamma(a) amplifies ~|a| times, and more near its poles
106 // (`a` is exact for integer n):
107 //
108 // binom(n, k) = sin(pi (n - k)) / (sin(pi n) (k - n) B(1 + k, -n))
109 let t = sinpi_sub(n, k) / cephes_sinpi(n) / (k - n);
110 let b = beta(1.0 + k, -n);
111 return if b.is_normal() {
112 t / b
113 } else {
114 // B(1 + k, -n) under- or overflows
115 let sgn = t.signum() * gammasgn(1.0 + k) * gammasgn(-n);
116 sgn * (t.abs().ln() - lbeta(1.0 + k, -n)).exp()
117 };
118 }
119 1.0 / (n + 1.0) / beta(a, 1.0 + k)
120}
121
122/// `Gamma(1 + n) sin(pi (n - k + 1)) / (pi poch(k - n, n + 1))`, the reflection formula of
123/// `binom(n, k)`, for `|k| > 2e4` and `|n| < 170`, so that the `poch` base exceeds 1e4
124fn binom_reflection(n: f64, k: f64) -> f64 {
125 let (a, s) = if k > 0.0 {
126 let (kx, nx) = (k.round(), n.round());
127 // sin(pi (n - k + 1)) = (-1)^(kx - nx) sin(pi ((k - kx) - (n - nx)))
128 let sgn = neg_one_pow(kx - nx);
129 (k - n, cephes_sinpi((k - kx) - (n - nx)) * sgn)
130 } else {
131 // the reflection of Gamma(1 + k) instead of Gamma(1 + n - k)
132 (-k, cephes_sinpi(-k))
133 };
134 if s == 0.0 {
135 return 0.0;
136 }
137 // poch(a, n + 1) = poch(a, n) (a + n), because the rounding error of n + 1 would be
138 // amplified by ~ln(a)
139 let p = poch(a, n);
140 let q = p * (a + n);
141 if p.is_normal() && q.is_normal() {
142 return gamma(1.0 + n) / q * (s / PI);
143 }
144 // poch(a, n) is split in two if it over- or underflows
145 let m = 0.5 * n;
146 gamma(1.0 + n) / poch(a, m) * (s / PI) / (poch(a + m, m) * (a + n))
147}