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
13/// Returns the `n`th Catalan number using checked `u128` arithmetic.
14///
15/// # Errors
16///
17/// Returns [`CatalanError::CatalanOverflow`] when the result no longer fits in
18/// `u128`.
19///
20/// # Examples
21///
22/// ```rust
23/// use use_catalan::catalan;
24///
25/// assert_eq!(catalan(4)?, 14);
26/// # Ok::<(), use_catalan::CatalanError>(())
27/// ```
28pub fn catalan(n: u64) -> Result<u128, CatalanError> {
29    if n <= 1 {
30        return Ok(1);
31    }
32
33    let mut result = 1_u128;
34    let mut step = 2_u64;
35
36    while step <= n {
37        let mut numerator = u128::from(n) + u128::from(step);
38        let mut denominator = u128::from(step);
39
40        let numerator_gcd = gcd(numerator, denominator);
41        numerator /= numerator_gcd;
42        denominator /= numerator_gcd;
43
44        let result_gcd = gcd(result, denominator);
45        result /= result_gcd;
46        denominator /= result_gcd;
47
48        debug_assert_eq!(denominator, 1);
49
50        result = match result.checked_mul(numerator) {
51            Some(value) => value,
52            None => return Err(CatalanError::CatalanOverflow(n)),
53        };
54
55        step += 1;
56    }
57
58    Ok(result)
59}
60
61/// Returns the `n`th Fuss-Catalan number for a positive `order`.
62///
63/// `order = 2` matches the standard Catalan sequence.
64///
65/// # Errors
66///
67/// Returns [`CatalanError::ZeroOrder`] when `order == 0`.
68///
69/// Returns [`CatalanError::FussCatalanOverflow`] when the result no longer fits
70/// in `u128`.
71///
72/// # Examples
73///
74/// ```rust
75/// use use_catalan::fuss_catalan;
76///
77/// assert_eq!(fuss_catalan(3, 3)?, 12);
78/// # Ok::<(), use_catalan::CatalanError>(())
79/// ```
80pub fn fuss_catalan(order: u64, n: u64) -> Result<u128, CatalanError> {
81    if order == 0 {
82        return Err(CatalanError::ZeroOrder);
83    }
84
85    if n == 0 || order == 1 {
86        return Ok(1);
87    }
88
89    let width = u128::from(order - 1) * u128::from(n);
90    let mut remaining_divisor = width + 1;
91    let mut result = 1_u128;
92    let mut step = 1_u64;
93
94    while step <= n {
95        let mut numerator = width + u128::from(step);
96        let mut denominator = u128::from(step);
97
98        let numerator_gcd = gcd(numerator, denominator);
99        numerator /= numerator_gcd;
100        denominator /= numerator_gcd;
101
102        let result_gcd = gcd(result, denominator);
103        result /= result_gcd;
104        denominator /= result_gcd;
105
106        let divisor_numerator_gcd = gcd(numerator, remaining_divisor);
107        numerator /= divisor_numerator_gcd;
108        remaining_divisor /= divisor_numerator_gcd;
109
110        let divisor_result_gcd = gcd(result, remaining_divisor);
111        result /= divisor_result_gcd;
112        remaining_divisor /= divisor_result_gcd;
113
114        debug_assert_eq!(denominator, 1);
115
116        result = match result.checked_mul(numerator) {
117            Some(value) => value,
118            None => return Err(CatalanError::FussCatalanOverflow { order, n }),
119        };
120
121        step += 1;
122    }
123
124    debug_assert_eq!(remaining_divisor, 1);
125
126    Ok(result)
127}
128
129#[cfg(test)]
130mod tests {
131    use super::{catalan, fuss_catalan};
132    use crate::error::CatalanError;
133
134    #[test]
135    fn computes_catalan_numbers() {
136        assert_eq!(catalan(0), Ok(1));
137        assert_eq!(catalan(1), Ok(1));
138        assert_eq!(catalan(4), Ok(14));
139        assert_eq!(catalan(10), Ok(16_796));
140    }
141
142    #[test]
143    fn computes_fuss_catalan_numbers() {
144        assert_eq!(fuss_catalan(1, 5), Ok(1));
145        assert_eq!(fuss_catalan(2, 4), Ok(14));
146        assert_eq!(fuss_catalan(3, 3), Ok(12));
147        assert_eq!(fuss_catalan(4, 2), Ok(4));
148    }
149
150    #[test]
151    fn rejects_invalid_orders_and_reports_overflow() {
152        assert_eq!(fuss_catalan(0, 3), Err(CatalanError::ZeroOrder));
153        assert!(matches!(
154            catalan(100),
155            Err(CatalanError::CatalanOverflow(100))
156        ));
157        assert!(matches!(
158            fuss_catalan(5, 60),
159            Err(CatalanError::FussCatalanOverflow { order: 5, n: 60 })
160        ));
161    }
162}
use_catalan/counting.rs

use_catalan/
counting.rs
