尝试使用 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() 可用于消除 % 运算的原因与添加以 10 为基数的数字来检查是否能被 9 整除的原因相同。在这种情况下，unpack() 创建 p 位数字，我们将除以by 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!