# What's the idiomatic or preferred way of calculating factorials?

Hi everyone,

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");
}
}
``````

I'm wondering if there is a better way of doing this (optimizations are welcome) or if I'm better off using a crate - I only came across this one.

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.)

1 Like

Idiomatic, perhaps not, but here's an example adapted from the Fibonacci thread.

35! overflows a `u128`, so yeah, there aren't that many to care about.

1 Like

That's a pretty good way, though you could shorten it a bunch:

``````pub fn n_times_n_factorial_try_fold(n: usize) -> Option<usize> {
(1..=n).try_fold(n, usize::checked_mul)
}
``````

Of course, there's nothing wrong with the normal iterative way either:

``````pub fn n_times_n_factorial_iterative(n: usize) -> Option<usize> {
let mut f = n;
for i in 1..=n {
f = f.checked_mul(i)?;
}
Some(f)
}
``````

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=6cfb15b1ca9d53dda6f7ac1d39a256e7

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.

7 Likes