高效添加小整数的Bignum实现

Question

我之前在用Python的原生大数（bignum）来做一个算法，后来决定试着用C++来加速一下。当我用长整型（long long）时，C++的速度比Python快了大约100倍，但当我在C++中使用GMP库时，速度只比Python快了10倍（在适合长整型的情况下）。

有没有更好的大数实现，适合进行大量的小加法？比如说，我们有一个大数N，要不断加一些小的数，比如+1、+21、+1等等，偶尔还会加另一个大数M？

Answer 1

你有没有对整个Python和C++应用程序进行性能分析？这样你才能确定自己真的需要那额外的速度。

试试Python 3k吧，它现在支持任意长度的整数了！

Answer 2

（注意：我在维护GMPY，并且在最近的版本中实现了不少优化。）

GMPY v1.11在将小数字加到mpz时确实使用了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的整型转换成长整型，然后调用mpz_add_ui，比把Python整型转换成mpz要快，所以在性能上有一定的优势。我不会感到惊讶，如果调用GMP函数的性能比直接在长整型上操作慢10倍的话。

你能把几个小数字累加成一个长整型，然后一次性加到你的大数字上吗？

Answer 3

GMP库本身有一个快速将短整型加到MPZ的功能

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

我不确定gmpy是否使用了这个功能，但如果它用了的话，可以试着把一个普通的Python整型加到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，因为我本来以为这样会快很多。