views:

248

answers:

3

I have been using python's native bignums for an algorithm and decided to try and speed it up by converting it to C++. When I used long longs, the C++ was about 100x faster than the python, but when I used GMP bindings in C++, it was only 10x faster than the python (for the same cases that fit in long longs).

Is there a better bignum implementation for doing a large number of small additions? For example, we have a big number N we'll be adding a lot of little +1, +21, +1, etc. and every once and a while adds another big number M?

+2  A: 

The GMP library itself has a fast short integer add to MPZ routine

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

I don't know whether gmpy uses that, but if it does try adding a normal python int to an mpz vs adding an mpz to mpz and see if it is quicker.

Edit

I tried a bit of benchmarking and found it doesn't make any difference

$ 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

So I guess gmpy doesn't use mpz_add_ui as I really would expect that to be a lot quicker.

Nick Craig-Wood
Interesting. I'm using the C++ overloading of arithmetic operations, perhaps these C++ bindings are also not utilizing this quick method. I'll do some tests tomorrow. Thanks!
sligocki
A: 

Did you do profiling ? Of Python and C++ whole applications. So that you know that you really need that additional speed.

Try Python 3k it now have any-length integers implemented!

przemo_li
This slowdown was for the whole program when the only change was from long longs to GMP MPZ. Thanks.
sligocki
What do you mean by "Python 3k now has any-length integers"? Python has had arbitrary-length integers since at least version 2.5 (and probably way before).
EOL
Now all ints all any-length
przemo_li
A: 

(Note: I help maintain GMPY and I've implemented quite a few optimizations in the most recent release.)

GMPY v1.11 does use mpz_add_ui when adding a small number to an mpz. The newest version of GMPY is also about 25% faster than prior versions when working with small numbers.

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

Since it is quicker to convert a Python int to a long and call mpz_add_ui than to convert a Python int to an mpz, there is a moderate performance advantage. I wouldn't be surprised if there is a 10x performance penalty for calling the GMP functions vs. native operations on a long long.

Can you accumulate several of the small numbers into one long long and add them at one time to your large number?

casevh
Yeah, I have been considering writing my own class to accumulate the small numbers and add them to the big one infrequently.Thanks for the note about GMPY 1.11.
sligocki