Bignum-Implementierung mit effizienter Addition kleiner Ganzzahlen

Question

Ich habe Pythons native Bignums für einen Algorithmus verwendet und beschlossen, es zu beschleunigen, indem ich es in C++ umwandelte. Wenn ich lange Longs verwendete, war das C++ etwa 100x schneller als das Python, aber wenn ich GMP-Bindings in C++ verwendete, war es nur 10x schneller als das Python (für die gleichen Fälle, die in Longs passen).

Gibt es eine bessere Bignum-Implementierung für eine große Anzahl von kleinen Zusätzen? Zum Beispiel haben wir eine große Zahl N, wir fügen viele kleine +1, +21, +1, usw. hinzu und fügen hin und wieder eine weitere große Zahl M hinzu?

Answer 1

Die GMP-Bibliothek selbst hat eine fast short integer add to MPZ routine

void mpz_add_ui (mpz_t rop, mpz_t op1, unsigned long int op2) 

Ich weiß nicht, ob gmpy nutzt das, aber wenn es nicht versuchen, ein normales Python int zu einem mpz Hinzufügen vs ein mpz zu mpz hinzufügen und sehen, ob es ist schneller.

bearbeiten

habe ich versucht, ein bisschen Benchmarking und fand es keinen Unterschied macht

$ python -m timeit -c 'from gmpy import mpz 
> a=mpz(10**1000)' 'a+1' 
100000 loops, best of 3: 5.4 usec per loop 

$ python -m timeit -c 'from gmpy import mpz 
a=mpz(10**1000); b=mpz(1)' 'a+b' 
100000 loops, best of 3: 5.5 usec per loop 

Also ich denke, gmpy nicht mpz_add_ui nicht benutzen, wie ich zu sein, dass wirklich erwarten viel schneller.

Answer 2

Haben Sie Profile erstellt? Von Python und C++ ganze Anwendungen. Damit Sie wissen, dass Sie diese zusätzliche Geschwindigkeit wirklich brauchen.

Probieren Sie Python 3k es jetzt haben Any-Length-Ganzzahlen implementiert!

Answer 3

. (Anmerkung: Ich helfe GMPY zu halten und ich habe schon einige Optimierungen in der neuesten Version implementiert)

GMPY v1.11 mpz_add_ui nicht verwendet, wenn eine kleine Anzahl an einem mpz hinzufügen. Die neueste Version von GMPY ist auch um 25% schneller als frühere Versionen, wenn mit kleinen Zahlen gearbeitet wird.

With GMPY 1.04 
$ py26 -mtimeit -s "import gmpy;a=gmpy.mpz(10**1000)" "a+1" 
10000000 loops, best of 3: 0.18 usec per loop 
$ py26 -mtimeit -s "import gmpy;a=gmpy.mpz(10**1000);b=gmpy.mpz(1)" "a+b" 
10000000 loops, best of 3: 0.153 usec per loop 

With GMPY 1.11 
$ py26 -mtimeit -s "import gmpy;a=gmpy.mpz(10**1000)" "a+1" 
10000000 loops, best of 3: 0.127 usec per loop 
$ py26 -mtimeit -s "import gmpy;a=gmpy.mpz(10**1000);b=gmpy.mpz(1)" "a+b" 
10000000 loops, best of 3: 0.148 usec per loop 

Da es schneller ist, eine Python int auf einen lange zu konvertieren und mpz_add_ui zu nennen als eine Python int zu einem mpz zu konvertieren, gibt es einen moderaten Leistungsvorteil. Ich wäre nicht überrascht, wenn es eine 10-fache Leistungseinbuße für den Aufruf der GMP-Funktionen gegenüber nativen Operationen gibt.

Können Sie mehrere der kleinen Zahlen zu einem langen zusammenfassen und sie zu Ihrer großen Zahl hinzufügen?