Rust如何处理大数避免斐波那契计算出现add with overflow溢出错误

问题原因 #

报错为整数溢出触发的panic：u64类型最大可容纳值为18446744073709551615，斐波那契第94项的数值已经超过该上限，debug模式下Rust默认开启整数溢出检查，因此程序直接退出。

解决方案：使用任意精度大整数 #

不需要手动实现基于智能指针的堆存储大数逻辑，Rust生态已经有成熟的任意精度无符号大整数实现BigUint，其内部已经封装了动态堆内存管理，支持无限大小的正整数运算（只要内存足够）。

修改步骤 #

1. 首先在项目的Cargo.toml中添加依赖：

[dependencies]
num-bigint = "0.4"
num-traits = "0.2"

2. 修改业务代码，将原来的u64替换为BigUint即可：

use num_bigint::BigUint;
use num_traits::{Zero, One};

fn fib(n: u8) -> BigUint {
    let mut prev = BigUint::zero();
    let mut curr = BigUint::one();
    
    for _ in 1..n {
        let next = prev + &curr;
        prev = curr;
        curr = next;
    }
    
    curr
}

fn main() {
    // 可自由调整循环上限，只要内存足够就不会出现溢出问题
    for n in 1..200 {
        let curr = fib(n);
        println!("fibonacci {} is {}", n, curr);
    }
}

关于智能指针实现大数的说明 #

你提到的用智能指针把大数存在堆上的思路是完全正确的，BigUint的底层逻辑就是按照这个思路实现的：它会把大整数拆成多个u32/u64的分段，存储在堆上的动态数组（Vec，本身就是带智能指针语义的容器）中，运算的时候自动处理分段的进位、溢出逻辑，上层使用者不需要关心底层的内存管理细节。如果是学习目的你也可以自行基于Vec<u64>实现自己的大整数类型，生产环境直接用num-bigint即可。

内容的提问来源于stack exchange，提问作者mangesh daspute