Unsigned Long Long geht nicht über die 93. Fibonacci-Nummer hinaus?

Question

Hier ist der Code, den ich für die Suche nach der n-ten Fibonacci-Zahl hat geschrieben:

unsigned long long fib(int n) 
{ 
    unsigned long long u = 1, v = 1, t; 

    for(int i=2; i<=n; i++) 
    { 
     t = u + v; 
     u = v; 
     v = t; 
    } 

    return v; 
} 

Während der Algorithmus ziemlich schnell läuft, beginnt die Ausgabe an ausflippen, wenn n> 93. Ich denke/weiß, dass es wegen der 64-Bit-Größe des unsigned long long ist. Ich bin neu in C++, aber gibt es Möglichkeiten, dies zu umgehen, so dass ich die Antwort von etwas wie fib (9999) bekommen kann?

Dank

Answer 1

http://gmplib.org/

GMP ist eine freie Bibliothek für beliebig genaue Arithmetik, auf signierte ganze, rationale Zahlen arbeiten und Gleitkommazahlen. Es gibt keine praktische Grenze für die Genauigkeit außer den durch den verfügbaren Speicher in der Maschine, auf der GMP läuft, implizierten. GMP verfügt über umfangreiche Funktionen und die Funktionen haben eine reguläre Oberfläche.

Die wichtigsten Zielanwendungen für GMP sind Kryptographie-Anwendungen und Forschung, Internet-Sicherheitsanwendungen, Algebrasysteme, Computational Algebra Forschung, etc ...

Answer 2

eine Bigint Bibliothek verwenden. Es gibt viele im Internet (z. B. here und here) oder rollen Sie Ihre eigenen.

EDIT: Rolling your own ist viel schwieriger als ich erwartet hatte. Die Arithmetik ist nicht der schwierige Teil; Es wird das Ergebnis in dezimaler Form ausgedruckt.