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

[vlvrd]

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

(Playground)

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.

[steffahn]

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

[quinedot]

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.

[scottmcm]

@vlvrd

I ended up using the try_fold function of the Iterator trait with checked multiplications

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

@vlvrd

if there is a better way of doing this (optimizations are welcome)

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 e^x, you don't recalculate k! every term, you use the previous value.