5. Arithmetische Algorithmen

5.1 Einfache Operationen

Kopieren Sie die Dateien integers.py und timeMyPrograms.py auf Ihren Rechner. Starten Sie 

python3 -i integer.py
n = randomNbitInteger(200000000)
measure_alg(mod17, n)
0.09730930099976831
n = randomNbitInteger(400000000)
measure_alg(mod17, n)
0.19873676600400358

Die Funktion mod17 braucht also ungefähr eine Zehntelsekunde, um den Rest einer 200-millionenstellige Zahl mod 17 auszurechnen; für eine doppelt so große Zahl braucht es doppelt so lange.

Übungsaufgabe 5.1.1 Messen Sie empirisch die Laufzeitkomplexität von mod17. Quälen Sie damit Ihren Rechner mit Zufallszahlen von n Bits und setzen Sie die gemessene Laufzeit mit n in Verbindung.
Schreiben Sie eine Funktion bitSize(n), die die Anzahl der Bits in der Binärdarstellung von n ausrechnet.
Übungsaufgabe 5.1.2

Messen Sie die Laufzeit meiner rekursiven Implementierung der Fibonacci-Zahlen: 

def fibRec(n):
    if (n < 2): 
        return n
    else:
        return fibRec(n-1) + fibRec(n-2)
Messen Sie mit measure_alg die Laufzeit von fibRec(n)für verschiedene Werte von n. Tragen Sie diese in eine Tabelle ein und versuchen Sie, herauszufinden, wozu die Laufzeit proportional ist: Zu n? Zu bitSize(n)? Zu Fn? Zu bitSize(Fn)?
Übungsaufgabe 5.1.3 Wiederholen Sie die vorherige Übung, jetzt aber mit fibIterative: berechnen Sie die Fibonacci-Zahlen iterativ, z.B. mit einer while-Schleife. Um die Laufzeit zu messen, müssen Sie jetzt allerdings größere Werte für n einsetzen.

Wenn wir Algorithmen für Zahlen untersuchen ("arithmetische" Algorithmen), dann ist die entscheidende Messgröße die Bit-Länge unserer Zahlen. Denn dies ist ja auch die Anzahl der Zeichen, die wir schreiben müssen, um die Zahlen zu notieren, äquivlent der Platz im Computer-Speicher, den sie belegen.

Wir haben also gesehen, dass die Laufzeit von mod17(n) ungefähr proportional zu bitSize(n) ist.

Übungsaufgabe 5.1.4 Schreiben Sie einen Algorithmus mod17(byte[] n), wo n ein Array aus Bytes ist und somit eine natürliche Zahl in Basis 256 darstellt. Also zum Beispiel würde n = [2, 177] die Zahl 2⋅256+177=689 darstellen. Ihr Algorithmus mod17 soll diese Zahl modulo 17 ausrechnen und Laufzeit O(1) haben. Für Ihren Algorithmus können Sie annehmen, dass alle arithmetischen Operationen auf int, also auf Zahlen mit bis zu 32 Bit, die Laufzeit O(1) haben, also in konstanter Zeit laufen.

Also: ein arithmetischer Algorithmus ist gut, wenn die Laufzeit ungefähr proportional zur Bit-Länge der Input-Zahlen ist. Probleme wie die Berechnung von Fibonacci-Zahlen stellen hier eine Ausnahme dar: die Zahl n=1000000000 besteht zwar aus wenigen Bits (ungefähr 30), allerdings ist Fn gigantisch groß; ihre Bit-Länge liegt im mehrstelligen Millionenbereich. Wir können also schlicht und einfach nicht erwarten, dass eine Implementierung fib(n) eine Laufzeit hat, die proportional zu bitSize(n) ist. Einfach, weil die Output-Länge zu groß ist. Deswegen:

Beobachtung 5.1.1 Das richtige Komplexitätsmaß für arithmetische Algorithmen ist nicht nur die Bit-Größe der Input-Zahlen, sondern auch der Ouput-Zahlen. Für eine Funktion f:N→N also zum Beispiel bitSize(n)+bitSize(f(n)) .

In den meisten Fällen (Addition, Multiplikation, Division) wird die Bit-Länge des Ergebnisses nicht weit über der der Inputs liegen. Die Fibonacci-Zahlen stellen also hier eine (hoffentlich lehrreiche) Ausnahme dar.

Übungsaufgabe 5.1.5 Zeigen Sie, dass für alle gilt und für alle hinreichend großen .

Übungsaufgabe 5.1.6 Zeigen Sie, dass ist.