Die Fibonacci Zahlen einmal anders und in O( log(n) ) berechnet

17.05.2008

Author: N43

Die Berechnung der n-ten Fibonacci Zahl hat mit der direkten Umsetzung der Rekursionsformel

$f_{n+1} = f_n + f_{n-1}$

die Laufzeit O(n). Im Idealfall verzichtet man auf die Rekursion und berechnet den n-ten Wert der Folge iterativ.

Es geht aber noch besser, nämlich in O( log(n) ). Betrachten wir dazu die Matrix $F = \begin{pmatrix} 1 && 1 \\ 1 && 0 \end{pmatrix}$
Multipliziert man F nun mit einer Matrix der folgenden Gestalt $A = \begin{pmatrix} f_{n+1} && f_n \\ f_n && f_{n-1} \end{pmatrix}$ , so erhält man
$F \cdot A = \begin{pmatrix} f_{n+1} + f_n && f_n + f_{n-1} \\ f_{n+1} && f_n \end{pmatrix} $

Durch passende Wahl der Elemente der Matrix A, nämlich, wie auch schon deren Bezeichner suggerieren, als Elemente $f_i$ der Fibonnaci-Folge, erhält man ein neues Element der Fibonacci-Folge, denn $f_{n+1} + f_{n} = f_{n+2}$ .

Und weiter ist $F \cdot A = \begin{pmatrix} f_{n+2} && f_{n+1} \\ f_{n+1} && f_n \end{pmatrix}$ wieder eine Matrix in der Gestalt von A, auf die wir F erneut von links multiplizieren können.

Insgesamt erhält man damit $F^k \cdot A = \begin{pmatrix} f_{n+1+k} && f_{n+k} \\ f_{n+k} && f_{n-1+k} \end{pmatrix}$ und mit $F = \begin{pmatrix} f_2 && f_1 \\ f_1 && f_0 \end{pmatrix} = \begin{pmatrix} 1 && 1 \\ 1 && 0 \end{pmatrix}$ letztendlich

$F^n = F^{n-1} \cdot F = \begin{pmatrix} f_{n+1} && f_n \\ f_n && f_{n-1} \end{pmatrix}$

Durch Anwendung des Square & Multiply Algorithmus zum Potenzieren von F erhält man schließlich einen Algorithmus, der die n-te Fibonacci Zahl in O (log (n)) berechnet.