Multiplizieren kann mensch seit mindestens 4000 Jahren, wie babylonische Multiplikationstabellen belegen. Aber erst jetzt wurde der schnellstmögliche Algorithmus zur Multiplikation zweier Zahlen gefunden, in einer letzte Woche auf dem französischen Preprintserver HAL angelegten Arbeit „Integer multiplication in time O(n logn)“.

Zur Vorgeschichte: 1971 hatten Arnold Schönhage und Volker Strassen vermutet, dass es für die Multiplikation zweier n-stelliger Zahlen einen Algorithmus mit O(n logn) Rechenoperationen geben sollte und dass dies bestmöglich ist. (Die O-Notation bedeutet, dass die Anzahl der Operationen höchstens Cnlogn ist für eine Konstante C.) In ihrer Arbeit „Schnelle Multiplikation großer Zahlen“ fanden sie immerhin einen Algorithmus mit O(n logn log(logn)) Schritten, was bis 2007 der unverbesserte Rekord blieb. (Der in der Schule verwendete Algorithmus braucht übrigens O(n2) Schritte.)

Die Idee von Schönhage und Strassen war, die Multiplikation ganzer Zahlen auf die Multiplikation von Polynomen zurückzuführen. Für die Multiplikation ganzzahliger Polynome gibt es Algorithmen, die auf schneller Fourier-Transformation beruhen. (Erläuterungen und Beispiele findet man hier.) Wenn man also n-stellige Zahlen in Stücke der Größe log(n) aufspaltet, kann man sie als Polynome vom Grad O(n/logn) kodieren und dann Algorithmen zur Polynommultiplikation anwenden. Die neue Arbeit von Harvey und v.d.Hoefen findet nun die (vermutlich) bestmögliche Kodierung ganzer Zahlen durch Polynome (in mehreren Variablen – der Punkt ist, dass spezielle Quotienten eines Polynomrings in mehreren Variablen besonders schnelle Multiplikationsalgorithmen haben) und damit den (vermutlich) schnellstmöglichen Multiplikationsalgorithmus. (Die Vermutung, dass es keinen Algorithmus in weniger als O(n logn) Schritten geben kann, ist allerdings noch unbewiesen.)

David Harvey, Joris van der Hoeven: Integer multiplication in time O(n logn)

