Implementazione di Bignum che ha un'aggiunta efficiente di piccoli interi

Question

Ho utilizzato i bignum nativi di python per un algoritmo e ho deciso di provare e accelerarlo convertendolo in C++. Quando ho usato long long, il C++ era circa 100 volte più veloce del python, ma quando ho usato i binding GMP in C++, era solo 10 volte più veloce del python (per gli stessi casi che si adattavano a lunghi long).

Esiste un'implementazione migliore per eseguire un numero elevato di piccole aggiunte? Ad esempio, abbiamo un grande numero N aggiungeremo un po 'di +1, +21, +1, ecc. E ogni tanto un altro grande numero M?

Answer 1

Il GMP biblioteca stessa ha un fast short integer add to MPZ routine

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

Io non so se gmpy utilizza tale, ma se lo fa provare ad aggiungere un normale int pitone a un mpz vs l'aggiunta di un mpz per mpz e vedere se è più veloce

Modifica

ho provato un po 'di benchmarking e l'ho trovato non fa alcuna differenza

$ 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 

Quindi credo gmpy non usa mpz_add_ui come ho davvero aspetterei che, per essere molto più veloce.

Answer 2

Hai eseguito il profiling? Di Python e C++ intere applicazioni. In modo che tu sappia che hai davvero bisogno di quella velocità aggiuntiva.

Prova Python 3k ora ha implementato interi di lunghezza qualsiasi!

Answer 3

(Nota:. Io aiuto mantenere GMPY e ho implementato un bel paio di ottimizzazioni nella versione più recente)

GMPY v1.11 fa uso mpz_add_ui quando si aggiunge un piccolo numero a un MPZ. Anche la versione più recente di GMPY è circa il 25% più veloce rispetto alle versioni precedenti quando si lavora con numeri piccoli.

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 

Poiché è più veloce per convertire un int Python per un lungo e chiamare mpz_add_ui di convertire un int Python per un mpz, v'è un vantaggio prestazioni moderate. Non sarei sorpreso se c'è una penalità di prestazioni 10 volte per chiamare le funzioni GMP rispetto alle operazioni native su un lungo lungo.

Puoi accumulare molti dei piccoli numeri in uno lungo e aggiungerli contemporaneamente al tuo numero elevato?