Come funziona l'esponenziazione di Fibonacci con l'algoritmo di squadratura?

5

Questo è uno dei migliori algoritmi per calcolare l'ennesima sequenza di Fibonacci. ha bisogno di O (log (n)) per fare il suo lavoro, quindi è così efficiente. L'ho trovato da qualche parte ma non so come funziona! Qualcuno può dirmi come funziona questo algoritmo? Grazie. Ecco il codice:

int fib3 (int n) {

    int i = 1, j = 0, k = 0, h = 1, t;
    while (n > 0) {
        if (n % 2) {
            t = j * h;
            j = i * h + j * k + t;
            i = i * k + t;
        }
        t = h * h;
        h = 2 * k * h + t;
        k = k * k + t;
        n /= 2;
    }
    return j;
}
    
posta Rasool 07.02.2014 - 21:51
fonte

1 risposta

3

Si chiama "forma a matrice" - dai un'occhiata a Wikipedia

Puoi calcolare il prossimo numero di Fibonacci (k + 2) moltiplicando la matrice su un vettore di due elementi precedenti (k + 1 e k). Quindi, k + 3 può essere calcolato moltiplicando la matrice sul vettore di (k + 2 e k + 1). Questo è uguale alla matrice quadrata moltiplicata per (k + 1 e k). Quindi.

Il tuo codice piazza semplicemente la matrice, tenendo conto dei poteri dispari.

    
risposta data 07.02.2014 - 22:22
fonte

Leggi altre domande sui tag