Python lange Multiplikation

Question

Ich bin in der Notwendigkeit eines Algorithmus schneller als die aktuelle normale Pythons lange Multiplikation.

Ich habe versucht, eine anständige Karatsuba Implementierung zu finden, aber ich kann es nicht.

def main():
    a=long(raw_input())
    if(a<0):
        a=a*-1
        a=((a*(a+1)/2)-1)
        print(-a)
    else:
        a=(a*(a+1))/2
        print(a)
main()

Wie Sie sehen, es ist nichts kompliziert, nur wenige Multiplikationen. Aber es hat Zahlen zu handhaben mit bis zu 100.000 Stellen in unter 2,5 Sekunden.

ich einige Schnipsel einer Funktion möchte oder einfach nur einen Link zu einem gewissen Implementierung einer schnelleren Multiplikationsfunktion, oder alles, was hilft.

Answer 1

könnten Sie haben einen Blick auf die Umsetzung des DecInt Modul (reine Python-Version ist verfügbar (Toom-Cook), obwohl die schnellsten sein wird es wohl bei der Verwendung von gmpy ).

Answer 2

Ich bin der Autor des DecInt (Dezimal-Integer) Bibliothek so werde ich ein paar Anmerkungen machen.

Die DecInt Bibliothek wurde speziell entwickelt, um mit sehr großen Zahlen zu arbeiten, die in dem Dezimalformat konvertiert werden benötigt. Das Problem mit zu Dezimal-Format zu konvertieren ist, dass die meisten beliebige Genauigkeit Bibliotheken speichern Werte in binär. Dies ist schnellste und effizienteste für Speicher verwendet wird, jedoch von binärer Umwandlung in Dezimalzahlen in der Regel langsam. Python binäre Umwandlung in Dezimalzahlen verwendet ein O (n ^ 2) -Algorithmus und langsam wird sehr schnell.

DecInt verwendet eine große Dezimalwurzel (in der Regel 10 ^ 250) und speichert die sehr große Zahl in Blöcken von 250 Stellen. Konvertieren eine sehr große Anzahl an Dezimalformat läuft nun in O (n).

Naive oder Grundschule, Multiplikation hat eine Laufzeit von O (n ^ 2). Python Karatsuba-Multiplikation verwendet, die Zeit von O hat laufen (n ^ 1,585). DecInt verwendet eine Kombination von Karatsuba, Toom-Cook und Nussbaumer Faltung eine Laufzeit von O (n * ln (n)) zu erhalten.

Auch wenn DecInt viel höheren Aufwand hat, die Kombination von O (n * ln (n)) Multiplikation und O (n) Umwandlung wird schließlich schneller als Python O (n ^ 1,585) Multiplikation und O (n ^ 2) Umwandlung.

Da die meisten Berechnungen nicht jedes Ergebnis benötigen, um im Dezimalformat angezeigt werden, fast jeden beliebige Genauigkeit Bibliothek verwendet binäre da, dass die Berechnungen erleichtern. DecInt zielt auf eine sehr kleine Nische. Für groß genug Zahlen werden DecInt schneller für Multiplikation und Division als nativer Python. Aber wenn Sie nach reiner Leistung sind, eine Bibliothek wie GMPY die schnellste sein.

Ich bin froh, dass Sie DecInt hilfreich.

Answer 3

15,9 ms auf meinem langsamen Notebook. Es ist der Druck, den Sie verlangsamt. Konvertieren in Binärzahlen in Dezimalzahlen ist ziemlich langsam, was ein notwendiger Schritt ist es auszudrucken. Wenn Sie die Nummer ausgeben müssen, sollten Sie die DecInt ChristopheD versuchen bereits erwähnt.

DecInt wird langsamer sein, die mehrfach zu tun, aber der Druck viel schneller machen

In [34]: a=2**333000

In [35]: len(str(a))
Out[35]: 100243

In [36]: b=2**333001

In [37]: len(str(b))
Out[37]: 100244

In [38]: timeit c=a*b
10 loops, best of 3: 15.9 ms per loop

Hier ist ein Beispiel mit einer leicht modifizierten Version des Codes. Beachten Sie, dass eine 100.000 Ziffernfolge auf eine lange Umwandlung nimmt bereits ~ 1sec auf diesem Computer

In [1]: def f(a):
   ...:     if(a<0):
   ...:         a=a*-1
   ...:         a=((a*(a+1)/2)-1)
   ...:     else:
   ...:         a=(a*(a+1))/2
   ...:     return a
   ...: 

In [2]: a=3**200000

In [3]: len(str(a))
Out[3]: 95425

In [4]: timeit f(a)
10 loops, best of 3: 417 ms per loop

Answer 4

Ich schlage vor, Sie bekommen die Sage Mathe-Tool , die jedes Python Mathe-Tool je gemacht gewalzte fast hat in einem Paket. Sehen Sie, wenn es ein schönes schnelles beliebige Genauigkeit Mathe-Tool in Sage, die Ihre Bedürfnisse entsprechen.