我一直在使用 python 的原生 bignums 作为算法,并决定尝试通过将其转换为 C++ 来加速它。当我使用 long long 时,C++ 比 python 快大约 100 倍,但是当我在 C++ 中使用 GMP 绑定时,它只比 python 快 10 倍(对于适合 long long 的相同情况)。
是否有更好的 bignum 实现来进行大量的小加法?例如,我们有一个大数字 N,我们将添加很多小的 +1、+21、+1 等,并且每隔一段时间添加另一个大数字 M?
我一直在使用 python 的原生 bignums 作为算法,并决定尝试通过将其转换为 C++ 来加速它。当我使用 long long 时,C++ 比 python 快大约 100 倍,但是当我在 C++ 中使用 GMP 绑定时,它只比 python 快 10 倍(对于适合 long long 的相同情况)。
是否有更好的 bignum 实现来进行大量的小加法?例如,我们有一个大数字 N,我们将添加很多小的 +1、+21、+1 等,并且每隔一段时间添加另一个大数字 M?
GMP 库本身有一个快速的短整数添加到 MPZ 例程
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
,因为我真的希望它会快很多。
你做过剖析吗?Python 和 C++整个应用程序。这样您就知道您确实需要额外的速度。
试试 Python 3k,它现在实现了任意长度的整数!
(注意:我帮助维护 GMPY,并且我在最近的版本中实现了很多优化。)
mpz_add_ui
向 mpz 添加少量数字时,GMPY v1.11 确实使用。在处理少量数字时,最新版本的 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 更快,因此具有适度的性能优势。如果长时间调用 GMP 函数与本地操作相比有 10 倍的性能损失,我不会感到惊讶。
你能把几个小数累积成一长一长,然后一次把它们加到你的大数上吗?