Fibonacci序列中的负输出

Question

尽管使用long int,但在Fibonacci序列中添加大数时,我得到负输出.如何解决？

#include <iostream>
using namespace std;
void main() {

    long int sum = 2;
    long int f1 = 1, f2 = 2, f3;
    for (unsigned int i = 2; i < 4000000; i++) {
        f3 = f2 + f1;
        if (!(f3 % 2)) {
            sum += f3;
        }
        swap(f1, f2);
        swap(f2, f3);
    }
    cout << sum << endl;
}

输出为-1833689714

Answer 1

正如您在这里看到的,第47个Fibonacci数超出了32Bit/4Byte整数的范围.之后的一切都会变成消极的.

对于你的程序,你使用了一个long int,它可能是32位或64位宽,C++标准并不保证(出于好的理由).如果我看到你的结果,对我来说似乎是32位.

首先,为了防止消极,你可以使用unsigned long int,这会使你的所有结果都是正数,并且能够模拟"略微"更大的数字.

但是,如果传递第47个Fibonacci数字,由于数据类型仍然太小,您仍会得到错误的结果.要解决此问题,您可以使用unsigned long long或uint64_t.

请记住,即使对于可以表示大约数字的数字的大数据类型.在第89次迭代中,18万亿/五十亿(10 ^ 18)斐波纳契数超过了这个数.