xsf/scipy_special/factorial.rs
1use num_traits::{PrimInt, Unsigned};
2
3/// Factorial $n!$
4///
5/// Pure rust implementation of [`scipy.special.factorial(n, exact=True)`][factorial].
6///
7/// [factorial]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.factorial.html
8///
9/// # Maximum `n`
10///
11/// Anything larger than the maximum `n` for the given unsigned integer type will overflow.
12///
13/// | type | `n <= _` |
14/// |----------|---------:|
15/// | [`u8`] | 5 |
16/// | [`u16`] | 8 |
17/// | [`u32`] | 12 |
18/// | [`u64`] | 20 |
19/// | [`u128`] | 34 |
20///
21/// # Examples
22///
23/// ```
24/// assert_eq!([0_u32, 1, 2, 4, 8].map(xsf::factorial), [1, 1, 2, 24, 40_320]);
25/// ```
26///
27/// # See also
28/// - [`factorial_checked`]: factorial with overflow checking
29/// - [`multifactorial`]: multifactorial $n!_{(k)}$
30#[inline]
31pub fn factorial<N: PrimInt + Unsigned>(n: N) -> N {
32 multifactorial(n, N::one())
33}
34
35/// Factorial $n!$ with overflow checking
36///
37/// # Examples
38///
39/// ```
40/// assert_eq!(xsf::factorial_checked(12_u32), Some(479_001_600));
41/// assert_eq!(xsf::factorial_checked(13_u32), None);
42/// ```
43///
44/// # See also
45/// - [`factorial`]: unchecked factorial
46/// - [`multifactorial_checked`]: multifactorial with overflow checking
47#[inline]
48pub fn factorial_checked<N: PrimInt + Unsigned>(n: N) -> Option<N> {
49 multifactorial_checked(n, N::one())
50}
51
52/// Multifactorial $n!_{(k)}$ for positive $k$
53///
54/// Corresponds to [`scipy.special.factorialk(n, k, exact=True)`][factorialk].
55///
56/// [factorialk]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.factorialk.html
57///
58/// # Panics
59/// - If $k = 0$ and $n = 1$, as $1^\infty$ is indeterminate.
60/// - If $k = 0$ and $n > 1$, as $n^\infty$ is divergent.
61///
62/// # See also
63/// - [`multifactorial_checked`]: multifactorial with overflow checking
64/// - [`factorial`]: factorial $n!$, the special case $k = 1$
65#[doc(alias = "factorialk", alias = "factorial2")]
66#[inline]
67pub fn multifactorial<N: PrimInt + Unsigned>(n: N, k: N) -> N {
68 if k.is_zero() {
69 if n.is_zero() {
70 n
71 } else if n.is_one() {
72 panic!("1^∞ is indeterminate");
73 } else {
74 panic!("n^∞ is divergent for n>1");
75 }
76 } else if n <= k {
77 if n.is_zero() { N::one() } else { n }
78 } else {
79 let (mut out, mut val) = (n, n);
80 while val > k {
81 val = val - k;
82 out = out * val;
83 }
84 out
85 }
86}
87
88/// Multifactorial $n!_{(k)}$ for positive $k$ with overflow checking
89///
90/// Corresponds to [`scipy.special.factorialk(n, k, exact=True)`][factorialk].
91///
92/// [factorialk]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.factorialk.html
93///
94/// # See also
95/// - [`multifactorial`]: unchecked multifactorial
96/// - [`factorial_checked`]: factorial $n!$ with overflow checking
97#[doc(alias = "factorialk_checked", alias = "factorial2_checked")]
98#[inline]
99pub fn multifactorial_checked<N: PrimInt + Unsigned>(n: N, k: N) -> Option<N> {
100 if k.is_zero() {
101 if n.is_zero() { Some(n) } else { None }
102 } else if n <= k {
103 Some(if n.is_zero() { N::one() } else { n })
104 } else {
105 let (mut out, mut val) = (n, n);
106 while val > k {
107 val = val - k;
108 out = out.checked_mul(&val)?;
109 }
110 Some(out)
111 }
112}