use_catalan/
counting.rs

1use crate::error::CatalanError;
2
3const fn gcd(mut left: u128, mut right: u128) -> u128 {
4    while right != 0 {
5        let remainder = left % right;
6        left = right;
7        right = remainder;
8    }
9
10    left
11}
12
13fn checked_binomial(total: u128, choose: u64) -> Option<u128> {
14    let choose = choose.min(u64::try_from(total.saturating_sub(u128::from(choose))).ok()?);
15    let mut result = 1_u128;
16    let mut step = 1_u64;
17
18    while step <= choose {
19        let mut numerator = total - u128::from(choose) + u128::from(step);
20        let mut denominator = u128::from(step);
21
22        let numerator_gcd = gcd(numerator, denominator);
23        numerator /= numerator_gcd;
24        denominator /= numerator_gcd;
25
26        let result_gcd = gcd(result, denominator);
27        result /= result_gcd;
28        denominator /= result_gcd;
29
30        debug_assert_eq!(denominator, 1);
31
32        result = result.checked_mul(numerator)?;
33        step += 1;
34    }
35
36    Some(result)
37}
38
39/// Returns the `n`th Catalan number using checked `u128` arithmetic.
40///
41/// # Errors
42///
43/// Returns [`CatalanError::CatalanOverflow`] when the result no longer fits in
44/// `u128`.
45///
46/// # Examples
47///
48/// ```rust
49/// use use_catalan::catalan;
50///
51/// assert_eq!(catalan(4)?, 14);
52/// # Ok::<(), use_catalan::CatalanError>(())
53/// ```
54pub fn catalan(n: u64) -> Result<u128, CatalanError> {
55    match fuss_catalan(2, n) {
56        Ok(value) => Ok(value),
57        Err(CatalanError::FussCatalanOverflow { .. }) => Err(CatalanError::CatalanOverflow(n)),
58        Err(CatalanError::ZeroOrder | CatalanError::CatalanOverflow(_)) => {
59            unreachable!("fuss_catalan(2, n) only reports overflow or success")
60        },
61    }
62}
63
64/// Returns the `n`th Fuss-Catalan number for a positive `order`.
65///
66/// `order = 2` matches the standard Catalan sequence.
67///
68/// # Errors
69///
70/// Returns [`CatalanError::ZeroOrder`] when `order == 0`.
71///
72/// Returns [`CatalanError::FussCatalanOverflow`] when the result no longer fits
73/// in `u128`.
74///
75/// # Examples
76///
77/// ```rust
78/// use use_catalan::fuss_catalan;
79///
80/// assert_eq!(fuss_catalan(3, 3)?, 12);
81/// # Ok::<(), use_catalan::CatalanError>(())
82/// ```
83pub fn fuss_catalan(order: u64, n: u64) -> Result<u128, CatalanError> {
84    if order == 0 {
85        return Err(CatalanError::ZeroOrder);
86    }
87
88    if n == 0 || order == 1 {
89        return Ok(1);
90    }
91
92    let total = u128::from(order) * u128::from(n);
93    let divisor = u128::from(order - 1) * u128::from(n) + 1;
94    let binomial =
95        checked_binomial(total, n).ok_or(CatalanError::FussCatalanOverflow { order, n })?;
96
97    if binomial % divisor != 0 {
98        return Err(CatalanError::FussCatalanOverflow { order, n });
99    }
100
101    Ok(binomial / divisor)
102}
103
104#[cfg(test)]
105mod tests {
106    use super::{catalan, fuss_catalan};
107    use crate::error::CatalanError;
108
109    #[test]
110    fn computes_catalan_numbers() {
111        assert_eq!(catalan(0), Ok(1));
112        assert_eq!(catalan(1), Ok(1));
113        assert_eq!(catalan(4), Ok(14));
114        assert_eq!(catalan(10), Ok(16_796));
115    }
116
117    #[test]
118    fn computes_fuss_catalan_numbers() {
119        assert_eq!(fuss_catalan(1, 5), Ok(1));
120        assert_eq!(fuss_catalan(2, 4), Ok(14));
121        assert_eq!(fuss_catalan(3, 3), Ok(12));
122        assert_eq!(fuss_catalan(4, 2), Ok(4));
123    }
124
125    #[test]
126    fn rejects_invalid_orders_and_reports_overflow() {
127        assert_eq!(fuss_catalan(0, 3), Err(CatalanError::ZeroOrder));
128        assert!(matches!(
129            catalan(100),
130            Err(CatalanError::CatalanOverflow(100))
131        ));
132        assert!(matches!(
133            fuss_catalan(5, 60),
134            Err(CatalanError::FussCatalanOverflow { order: 5, n: 60 })
135        ));
136    }
137}
use_catalan/counting.rs

use_catalan/
counting.rs
