如何在 Rust 中计算 21 阶乘而不发生整数溢出？

Question

我的项目需要计算 21 的阶乘。

fn factorial(num: u64) -> u64 {
    match num {
        0 => 1,
        1 => 1,
        _ => factorial(num - 1) * num,
    }
}

fn main() {
    let x = factorial(21);
    println!("The value of 21 factorial is {} ", x);
}

运行此代码时，出现错误：

thread 'main' panicked at 'attempt to multiply with overflow', src\main.rs:5:18

Answer 1

一个

u64

无法容纳21！ （介于 2^65 和 2^66 之间），但是

u128

可以。

Answer 2

可能的实施方案是

pub fn factorial(num: u128) -> u128 {
    (1..=num).product()
}


#[test]
fn factorial_of_21() {
   assert_eq!(51090942171709440000,factorial(21));
}

#[test]
fn factorial_of_0() {
   assert_eq!(1,factorial(0));
}

Answer 3

我的项目需要计算 21 的阶乘。

21！不适合 64 位 int。您需要一些任意精度算术（或bigint）库来实现您的库，或者使用128位整数或一些浮点数。

根据这个列表，你可以考虑使用ramp。

Answer 4

我认为实现应该是这样的

pub fn factorial(num: u128) -> u128 {
    (1..=num).product()
}

Answer 5

fn factorial_try_fold(n: u128) -> Option<u128> {
    (1..=n).try_fold(1u128, |acc, f| acc.checked_mul(f))
}

fn main() {
    let num = 21;
    match factorial_try_fold(num) {
        Some(result) => println!("Answer: {}! = {}", num, result),
        None => println!("Error calculating factorial"),
    }
}

输出：

Answer: 21! = 51090942171709440000

Answer 6

fn factorial(num: u128) -> u128 {
    if num <= 1 {
        return 1;
    }
    // Computes saturating at the numeric bounds instead of overflowing
    return num.saturating_mul(factorial(num - 1));
}
 
fn main() {
    let x = factorial(21);
    println!("The value of 21 factorial is {}", x);
}

实现来自C++递归示例。我希望这会有所帮助，但我无法使用

u64

实现代码。可以将值设置为

u64

，但计算会不正确。 21 的

u64

值为 18446744073709551615，而 21 的

u128

值为 51090942171709440000。

https://doc.rust-lang.org/nightly/std/primitive.u128.html#method.saturating_mul https://www.programiz.com/cpp-programming/examples/factorial-recursion