Was ist der schnellste Algorithmus zur Multiplikation von zwei n-stelligen Zahlen?

21

Ich möchte wissen, welcher Algorithmus für die Multiplikation von zwei n-stelligen Zahlen am schnellsten ist. Platzkomplexität kann hier gelockert werden!

Andy
quelle
1
Interessieren Sie sich für die theoretische Frage oder für die praktische Frage?
Yuval Filmus
Beides, aber eher praktisch!
Andy
1
Für die praktische Frage empfehle ich GMP. Wenn Sie neugierig sind, was sie verwenden, schauen Sie sich die Dokumentation oder den Quellcode an.
Yuval Filmus
Niemand weiß. Wir haben es noch nicht gefunden.
JeffE

Antworten:

22

Fürers Algorithmus von Martin Fürer hat ab sofort eine Zeitkomplexität von die Fouriertransformationen über komplexe Zahlen verwendet. Sein Algorithmus basiert auf Schönhages und Straßens Algorithmus, der eine zeitliche Komplexität vonnlog(n)2Θ(log(n))Θ(nlog(n)log(log(n)))

Andere Algorithmen, die schneller sind als der Multiplikationsalgorithmus der Grundschule, sind die Karatsuba-Multiplikation mit einer zeitlichen Komplexität von ≈ O (n ^ {1,585}) und der Toom 3-Algorithmus mit einer zeitlichen Komplexität von Θ (n ^ {1,465})O ( n 1,585 ) Θ ( n 1,465 )O(nlog23)O(n1.585)Θ(n1.465)

Beachten Sie, dass dies die schnellen Algorithmen sind. Das Finden des schnellsten Algorithmus für die Multiplikation ist ein offenes Problem in der Informatik.

Verweise :

  1. Fürers Algorithmus
  2. FFT-basierte Multiplikation großer Zahlen
  3. Schnelle Fourier-Transformation
  4. Toom-Cook-Vermehrung
  5. Schönhage-Strassen-Algorithmus
  6. Karatsuba-Algorithmus
avi
quelle
Beachten Sie die jüngste Veröffentlichung von D. Harvey und J. van der Hoeven (März 2019), in der ein Algorithmus mit -Komplexität beschrieben wird. O(nlnn)
Hardmath
9

Beachten Sie, dass die von avi aufgelisteten FFT-Algorithmen eine große Konstante hinzufügen, was sie für Zahlen unter Tausenden + Bits unpraktisch macht.

Neben dieser Liste gibt es noch einige andere interessante Algorithmen und offene Fragen:

  • Lineare Zeitmultiplikation in einem RAM-Modell (mit Vorberechnung)
  • Die Multiplikation mit einer Konstanten ist sublinear( PDF ) - dies bedeutet eine sublineare Anzahl von Additionen, die für eine Bitkomplexität von insgesamt. Dies entspricht im Wesentlichen einer langen Multiplikation (bei der Sie basierend auf der Zahl vons in der unteren Zahlverschieben / hinzufügen), die, jedoch mit einembeschleunigen.1O(n2)O(logn)O(n2logn)1O(n2)O(logn)
  • Rückstandsnummernsystem und andere Darstellungen von Zahlen; Die Multiplikation ist nahezu linear. Der Nachteil ist, dass die Multiplikation modular ist und {Überlauferkennung, Parität, Größenvergleich} alle so schwer oder fast so schwer wie das Zurückkonvertieren der Zahl in eine binäre oder ähnliche Darstellung und das Ausführen des herkömmlichen Vergleichs sind. Diese Umrechnung ist mindestens so schlecht wie die herkömmliche Multiplikation (derzeit AFAIK).
    • Andere Darstellungen:
      • [ Logarithmische Darstellung ]: Die Multiplikation ist eine Addition der logarithmischen Darstellung. Beispiel:
        16×32=2log216+log232=24+5=29
        • Nachteil ist, dass die Konvertierung in und aus der logarithmischen Darstellung so schwierig wie die Multiplikation oder schwieriger sein kann. Die Darstellung kann auch gebrochen / irrational / ungefähr usw. sein. Andere Operationen (Addition?) Sind wahrscheinlich schwieriger.
      • Kanonische Darstellung : Stellen Sie die Zahlen als Exponenten der Primfaktorisierung dar. Die Multiplikation ist die Addition der Exponenten. Beispiel:
        36×48=3251×223141=22324151
      • Nachteil ist, erfordert Faktoren oder Faktorisierung, ein viel schwierigeres Problem als die Multiplikation. Andere Operationen wie das Hinzufügen sind wahrscheinlich sehr schwierig.
Realz Slaw
quelle
1
Ich glaube, dass ein auf Residuen / Chinese Remainder Theorem basierender Ansatz mit den richtigen Modulen zu einer Beschleunigung gegenüber der traditionellen Multiplikation führen kann , selbst wenn die Umrechnung rückgängig gemacht wird. Irgendwann war dies in Kapitel 4 von TAOCP, zumindest als Fußnote. (Es kommt immer noch nicht in die Nähe der FFT-basierten Methoden, aber es ist eine interessante historische Anmerkung)
Steven Stadnicki
@StevenStadnicki oh cool, das muss ich mir dann ansehen; Kennst du zufällig die Komplexität?
Realz Slaw