Aufgaben zu Algorithmen

Programmiere eine rekursive Funktion karatsuba_mul(a, b), um zwei nichtnegative ganze Zahlen $a$ und $b$ mit dem Karatsuba-Multiplikationsverfahren miteinander zu multiplizieren.

In den folgenden Hinweisen wird beispielhaft Python als Programmiersprache benutzt.

Hinweise:

Du bestimmst zunächst das Maximum der Bit-Längen der beiden Operanden $a$ und $b$.:

• Wenn diese Zahl $m$ kleiner oder gleich 1 ist, berechnest du das Produkt $a \cdot b$ konventionell und gibst diesen Wert zurück.

• Ansonsten setzt du $k = m//2$ (ganzzahlige Division durch 2) und beginnst mit der rekursiven Berechnung.

Operanden aufteilen

Die Teilstücke $a_1$ und $a_0$ erzeugst du am effizientesten durch Bit-Schieben und Bit-Maskieren.

• Das vordere Teilstück $a_1$ erhältst du, indem du $a$ um $k$ Positionen nach rechts schiebst:

• Das hintere Teilstück $a_0$ erhältst du, indem du eine "Bit-Maske" von $k$ Einsen über $a$ legst und nur diejenigen Bits von $a$ berücksichtigst, die unter diesen Einsen liegen.

Technisch gesehen realisiert du diese Maskierung durch eine Und-Verknüpfung (Operator &). Die Bit-Maske von $k$ Einsen entspricht der Zahl $2^k -1$. Die Zahl $2^k$ erzeugst du, indem du $2^0 = 1$ um $k$ Positionen nach links schiebst.

Ganz entsprechend erzeugst du die Teilstücke $b_1$ und $b_0$.

Rekursion

Nun berechnest du durch rekursive Aufrufe der Funktion karatsuba_mul die drei Produkte

• $p_0 = a_0\cdot b_0$

• $p_1 = (a_1+a_0)\cdot(b_1+b_0)$ und

• $p_2 = a_1\cdot b_1$

Zum Schluss berechnest du nach der Formel des Karatsuba-Algorithmus die drei Teilstücke $c_0$, $c_1$ und $c_2$ und schiebst diese jeweils um 0 Bit, $k$ Bit und $2k$ Bit nach links, bevor du sie addierst und als Ergebnis zurückgibst.