python - 尝试使用 gmpy 在 Python 中计算大数。 Python 一直崩溃？

Question

有人建议我使用 gmpy 来帮助有效地计算大数。在我只使用 python 之前，我的脚本运行了一两天然后内存不足(不确定这是怎么发生的，因为我的程序的内存使用基本上应该始终保持不变。可能是内存泄漏？)

无论如何，在运行我的程序几秒钟后，我不断收到这个奇怪的错误:

mp_allocate< 545275904->545275904 >
Fatal Python error: mp_allocate failure

This application has requested the Runtime to terminate it in an unusual way. 
Please contact the application's support team for more information.

此外，python 崩溃了，Windows 7 给了我通用的 python.exe 已停止工作 对话框。

使用标准 python 整数不会发生这种情况。现在我切换到 gmpy，我在运行脚本的几秒钟内就收到了这个错误。我以为 gmpy 专门处理大数运算？

作为引用，下面是一个产生错误的示例程序:

import gmpy2

p = gmpy2.xmpz(3000000000)
s = gmpy2.xmpz(2)
M = s**p

for x in range(p):
    s = (s * s) % M

我有 10 GB 的 RAM，在没有 gmpy 的情况下，这个脚本运行了好几天都没有用完内存(考虑到 s 从未真正变大，仍然不确定这是怎么发生的..

有人有什么想法吗？

编辑:忘了说我使用的是 Python 3.2

Answer 1

免责声明:我是 gmpy 和 gmpy2 的维护者。

直到今晚我才能测试这个。但是有一些意见和问题。

不使用 (s * s) % M，而是使用 pow(s, 2, M)。它应该更快。

如果您使用 gmpy2.mpz() 而不是 gmpy2.xmpz() 会怎样？

您运行的是 64 位版本的 Python 和 gmpy2 吗？ (我想是的，但我只是想确认一下。)

关于 range 与 xrange，在 Python 3.x 中，range 已经取代了 xrange。

编辑附加信息。

崩溃的原因是 32 位构建中的内部结构溢出。使用 64 位版本的 Python 和 gmpy 或 gmpy2 是正确的解决方法。

unpack(x,n) 函数类似于字符串的 split():它将一个数字分成一系列 n 位值。它等同于但快于:

def unpack(x,n):
r = []
m = 2**n
while x:
    x, temp = divmod(x,m)
    r.append(temp)
return r

一些文档可以通过 help(gmpy2.unpack) 获得，但更好的文档在我的待办事项列表中。

unpack() 可用于消除 % 操作的原因与添加 base-10 数字的数字以检查 9 的整除性相同。在这种情况下，unpack() 创建 p 位数字和我们除以 2**p - 1。

这是一些测试代码:

import gmpy2
import time

def mersenne1(p):
    '''Primality test for Mersenne prime: 2**p -1.
    Uses native Python longs. Does not verify that p is prime.'''

    s = 4
    M = 2**p - 1
    for i in range(p-2):
        s = ((s*s)-2) % M
    return False if s else True

def mersenne2(p):
    '''Primality test for Mersenne prime: 2**p -1.
    Uses gmpy2.mpz. Does not verify that p is prime.'''

    s = gmpy2.mpz(4)
    M = gmpy2.mpz(2)**p - 1
    for i in range(p-2):
        s = ((s*s)-2) % M
    return False if s else True

def mersenne3(p):
    '''Primality test for Mersenne prime: 2**p -1.
    Uses gmpy2.mpz and no mod. Does not verify that p is prime.'''

    s = gmpy2.mpz(4)
    M = gmpy2.mpz(2)**p - 1
    for i in range(p-2):
        s = (s*s)
        s = sum(gmpy2.unpack(s, p))
        s = sum(gmpy2.unpack(s, p))
        if s < 2:
            s = M - 2 + s
        else:
            s = s - 2
    return False if s else True

if __name__ == "__main__":
    p = 44497

    start = time.time()
    result1 = mersenne1(p)
    print("Elapsed time: {:6.3f}".format(time.time() - start))

    start = time.time()
    result2 = mersenne2(p)
    print("Elapsed time: {:6.3f}".format(time.time() - start))

    start = time.time()
    result3 = mersenne3(p)
    print("Elapsed time: {:6.3f}".format(time.time() - start))

    if result1 == result2 == result3:
        print("All three tests are equal!")
    else:
        print("Oops, something has gone wrong.")

还有一些运行时间...

C:\x64\Python32>python.exe mersenne.py
Elapsed time: 163.683
Elapsed time: 12.782
Elapsed time:  3.630
All three tests are equal!