Karazuba-Algorithmus

Algorithmus zur schnellen Multiplikation
(Weitergeleitet von Karatsuba-Algorithmus)

Der Karazuba-Algorithmus ist ein Algorithmus zur Multiplikation zweier großer ganzer Zahlen. Er wurde 1960 von dem 23-jährigen Anatoli Alexejewitsch Karazuba (engl. Karatsuba, russisch Анатолий Алексеевич Карацуба) entwickelt und 1962 veröffentlicht.

Bezeichnet die Bit-Anzahl der beiden Zahlen und ein Landau-Symbol, so ist der Algorithmus mit einer Laufzeitkomplexität von deutlich schneller als die Schulmethode. Diese (und auch deren implizite Übertragung auf das Binärsystem in Form der russischen Bauernmultiplikation) besitzt eine Laufzeitkomplexität von . Die Methode von Karazuba wurde zum Vorbild für das Teile-und-herrsche-Prinzip in der Informatik. Für hinreichend große Zahlen ist der Karazuba-Algorithmus langsamer als seine Verallgemeinerungen, wie der Toom-Cook-Algorithmus (1965) und der Schönhage-Strassen-Algorithmus (1971), dessen Laufzeitkomplexität beträgt und der aus Sicht der Komplexitätstheorie als schnellster Algorithmus zur Multiplikation großer ganzer Zahlen galt, bis 2007 Martin Fürer eine Weiterentwicklung mit einer (bisher nur theoretisch) geringeren Laufzeitkomplexität vorstellte.[1]

Idee des Algorithmus

Bearbeiten

Multiplizieren verursacht in der Schulmethode einen Aufwand, der mit dem Quadrat der Stellenanzahl wächst, während Additionen und Verschiebeoperationen, bei denen mit einer Potenz der Basis des verwendeten Stellenwertsystems multipliziert wird, nur linearen Aufwand benötigen. Die Idee ist, nach dem Teile-und-herrsche-Prinzip die beiden zu multiplizierenden Zahlen in zwei Teile aufzuspalten, und die Multiplikationen soweit möglich durch Additionen und Verschiebeoperationen zu ersetzen. Das Ausmultiplizieren der aufgeteilten Zahlen ergibt drei Teilterme, die durch vier Multiplikationen gebildet werden. Diese können durch Verschiebe- und Additionsoperationen zum Gesamtergebnis zusammengesetzt werden. Einer dieser Terme ist dabei eine Summe zweier Produkte. Dieser Term lässt sich als Differenz mit einem neuen Produkt und der Summe der anderen beiden Teilterme schreiben. Insgesamt spart man so also eine Teilmultiplikation ein. Führt man dieses Verfahren rekursiv durch, so erhält man eine wesentlich günstigere Laufzeit als nach der Schulmethode.

Der Algorithmus im Detail

Bearbeiten

Der hier angegebene Algorithmus gilt für natürliche Zahlen, er lässt sich aber leicht auch auf ganze Zahlen verallgemeinern, indem ihre Vorzeichen gesondert berücksichtigt werden. Die Faktoren   und   seien im Stellenwertsystem zur Basis   als Tupel dargestellt. Der Wert von   ist unerheblich: Etwa in einem Computer mit einem Multiplizierer für 32 Bit breite Zahlen würde   gewählt werden. Die Beispiele weiter unten verwenden Dezimalzahlen. Um die Rekursion bis   durchführen zu können, seien die Längen beider Zifferntupel eine Zweierpotenz   mit  , und es sei  . Das ist immer erreichbar durch geeignet vorangestellte Nullen; an der unten durchgeführten Laufzeitabschätzung ändert sich dadurch nichts Wesentliches.

Die Zifferntupel seien also

  und  

Jedes Zifferntupel wird nun in zwei Tupel der Länge   aufgespalten. Das liefert die vier Zahlen

  und   sowie
  und  

Damit ist

  und  

Ausmultipliziert ergibt sich

 

Den Term   kann man nun in eine andere, hier schneller berechenbare Form bringen:

 

Damit ergibt sich für das Produkt die Darstellung

 

