Skip to main content

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}