Nach 4000 Jahren: Die schnellste Multiplikation der Welt

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.

22. #22 Thilo

    15. April 2019

    https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/