尝试使用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 has stopped working对话框.

使用标准的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演出的内存并没有gmpy这个脚本运行了几天而没有内存耗尽(仍然不确定如何发生这种情况,因为s从来没有真正变大..

有人有主意吗？

编辑:忘了提我正在使用Python 3.2

Answer 1

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

直到今晚我才能测试这个.但有几点意见和问题.

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

如果你使用gmpy2.mpz()而不是gmpy2.xmpz()会发生什么？

你在运行64位版本的Python和gmpy2吗？(我假设如此,但我只想确认一下.)

关于范围与xrange,在Python 3.x中,范围已经取代了xrange.

使用其他信息进行编辑

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

unpack(x,n)函数类似于string的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!