Aufgaben zu Algorithmen

Programmiere eine rekursive Funktion karatsuba_mul(a, b), um zwei nichtnegative ganze Zahlen $aa$ und $bb$ 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 $aa$ und $bb$.:

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

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

Operanden aufteilen

Die Teilstücke $a_{1}a\_1$ und $a_{0}a\_0$ erzeugst du am effizientesten durch Bit-Schieben und Bit-Maskieren.

• Das vordere Teilstück $a_{1}a\_1$ erhältst du, indem du $aa$ um $kk$ Positionen nach rechts schiebst:

• Das hintere Teilstück $a_{0}a\_0$ erhältst du, indem du eine "Bit-Maske" von $kk$ Einsen über $aa$ legst und nur diejenigen Bits von $aa$ berücksichtigst, die unter diesen Einsen liegen.

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

Ganz entsprechend erzeugst du die Teilstücke $b_{1}b\_1$ und $b_{0}b\_0$.

Rekursion

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

• $p_0=a_0\cdot b_{0}p\_0\; =\; a\_0\backslash cdot\; b\_0$

• $p_1=(a_1+a_0)\cdot (b_1+b_0)p\_1\; =\; (a\_1+a\_0)\backslash cdot(b\_1+b\_0)$ und

• $p_2=a_1\cdot b_{1}p\_2\; =\; a\_1\backslash cdot\; b\_1$

Zum Schluss berechnest du nach der Formel des Karatsuba-Algorithmus die drei Teilstücke $c_{0}c\_0$, $c_{1}c\_1$ und $c_{2}c\_2$ und schiebst diese jeweils um 0 Bit, $kk$ Bit und $2k2k$ Bit nach links, bevor du sie addierst und als Ergebnis zurückgibst.