Springe zum Inhalt oder Footer
SerloDie freie Lernplattform

Aufgaben zu Algorithmen

  1. 1

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

     m=max(a.bit_length(), b.bit_length())
    • Wenn diese Zahl m kleiner oder gleich 1 ist, berechnest du das Produkt ab 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 a1 und a0 erzeugst du am effizientesten durch Bit-Schieben und Bit-Maskieren.

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

    a1=a>>k
    • Das hintere Teilstück a0 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 2k1. Die Zahl 2k erzeugst du, indem du 20=1 um k Positionen nach links schiebst.

    a0=a & (1<<k)-1 

    Ganz entsprechend erzeugst du die Teilstücke b1 und b0.

    Rekursion

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

    • p0=a0b0

    • p1=(a1+a0)(b1+b0) und

    • p2=a1b1

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


Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0Was bedeutet das?