Cannot store large values when calculating factorials

Question

I'm implementing an algorithm to get the factorial of a certain number for a programming class.

fn factorial(number: u64) -> u64 {
    if number < 2 {
        1
    } else {
        number * factorial(number - 1)
    }
}

When I tried with 100 or even with 25 I get this error "thread 'main' panicked at 'attempt to multiply with overflow'", so I tried wrapping, and the result function was:

fn factorial(number: u64) -> u64 {
    if number < 2 {
        1
    } else {
        number.wrapping_mul(factorial(number - 1))
    }
}

This way there is not panic but the result is always zero, so I tried using f64 and result was

100! = 93326215443944100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

instead of

100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Is there another way to store the result so the right value is returned?

Answer 1

100! is a really big number. In fact, the largest factorial that will fit in a u64 is just 20!. For numbers that don't fit in a u64, num::bigint::BigUint is an appropriate storage option.

The following code calculates a value for 100!. You can run it in your browser here.

extern crate num;

use num::BigUint;

fn factorial(number: BigUint) -> BigUint {
    let big_1 = 1u32.into();
    let big_2 = 2u32.into();
    if number < big_2 {
        big_1
    } else {
        let prev_factorial = factorial(number.clone() - big_1);
        number * prev_factorial
    }
}

fn main() {
    let number = 100u32.into();
    println!("{}", factorial(number));
}

To give some insight into why u64 doesn't work, you can call the bits method on the result. If you do so, you will find that the value of 100! requires 525 bits to store. That's more than 8 u64's worth of storage.