计算阶乘时无法存储大值

Question

我正在实现一个算法来获得编程类的一定数量的阶乘。

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

当我尝试100或甚至25时我得到这个错误"thread 'main' panicked at 'attempt to multiply with overflow'"，所以我尝试包装，结果函数是：

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

这种方式没有恐慌，但结果始终为零，所以我尝试使用f64，结果是

100! = 93326215443944100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

代替

100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

是否有另一种方法来存储结果，以便返回正确的值？

Answer 1

100！是一个非常大的数字。事实上，适合u64的最大因子只有20！对于不适合u64的数字，num::bigint::BigUint是一个合适的存储选项。

以下代码计算100！的值。您可以在浏览器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));
}

为了深入了解为什么u64不起作用，你可以在结果上调用bits方法。如果你这样做，你会发现价值100！需要525位才能存储。这超过了8个u64的存储空间。