What's the idiomatic or preferred way of calculating factorials in Rust? I came across a problem in which I needed to calculate n! * n without overflowing a usize variable, so I ended up using the try_fold function of the Iterator trait with checked multiplications.
fn main() {
let n: usize = 20;
println!("n: {}, usize::MAX: {}", n, usize::MAX);
println!();
let result: Option<usize> = (1..=n)
.try_fold(1, |acc: usize, f: usize| {
let factorial = acc.checked_mul(f);
if let Some(factorial) = factorial {
println!("n!: {}", factorial);
factorial.checked_mul(n)?;
}
factorial
})
.and_then(|factorial| factorial.checked_mul(n));
println!();
if result.is_some() {
println!("n! * n: {}", result.unwrap());
} else {
println!("n! * n overflows a usize");
}
}
Arguably, you could just make a lookup-table. There's not all that many results that fit into any given integer type.
Add a naive (e. g. recursive) implementation for testing purposes and write a test that asserts correctness of all possible inputs (and tests a few failure cases with larger inputs) and you're good.
(For the particular case of usize you do of course also need to handle its platform-dependent size somehow.)
Generally for factorials if you need a bunch you integrate the recurrence relationship into the calculation. For example, if you're doing a taylor series for ex, you don't recalculate k! every term, you use the previous value.