小さな整数を効率的に追加するBignumの実装

Question

私はアルゴリズムのためにpythonのネイティブbignumを使用していましたが、それをC++に変換して速度を上げようと決めました。ロングロングを使用した場合、C++はPythonより約100倍高速でしたが、C++でGMPバインディングを使用した場合、Pythonよりも10倍高速でした（ロングロングの場合と同じです）。

多数の小さな追加を行うためのより良いビッグサム実装がありますか？たとえば、私たちは大きな数字を持っています。私は+1、+21、+ 1などを少し追加しています。

Answer 1

GMPライブラリ自体は、私はgmpyがあることを使用するかどうかわかりませんが、それはMPZにMPZを追加する対MPZに、通常のPythonのint型を追加してみてくださいし、かどうかを確認しなければfast short integer add to MPZ routine

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

を持っていますそれはより速いです。

編集

私は、ベンチマークのビットを試してみましたが、それはだから私は、私は本当にそれがあることを期待するようgmpyがmpz_add_uiを使用していないと思うに違い

$ 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 

をしないましたずいぶん早く。

Answer 2

プロファイリングしましたか？ PythonおよびC++の全体アプリケーション。あなたは本当にその速度がさらに必要であることを知っています。

Python 3kを試してみてください。これで、任意の長さの整数が実装されました！

Answer 3

（注：私はGMPYを維持する助けと私は最新のリリースでは、かなりの数の最適化を実装しました）MPZに小さな数を追加する際に

GMPY v1.11デベロッパーがmpz_add_uiを使用しません。 GMPYの最新バージョンは、以前のバージョンよりも約25％高速です。

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 

MPZにPythonのint型に変換するよりも、それは長いにPythonのint型に変換し、mpz_add_uiを呼び出すために高速ですので、適度なパフォーマンス上の利点があります。長い間GMP関数をネイティブ演算と呼び出す場合のパフォーマンスが10倍になると、私は驚くことはありません。

小さな番号のいくつかを1つのlong longに蓄積し、一度に大きな番号に追加できますか？