具有小整数有效加法的Bignum实现

Question

我一直在使用python的原生bignums作为算法，并决定尝试通过将其转换为C++来加快速度。当我使用long long时，C++大约比python快100倍，但当我在C++中使用GMP绑定时，它只比python快10倍(对于同样适合long的情况)。

有没有更好的bignum实现来做大量的小添加？例如，我们有一个大数字N，我们将添加大量的小数字+1，+21，+1，等等，然后不时地增加另一个大数字M？

Answer 1

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中，而不是将一个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，因为我真的希望这会快很多。

Answer 2

你做侧写了吗？Python和C++ whole应用程序。这样你就知道你真的需要额外的速度。

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

Answer 3

(注意:我帮助维护GMPY，并且在最近的版本中实现了相当多的优化。)

GMPYv1.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 int转换为long并调用mpz_add_ui比将Python int转换为mpz更快，因此具有中等的性能优势。如果在long long上调用GMP函数与本地操作相比会有10倍的性能损失，我不会感到惊讶。

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