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 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

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 $F_n$? Zu $\bitsize(F_n)$?

Übungsaufgabe 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 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 \cdot 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 $F_n$ 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 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: \mathbb{N} \rightarrow \mathbb{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 Zeigen Sie, dass $F_n \leq 2^n$ für alle $n$ gilt und $F_n \geq 2^{n/2}$ für alle hinreichend großen $n$.

Übungsaufgabe Zeigen Sie, dass $\bitsize(F_n) \in \Theta(n)$ ist.