Wie man große Zahlen schneller multipliziert?

Question

Ich experimentierte mit der Multiplikation großer Zahlen in Python. Für meinen Zweck habe ich versucht zu bewerten.

Jetzt läuft meine Frage darauf hinaus, wie man Zahlen in Python schneller multipliziert. ist es schneller mit Float zu tun? Die Antwort scheint nein. Nehmen Sie ein einfacheres Beispiel mit

n * (n + 1)/2

Meine Idee war, dass der folgende Code ist schneller

product = 1 
if n % 2 == 0: 
    product *= n/2 
    product *= n 
else: 
    product *= (n+1)/2 
    product *= n 
return product 

Warum sollte dies schneller sein? Nun, Sie müssten die Nummer n*(n+1) nicht durch zwei teilen. Allerdings verschwendet man eine Rechnung mit der Nummer modulo2. Vielleicht ist try exception schneller?

Also meine Frage läuft auf. Wie berechnet man das Produkt und die Teilung sehr großer Zahlen in Python? Hier ist mein Arbeitscode. Keine speziellen Geschwindigkeitsverbesserungen für diesen Code erforderlich. Aber die breitere Frage, wie man mit der Division und Multiplikation großer Zahlen umgehen soll. Meine Nummer ist um 10^(10^6) atm.

def spiral_sum_fast(num): 
    rem = num % 6 
    if rem % 2 == 0: 
     raise Exception("The sidelength must be a odd number") 
    odd = 1 + num/2 
    odd_squared = 2 * odd**2 

    if rem % 3 == 0: 
     temp = odd/3 
     temp *= 8 * odd_squared + 14 
    else: 
     temp = (4 * odd_squared + 7)/3 
     temp *= 2 * odd 
    return temp - 3 * odd_squared - 3 


if __name__ == '__main__': 

    k = 10**(10**6) + 1 
    spiral_sum_fast(k) 

Answer 1

Im Allgemeinen sollten Sie spezialisierte Bibliotheken für spezialisierte Jobs. In Ihrem Fall erfordert dies möglicherweise große Zahlen und optimale Geschwindigkeit. Werfen Sie einen Blick auf diese blog, die sich mit großen Zahlen beschäftigt und Geschwindigkeitsvergleiche zwischen reinem Python und dem GNU Multiple Precision Arithmetic Library von Python macht, was zu einer großen Leistungsverbesserung führt.

Answer 2

Der Kern Ihrer Frage scheint eine Variation von "wie schnell sind numerische Operationen in Python?" und die Antwort darauf hängt davon ab, an welcher Art von Nummer Sie arbeiten und welche Art von Computer Sie verwenden.

Es gibt vier Arten von Zahlen in Python: https://docs.python.org/2/library/stdtypes.html#numeric-types-int-float-long-complex

Die Frage, welche Art von Maschine, die Sie verwenden, beeinflusst, ob oder nicht Gleitkommamathematik schnell oder langsam sein wird. In den meisten Fällen wird die gesamte numerische Arbeit von der Langsamkeit des Arbeitsspeichers überlagert, aber es gibt einige Fälle, in denen der von Ihnen eingestellte Zahlensatz und die Anweisungen alle in den Cache passen und nicht durch die Speicherzugriffszeit begrenzt sind. Die nächste Frage ist, da ein "int" normalerweise ein 32-Bit C lang in Python ist, und ein "long" größer ist als das, sind Ihre Ints wirklich groß genug, um die 4B Barriere zu überschreiten in lange? Aus dem Sound davon, ja, lassen Sie uns die Implementierung des Python-Longobjects betrachten:

Also, es ist nur ein Haufen Int Mults. Zugegeben, es ist eine lineare Kette von ihnen, also, wie lang ist diese Kette?

>>> k = 10**(10**6) + 1 
>>> k.bit_length()/32 
103810 

Ok, die int-Kette ist länger als die wenige hundert Zyklen jeder Treffer in dem Hauptspeicher erfolgt, so dass Sie den Punkt treffen könnten, wo man tatsächlich CPU gebunden ist ...

bis man sich anschaut, wie groß diese Nummer ist ist eigentlich.

>>> k.bit_length()/(8*1024) 
405 

405KB? Wie groß sind Caches? http://www.intel.com/content/www/us/en/processors/core/6th-gen-core-family-mobile-u-y-processor-lines-datasheet-vol-1.html

Also, L1, 64B? L2 ist wahrscheinlich 256KB? L3 ist derjenige, der wahrscheinlich um 4M ist. Selbst dann - wie viele dieser 405KB-Nummern werden während des Prozesses aufbewahrt? Wie viel Speicher benötigt Python? Überfallen wir den Cache? Wie teuer ist das?

Approximate cost to access various caches and main memory?

Das ist, soweit ich jetzt in dieses Loch bin zu graben, sondern Zeichen auf Langsamkeit aus dem Cache Erschöpfung zeigen. Du benutzt große Zahlen. Big ist mehr als ein mathematisches Konzept, es stößt gegen die physische Realität der Erinnerung an. Das verbleibende Profiling von "wie viele Temp-Kopien bleibt Python herum?" und "wie benutzt der Dolmetscher den Rest der Erinnerung?" sind interessante Fragen und über den Rahmen dieser Antwort hinaus.

Answer 3

Zunächst einmal wird 4 * ungerade^2 + 7 wird immer 2 mod 3. So müssen Sie nicht überprüfen.

Aber Sie möchten die Operationen sowieso nicht neu ordnen. Überlegen Sie, was mit der Ganzzahlarithmetik von 4 * 5/3 vs 4/3 * 5 passiert. Das erste Ergebnis ist 6. Während das 2. Ergebnis 5 ist. Bei größeren Zahlen würden Sie sogar noch mehr Informationen verlieren, wenn Sie die Division in der Reihenfolge der Operationen an eine frühere Position verschieben.

Ein weiterer Punkt: Sie wollen nie x**2 tun. ** verwendet C pow(), so dass es ein Gleitkommaergebnis haben wird. Verwenden Sie stattdessen einfach x * x. Es wird schneller und genauer sein.

Wie für das Beispiel von n*(n+1)/2 wird n*(n+1) immer teilbar sein durch 2. Und alles, was Sie tun, ist eine große Anzahl von 1-Bit-Verschiebung nach rechts und Sie wissen, dass das Bit Sie verlieren 0 ist.

Es scheint, als ob Sie im Allgemeinen besorgt sind, große Zahlen durch kleine zu teilen. Aber (wie im ersten Beispiel, das ich gab), wenn Sie die Division zu früh machen, verlieren Sie Informationen und erhalten weniger genaue Antworten. Die Berechnung wird auch nicht schneller sein. Sie können Tricks wie diese benötigen, wenn Sie große Zahlen durch große Zahlen teilen, aber wenn Sie große Zahlen durch kleine Zahlen teilen (und Sie Ganzzahlarithmetik verwenden), wird das Ergebnis nur ein paar Bit kürzer sein als die große Zahl, mit der Sie begonnen haben . Es wird weder schneller noch genauer sein, "früh zu teilen" oder Gleitkommaarithmetik zu verwenden.