Non firmato Long lungo non andrà oltre il 93 ° numero di Fibonacci?

Question

Ecco il codice che ho scritto per trovare il numero di Fibonacci n-esimo:

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

Mentre l'algoritmo funziona abbastanza rapidamente, l'uscita inizia a freak out quando n> 93. Penso che lo sappia a causa della lunghezza a 64 bit dei lunghi non firmati. Sono nuovo al C++, ma ci sono modi per aggirare questo, così posso ottenere la risposta di qualcosa come fib (9999)?

Grazie

Answer 1

http://gmplib.org/

GMP è una libreria gratuita per arbitraria aritmetica di precisione, che operano su interi con segno, numeri razionali e numeri in virgola mobile. Non esiste un limite pratico alla precisione tranne quelli impliciti dalla memoria disponibile nella macchina su cui gira GMP. GMP ha un ricco set di funzioni e le funzioni hanno un'interfaccia regolare.

Le principali applicazioni di destinazione per le GMP sono applicazioni di crittografia e di ricerca, le applicazioni di sicurezza Internet, sistemi di algebra, la ricerca algebra computazionale, ecc ...

Answer 2

utilizzare una libreria bigint. Ce ne sono molti in giro per il web (ad esempio, here e here) o fai il tuo.

MODIFICA: Rolling your own è molto più difficile di quanto mi aspettassi. L'aritmetica non è la parte difficile; sta stampando il risultato in forma decimale.