Kommentare (22)

  1. #1 schlappohr
    27. März 2019

    Ich vermute, die Problemgröße n ist die Anzahl der Ziffern (Bits) der Operanden?
    Wäre aber mal interessant zu wissen, ab welchem n der neue Algorithmus schneller ist als der klassische Schulagorithmus oder die Karatzuba-Multiplikation. Zwar gilt schon für kleine n, dass nlogn kleiner als n² ist, aber die Konstanten, die in der O-Notation stecken, relativieren das ganze vermutlich ein wenig. Es würde mich sehr wundern, wenn eine FFT gefolgt von einer Polynommultiplikation gefolgt von einer iFFT schon bei kleinen Zahlen effizienter ist als die klassischen Algorithmen.

  2. #2 tomtoo
    27. März 2019

    Wie ist da schneller zu verstehen?(Ab wann)
    Schliese mich da @Schlappohrs Frage an.

  3. #3 Karl Mistelberger
    mistelberger.net
    27. März 2019

    Schon zu Strassens Algorithmus wird angemerkt:

    This is fun, but let’s look at practicalities: If you estimate how large N has to be before the difference between exponent 3 and exponent log2 7 = 2.807 is substantial enough to outweigh the bookkeeping overhead, arising from the complicated nature of the recursive Strassen algorithm, you will find that LU decomposition is in no immediate danger of becoming obsolete.

    ftp://tech.obihiro.ac.jp/suzuki/Numerical_Recipes_in_Fortran.pdf

    Der Punkt ist: Gibt es was Schnelleres als LU decomposition? Wie schnell läuft das auf dem SuperMUC-NG ?

    https://media.ccc.de/v/35c3-9703-supermuc-ng

  4. #4 schlappohr
    27. März 2019

    Wie schnell läuft das auf dem SuperMUC-NG ?

    Das ist nochmal eine ganz andere Frage. Dabei gehts um Parallelisierbarkeit, Umsetzbarkeit auf der Maschinenarchitektur, Cache-Effizienz (Lokalitätsverhalten), also sehr technische Aspekte. Aber interessant wäre mal, ab welcher Problemgröße die Anzahl der Elementaroperationen kleiner ist als bei den herkömmlichen Methoden, unabhängig von der Maschine (das meinte ich mit “schneller” in #1, war missverständlich ausgedrückt)

  5. #5 Philipp
    27. März 2019

    @Karl Mistelberger:
    Der Strassen-Algorithmus zur Multiplikation von Matrizen ist nicht das selbe wie der Schönhage-Strassen-Algorithmus zur Multiplikation von ganzen Zahlen. Und an der zitierten Stelle geht es ja noch nicht einmal um den Strassen-Algorithmus selbst, sondern um ein Verfahren zur Matrixinversion, das man aus Strassen erhält.

    Meines Wissens nach verwendet man zur numerischen Lösung wirklich großer linearer Gleichungssysteme auch eher iterative Verfahren, insbesondere wenn die Matrix sparse ist.

  6. #6 rolak
    28. März 2019

    ab welchem n der neue Algorithmus schneller ist

    Schon der alte schafft das erstaunlich flott, schlappohr:

    In practice the Schönhage–Strassen algorithm starts to outperform older methods such as Karatsuba and Toom–Cook multiplication for numbers beyond 2^(2^15) to 2^(2^17) (10,000 to 40,000 decimal) digits.

  7. #7 Horst
    28. März 2019

    Mir möge Jemand erläutern, was hier mit “Oparation” gemeint ist. Eine komplexe Funktion ist auf Maschinenebene mitnichten eine Operation.

    Was könnte in diesem Zusammenhang zur “Multiplikation von Hand” schneller sein als Shift und Addition bez. der Anzahl der Operationen? Als Compilerbauer kann ich bspw. problemlos binär rechnen wenns denn sein muss.

  8. #8 bote19
    28. März 2019

    Die Anzahl von Rechenoperationen ist nicht allein ausschlaggebend für die Geschwindigkeit. Die hängt auch ab von der Struktur der elektronischen Bausteine und wie die Zahlen codiert werden. Bislang waren ja mehrfach Additionen oft schneller als Multiplikationen.
    Auf jeden Fall ein sehr interessantes Thema.

  9. #9 bote19
    28. März 2019

    Horst
    bei Operationen sind hoffentlich nur binäre Operationen gemeint.

  10. #10 alex
    28. März 2019

    @Horst:
    Als Elementaroperationen wird man hier z.B. die Multiplikation oder Addition zweier Ziffern oder die Verschiebung der Zahl verstehen.

    Dass die Schulmethode (die im Prinzip darauf hinausläuft, jede Ziffer des ersten Faktors mit jeder Ziffer des zweiten Faktors zu multiplizieren, die Ergebnisse entsprechend zu verschieben, und dann zu addieren) für große Zahlen nicht optimal ist, kann man schon an sehr viel einfacheren Algorithmen sehen. Z.B. an dem von Karatsuba.

  11. #11 Dr. Webbaer
    29. März 2019

    Der Schreiber dieser Zeilen hat sich schon vor vielen Jahren gewundert, wenn mit Programmiersprachen zu tun habend, dass es neben der herkömmlichen Verwendung von Rechenoperatoren noch das Angebot gab für die Multiplikation eine besondere Funktion zu verwenden, die schneller war, wie angegeben worden ist.
    Wobei dies, lol, – ‘Die neue Arbeit von Harvey und v.d.Hoefen findet nun die (vermutlich) bestmögliche Kodierung ganzer Zahlen durch Polynome (in mehreren Variablen – der Punkt ist, dass spezielle Quotienten eines Polynomrings in mehreren Variablen besonders schnelle Multiplikationsalgorithmen haben) und damit den (vermutlich) schnellstmöglichen Multiplikationsalgorithmus.’ – sich cooler anhört, aber ähnlich meint.

    Die Multiplikation bleibt sozusagen eine Kunst,
    MFG
    Dr. Webbaer

  12. #12 rolak
    29. März 2019

    ? was hier mit “Oparation” gemeint ist

    Dasselbe wie sonst auch, Horst, ein Synonym wäre ‘Seniorenteller’.

    Im übrigen ist auch eine ordinäre, kurzstellige Addition im Binärsystem auf Maschinenebene mitnichten eine Operation (im Sinne von ‘eine Aktion und fertig’), sondern ein Kuddelmuddel von Datentransporten und ziemlich komplexen Vergatterungen in mehreren Takten. Und ab einer bestimmten Bitzahl kann sie nicht einmal mehr auf Maschinensprachen-Ebene in diesem Sinne ‘Operation’ genannt werden.

    Doch selbstverständlich ist das alles nur eine Kontextfrage, sagt ua MAC.

  13. #13 Horst
    4. April 2019

    @rolak Die Definition einer Operation kann aus meiner Sicht in diesem Zusammenhang nur die kleinstmögliche “Befehlsausführung” auf Anwenderschicht sein, keine Konstruktive. Auf Maschinenebene wäre das der jeweilig verfügbare und definierte Satz an Maschinenbefehlen, beim neuronalen Netz der abstrahierte “Rechenschritt”. Andernfalls käme man im Falle des biologischen, neuronalen Netzes irgendwann bei der elektrochemischen reaktion auf Zellebene an.

    Insofern ist meiner Meinung nach die proklamierte ” schnellste Multiplikation seit 4000 Jahren” nonsense, aber Mathematiker leben ja gerne in ihrer ganz eigenen Welt 😉

  14. #14 rolak
    5. April 2019

    Die Definition einer Operation kann aus meiner Sicht

    Solange diese Definition nicht einen exklusiven Aspekt Deiner Eigenwelt behandelt, Horst, ist ihr Deine Sichtweise völlig schnurz. Sozusagen ein FlOp-Flop.

    Andernfalls käme man

    Macht nix, kannst Dir ja mal überlegen, was bei den Operationen alles so abgeht, wieviele Prozesse auf wievielen Prozessoren beteiligt sein können etc pp ad lib

  15. #15 Horst
    5. April 2019

    “meine Eigenwelt” ist die maschinennahe Programmierung von Entwicklungswerkzeugen und Bibliotheken, insofern muss ich nicht nur überlegen, sondern das bauen womit auch unsere Mathematiker arbeiten. Das Anwendern und auch Entwicklern auf höherer Abstraktionsebene völlig egal ist wie das technisch umgesetzt wird, ist bei solchen Definitionen und den Reaktionen aufs Hinterfragen durchaus offensichtlich, aber auch nicht weiter schlimm.

    das einfache Schulbeispiel “multipliziere 226345654665466 mit 2” sind aus klassischet mathematischer Sicht n “Operationen”, binär jedoch nur Eine. Du kannst dir ja mal überlegen weswegen das selbst auf einem Blatt Papier nur eine ” Operation” ist. 😉

  16. #16 alex
    5. April 2019

    @Horst:
    Du verstehst aber schon, dass es hier um Multiplikationen geht, bei denen beide Operanden so große Zahlen sind, dass sie bei weitem nicht in ein Maschinenwort passen? Die GMP verwendet beispielsweise den Schönhage-Strassen-Algorithmus (je nach Hardware-Architektur) für Zahlen ab mehreren zehntausend bis mehr als hunderttausend Dezimalstellen. Und für diesen neuen Algorithmus würde ich erwarten, dass er erst bei noch größerem n schneller als Schönhage-Strassen ist.

  17. #17 live22 ios
    Switzerland, Nassen
    5. April 2019

    American Greetings cards — Buy 3 and get $3 began to allow Extra Usd.

    It’s hard to know when you find yourself going to win or
    general. Those based on luck and people based on skills.c https://www.lianlaov.com/home.php?mod=space&uid=157199&do=profile&from=space

  18. #18 Horst
    9. April 2019

    @alex die anzahl der stellen ist nur durch den Speicher begrenzt, also nicht von belang und gerade bei großen zahlen stellt schönhage-strassen mit modernen prozessoren kein vorteil mehr dar. selbst die klassische uralt-version unter der Annahme, dass kein Maschinenbefehl “mul” vorhanden ist, dürfte mittels betrachtung der 2er-Faktoren, also einmaliger Shift um x Stellen und anschließender addition hier ziemlich schnell im Sinne des Zeitfaktors und Anzahl der Operationen sein. Gerade bei großen ganzen Zahlen ist das ziemlich “schnell”.

  19. #19 alex
    9. April 2019

    @Horst:
    Soso. Für diese steile Behauptung hast du sicherlich einen Beleg, nicht wahr? Und du kannst dann sicherlich auch erklären, warum beispielsweise die GMP für ausreichend große Zahlen Schönhage-Strassen verwendet. Und du kannst auch sicherlich erklären, warum ein O(n²)-Algorithmus für großes n schneller sein soll als ein O(n log n log log n)-Algorithmus.

    Die Details der Implementierung sowohl was Hardware als auch Software angeht, haben nur einen Einfluss auf die Konstanten in den Landau-Symbolen. D.h. ab welchem n Schönhage-Strassen schneller ist. Dass O(n log n log log n) für ausreichend großes n schneller ist als O(n²) ist wahr vollkommen unabhängig von der Implementierung. Und genau in diesem Sinn ist die Überschrift des Artikels gemeint.

    Es wäre schön, wenn du keine wilden Behauptungen zu Themen aufstellen würdest, von denen du offensichtlich keine Ahnung hast.

  20. #20 Horst
    10. April 2019

    @alex In meinem ursprünglichen post habe ich eine Frage gestellt die unmissverständlich darlegt, dass diese Art der mathematischen Betrachtung nicht mein Fachgebiet ist. Meine Betrachtungen sind rein maschinennah und ich spreche hier offensichtlich mit jemandem der – wie sagtest du so schön “davon offensichtlich keine Ahnung” hat. Wenn das Stellen einer Frage zur Klärung des Kontextes zu solchen Antworten führt, ist eine weitere Diskussion obsolet.

  21. #21 alex
    10. April 2019

    @Horst:

    In meinem ursprünglichen post habe ich eine Frage gestellt die unmissverständlich darlegt, dass diese Art der mathematischen Betrachtung nicht mein Fachgebiet ist.

    Diese Frage hatte ich bereits in meinem Kommentar #10 beantwortet.

    Wenn das Stellen einer Frage zur Klärung des Kontextes zu solchen Antworten führt, ist eine weitere Diskussion obsolet.

    Du hast ja nicht nur einfach eine Frage gestellt. Der zweite Absatz in deinem Kommentar #13 oder dein Kommentar #18 gehen weit über das Stellen einer Frage hinaus. Dort stellst du falsche Tatsachenbehauptungen auf.

    Noch einmal: Wie “maschinennah” man das Problem betrachtet, ist irrelevant für folgende einfache Tatsache: Wenn du zwei Zahlen zu multiplizieren hast, die beide hunderttausende Dezimalstellen haben, dann das Standardverfahren nicht optimal. Das ist einfach ein Fakt. Da kannst du so viele Leute beleidigen wie du willst.

    Ich habe dir auch bereits den Namen eines Algorithmus genannt, bei dem es ohne viel mathematisches Vorwissen möglich ist nachzuvollziehen, dass er für große Zahlen schneller ist als der Standardalgorithmus. Und auch dort hast du dich entschieden, das einfach zu ignorieren.