Übungen
Teil (a) beruht auf der Fibonacci-Rekursion und zeigt
per einfacher Induktion, dass die Matrix M^n als Koeffizienten die
Zahlen
F(n-2), F(n-1) und F(n) enthält. Teil
(b)
erhält man durch Bildung der Determinanten. Wendet man auf die Aussage
von (a)
das Prinzip der Schnellen Exponentiation an, dann erhält
man ein
sehr effizientes Programm (zu
Beginn der Vorlesung wurden Daten gezeigt) zur Berechnung der Fibonacci-Zahlen,
auf dieser Seite in leicht veränderter Notation dargestellt. Da man
die Matrizen garnicht explizit quadrieren muss, kann man das Programm auch
so schreiben, dass die Matrix- bzw. Vektor-Einträge als Parameter
i,j,h,k
vorkommen. Das ist dann das eingangs vorgestellte, auf den ersten Blick
kryptisch erscheinende Programm fib3.
Interessant ist die Analyse der Bit-Komplexität dieses Verfahrens.
Klar ist, dass man bei input n genau log n Durchläufe
der while-Schleife hat. Aber die Werte der Parameter i,j,h,k wachsen
so rasch an, dass etwa die Hälfte der gesamten Arbeit im letzten Schleifendurchlauf
geleistet werden muss. [Das ist ein Beispiel dafür, dass im Teil (b)
der
Aufgabe 9 für g(n) mit exponentiellem Wachstum, also
etwa g(n) in Theta(2^n) keineswegs f(n) in Theta(n*2^n)
sondern
f(n)
in Theta(2^n) liegt]. Man kommt so (bei traditioneller Multiplikation
auf eine Bit-Komplexität von Theta(n^2), bei schnellster Multiplikation
sogar Theta(n*log^2 n).
Interessant sollte noch folgende Bemerkung sein (eine partielle Antwort
auf (d)): der gleiche Trick der Berechnung mittels schneller Matrix-Exponentiation
lässt sich bei allen Zahlenfolgen G(0),G(1),G(2),... anwenden,
die durch eine lineare Rekursion mit konstanten Koeffizienten definiert
sind, für die es also eine Zahl k (die Ordnung der Rekursion)
und Koeffizienten a(1), a(2), ...,a(k) gibt mit
G(n+1) = a(1)*G(n)+a(2)*G(n-1) + ... + a(k)*G(n-k+1) für n+1 >= k
und Anfangswerten G(0),G(1),...,G(k-1). Die Fibonacci-Folge ist
nur das allereinfachste Beispiel einer solchen Folge.