5. Arithmetische Algorithmen

5.2 Schnelle Matrix-Exponentiation

Ich zeige Ihnen jetzt eine trickreiche Methode, Fibonacci-Zahlen noch schneller zu berechnen. In Ihrem itertativen Code haben Sie wahrscheinlich etwas in der Art geschrieben: 

        newA = b 
        newB = a + b
        a = newA
        b = newB
Mathematisch ausgedrückt: jeder Schleifendurchlauf bildet das Paar auf ein neues Paar ab, nämlich Dies ist eine lineare Abbildung und kann als Matrix dargestellt werden: Schreiben wir also und , dann ist der Vektor nach Schleifendurchläufen zu geworden. Anders gesagt: Wir können also berechnen, indem wir berechnen. Wir brauchen also einen Algorithmus für die Matrix-Exponentiation. Einen naiven Algorithmus sehen Sie hier: 
function matrixExp (M, n):
    R := die Identitätsmatrix                                
    for i = 1 ... n: 
        R := M * R 
    return R
Übungsaufgabe 5.2.1 Implementieren Sie matrixExp(M, n) in Python. Beschränken Sie sich hier auf -Matrizen . Schreiben Sie als erstes eine Funktion matrixMult(A,B), die zwei -Matrizen multipliziert. Falls Sie es vergessen haben:
Übungsaufgabe 5.2.2 Messen Sie empirisch die Laufzeit Ihrer Funktion matrixExp(M,n) für eine feste Matrix , die Sie selbst wählen dürfen, und wachsende Zahlen . Wie verhält sich die Laufzeit in Abhängigkeit von ?

Schnelle Exponentiation

Mittels Rekursion können Sie Matrix-Exponentiation viel schneller implementieren. Die Idee ist einfach: wenn gerade ist, also , dann können wir rechnen. Der erste Schritt ist ein rekursiver Aufruf. Der zweite Schritt multipliziert einfach das Ergebnis mit sich selbst. Wenn ungerade ist, also , dann rechnen wir also wie im geraden Fall, nur, dass wir noch eine Multiplikation mit am Ende ausführen. Sie sehen: der Wert von halbiert sich mit jedem rekursiven Aufruf, sie haben also höchstens rekursive Aufrufe.
Übungsaufgabe 5.2.3 Schreiben Sie in Python eine Funktion fastMatrixExp(M,n), die diese Idee implementiert. Messen Sie die Laufzeit. Setzen Sie die Laufzeit zu in Bezug. Was geschieht mit der Laufzeit, wenn Sie verdoppeln?
Übungsaufgabe 5.2.4 Wenn Sie fastMatrixExp(M,n) richtig implementiert haben, wird ein Aufruf nur Operationen ausführen, da sich ja in jedem Schritt halbiert. Warum ist die gemessene Laufzeit dennoch nicht ?

Um die Laufzeit von fastMatrixExp auch theoretisch zu verstehen, nehmen wir vereinfachend an, dass gilt, also eine Zweierpotenz ist. Dies ist besonders bequem, weil in diesem Falle die "Zwischenergebnisse" von fastMatrixExp die folgende Form haben:

In jeden Schritt nehmen wir also die vorherige Matrix und quadrieren sie. Wie lange benötigen wir, um eine Matrix zu quadrieren?

Wir brauchen also acht Multiplikationen und vier Additionen. Intuitiv gesehen ist Multiplikation schwieriger als Addition, daher beschränken wir uns darauf, die Komplexität der acht Multiplikationen verstehen zu wollen. Nehmen wir an, die Zahlen haben Bit-Länge höchstens . Sei die Komplexität der Multiplikation von -Bit-Zahlen. Dann brauchen wir also Schritte für die Quadrierung unserer Matrix.

Wenn , dann ist

Die vier Einträge in haben also Bit-Länge , und somit dauert die letzte Matrix-Quadrierung, auch viele Schritte. Was ist mit den vorherigen Schritten, also ? Der braucht viele Schritte. Es wird sich herausstellen, dass diese Schritte nicht so sehr ins Gewicht fallen. Formell gesprochen: wenn wir berechnen, dann entfällt ein konstant großer Anteil der Laufzeit auf den letzten Schritt: .

Übungsaufgabe 5.2.5 Messen Sie empirisch, wie lange es in Python braucht, zwei -stellige Zahlen miteinander zu multiplizieren. Legen Sie eine Tabelle an! Was geschieht mit der Laufzeit, wenn Sie verdoppeln?

Übungsaufgabe 5.2.6 Schreiben Sie eine Funktion fibFME, die wie oben beschrieben mithilfe der Fast Matrix Exponentation berechnet. Messen Sie die Laufzeit und untersuchen Sie, wie sich eine Verdopplung von auf die Laufzeit auswirkt.