有效添加小整數的Bignum實現

我一直在使用python的原生bignums作爲算法，並決定嘗試通過將其轉換爲C++來加速它。當我使用long long時，C++的速度比python快大約100倍，但是當我在C++中使用GMP綁定時，它的速度只比python快10倍（對於適用於long long的相同情況）。有效添加小整數的Bignum實現

是否有一個更好的bignum執行大量的小增加？例如，我們有一個很大的數字N，我們會增加很多小的+1，+ 21，+ 1等等，每過一段時間又增加一個大的數字M？

來源

2009-12-02 sligocki

的GMP庫本身具有fast short integer add to MPZ routine

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

我不知道gmpy是否使用，但如果它試圖將一個普通的Python的int的MPZ VS添加到MPZ MPZ，看看它更快。

編輯

我嘗試了一下標杆，發現它沒有任何區別

$ 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

所以我想gmpy不使用mpz_add_ui因爲我真的期望這是快得多。

來源

2009-12-02 07:48:04

有趣。我正在使用算術運算的C++重載，也許這些C++綁定也沒有使用這種快速方法。我明天會做一些測試。謝謝！ – sligocki 2009-12-02 09:18:02

你做過分析嗎？ Python和C++ 整個應用程序。所以你知道你真的需要這個額外的速度。

嘗試Python 3k它現在有任何長度的整數實現！

來源

2009-12-02 07:51:30

當整個項目的變化是從多頭到GMP MPZ的時候，這種放緩就是這樣。謝謝。 – sligocki 2009-12-02 08:12:28

「Python 3k現在具有任意長度的整數」是什麼意思？自從至少2.5版本以來，Python已經具有任意長度的整數（並且可能以前）。 – EOL 2009-12-02 14:49:07

現在所有ints都是任意長度的 – 2009-12-02 17:29:34

（注：我幫助維持GMPY，我已經在最近的版本中實現了不少的優化）增加少量到MPZ時

GMPY 1.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

既然是更快地一個Python INT轉換爲長，並調用mpz_add_ui不是一個Python INT轉換爲MPZ，有一個溫和的性能優勢。如果長時間調用GMP函數與本機操作的性能相差10倍，我不會感到驚訝。

您可以將幾個小數累加成一個long long，並將它們一次添加到您的大數？

來源

2009-12-04 08:16:28 casevh

是的，我一直在考慮寫我自己的課程來積累小數目並且不經常將它們添加到大數目中。感謝關於GMPY 1.11的說明。 – sligocki 2009-12-05 00:20:55

有效添加小整數的Bignum實現

回答

相關問題