斐波那契數列中的負輸出

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

正如你可以看到here第47 Fibonacci數超過32位/ 4字節爲整數的範圍內。之後的一切都會變成負面的。

對於您的程序，您使用了一個長整型，它可能是32位或64位寬，C++標準並不能保證（出於很好的理由）。如果我看到你的結果，對我來說就像是32位。

首先，爲了防止出現負面情況，您可以使用unsigned long int，這會使所有結果成爲正數，並且可以爲「稍微」增大的數字建模。

但是，如果您傳遞第47個斐波那契數，因爲您的數據類型仍然太小，您仍然會得到錯誤的結果。要解決這個問題，你可以使用unsigned long long或者uint64_t。

請記住，即使對於這樣的大數據類型，可以表示數字高達約。在第89次迭代中，斐波納契數字超過了18萬億/十億分之一（10^18）。