in der nur noch die drei „kurzen“ Produkte

 

erscheinen. Rekursiv berechnet und mit einfachen Verschiebe- und Additionsoperationen verknüpft ergeben sie

 

Von den vier möglichen Produkten (von X mit Y) Xh Yh, Xh Yl, Xl Yh, Xl Yl wird das erste P1 und das letzte P2 direkt im Ergebnis verwendet. Der Term aus der Summe der beiden mittleren Produkten kann als Summe von allen Produkten minus des ersten und letzten Produkt gebildet werden. Die Summe aus allen vier Produkten kann über das neu eingeführte Produkt P3 mit nur einer Multiplikation erzeugt werden.

Laufzeitanalyse

Bearbeiten

Eine Multiplikation zweier  -stelliger Zahlen wird zurückgeführt auf drei Multiplikationen von je zwei  -stelligen Zahlen und vier Additionen bzw. Subtraktionen  -stelliger Zahlen eventuell mit Überträgen sowie mit zwei Verschiebungen. Die benötigte Zeit für die Operationen, die keine Multiplikationen sind, ist kleiner als   mit einer von   unabhängigen Konstanten  . Bezeichnet   die Gesamtzahl der Operationen bei der Multiplikation zweier  -stelliger Zahlen, so gilt

 

Der hier anwendbare erste Fall des Master-Theorems mit   und   liefert   als Laufzeitkomplexität von   Die direkte Herleitung mit vollständiger Induktion ermöglicht einen genaueren Einblick:

 

Ersetzen von   durch   ergibt dann

 

Beispiel zur Produktumformung

Bearbeiten

Die zu multiplizierenden Zahlen seien

  und  .

Da es hier nur um die Veranschaulichung der Produktumformung geht, wird mit vorangestellten Nullen auf die nächste gerade und gleiche Länge und nicht auf eine Zweipotenzlänge aufgefüllt. Damit ergeben sich die Zifferntupel

  und  

der Länge  , die in vier Tupel der Länge   zerlegt werden:

  und   sowie
  und  

Es gilt

  und
 

Die benötigten Produkte sind

 ,
  und
  

Der Algorithmus würde die Produkte  ,   und   rekursiv bestimmen. Es bleibt das Ergebnis gemäß obiger Formel zusammenzusetzen:

 

Während die Schulmethode 110 Ziffernmultiplikationen und 90 Additionen (ohne Überträge) benötigt, sind es hier 92 Multiplikationen und 83 Additionen.

Verallgemeinerung

Bearbeiten

Statt in zwei Teile, können die zu multiplizierenden Zahlen auch in mehr Teile zerlegt werden. Durch geschickte Linearkombination von Teilergebnissen genügen dann bei Zerlegung in   Teile   Multiplikationen auf den kleineren Zahlen. Rekursiv angewandt führt dieses Verfahren dann zum Toom-Cook-Algorithmus.

Literatur

Bearbeiten
  • A. Karatsuba, Y. Ofman: Multiplication of Many-Digital Numbers by Automatic Computers. In: Soviet Physics-Doklady. 7, 1963, S. 595–596 (engl. Übersetzung des russ. Originals. In: Doklady Akad. Nauk SSSR. Band 145, 1962, S. 293–294).
  • A. A. Karacuba: Berechnungen und die Kompliziertheit von Beziehungen. In: Elektron. Informationsverarb. Kybernetik. 11, 1975, S. 603–606.
  • A. A. Karatsuba: The Complexity of Computations. In: Proc. Steklov Inst. Math. 211, 1995, S. 169–183 (cs.ru PDF; engl. Übersetzung des russ. Originals. In: Trudy Mat. Inst. Steklova. 211, 1995, S. 186–202).
  • D. E. Knuth: The Art of Computer Programming. Band 2: Seminumerical Algorithms. Addison-Wesley Publ.Co., Reading, Mass., 1969, ISBN 0-201-89684-2.
Bearbeiten

Einzelnachweise und Anmerkungen

Bearbeiten
  1. Das englische Lemma Fürer's algorithm enthält dazu einige Hinweise.