Negative Ausgabe in Fibonacci Sequenz

Question

Ich bekomme negative Ausgabe, wenn große Zahlen in Fibonacci-Sequenz trotz Verwendung long Int hinzugefügt werden. Wie behebt man das?

#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; 
} 

Der Ausgang ist -1833689714

Answer 1

Wie Sie here die 47th Fibonacci-Zahl übersteigt die Reichweite eines 32Bit/4Byte ganze Zahl sehen. Alles danach wird negativ werden.

Für Ihr Programm haben Sie einen langen Int verwendet, der 32 oder 64 Bit breit sein kann, der C++ - Standard garantiert dies jedoch nicht (aus guten Gründen). Wenn ich dein Ergebnis sehe, scheint es wie 32 Bit für mich.

Zuerst, um negative Ergebnisse zu vermeiden, könnten Sie unsigned long int verwenden, was alle Ihre Ergebnisse positiv macht und Ihnen die Möglichkeit gibt, "etwas" größere Zahlen zu modellieren.

Allerdings erhalten Sie immer noch die falschen Ergebnisse, wenn Sie die 47. Fibonacci-Nummer übergeben, da Ihr Datentyp immer noch zu klein ist. Um dies zu beheben, könnten Sie unsigned long long oder unint64_t verwenden.

Denken Sie daran, auch für so große Datentypen, die Zahlen bis zu ca. repräsentieren können. 18 Billionen/Trillion (10^18) übersteigen die Fibonacci-Zahlen diese bei der 89. Iteration.