使用Cython时计算错误

Question

我实现了Lucas-Lehmer primality test以检查python中的Mersenne素数。然后，我使用Cython加快了计算速度。

• 原始Python代码：

def lucas_lehmer(p):    
    if p == 2:
        return True

    s = 4
    M = (1 << p) - 1

    for i in range(p-2):    
        s = ((s * s) - 2) % M
        print("Processed: {}%".format(100*i//(p-2)))

    if s == 0:
        return True

    else:
        return False

• Cython代码：

cpdef lucas_lehmer(int p):    
    if p == 2:
        return True

    cdef unsigned long long int M
    M = (1 << p) - 1

    cdef unsigned long long int s
    s = 4

    cdef int i

    for i in range(p-2):    
        s = ((s * s) - 2) % M
        print("Processed: {}%".format(100*i//(p-2)))

    if s == 0:
        return True

    else:
        return False

运行原始的Python代码，它可以正常工作。但是对于Cython，仅在p = 31和更低的情况下才是正确的，在p = 61和更大的条件下进行测试（所有测试的p值都是2^p-1是质数的值），它返回False（不是质数），除了p = 86243 ]。

对于像97这样的p，即使2^97-1不是质数，程序实际上返回True（是质数），这是一个矛盾。

为什么会这样？如果不对变量M和s使用cdef，则计算将是正确的，但性能不会得到任何改善。

Answer 1

对您的代码进行了一些测试，我发现M始终等于1因此我将p定义为cdef并获得了所需的结果。

不确定是什么问题，但这与p上的位操作有关。 p必须具有与M相同的类型，才能有意义，并且如果一个是cdef而另一个是python int，则它不起作用吗？

cpdef lucas_lehmer(int py):    
    cdef p
    p = py
    if p == 2:
        return True

    cdef M
    M = (1 << p) - 1

    cdef s
    s = 4

    cdef int i

    for i in range(p-2):    
        s = ((s * s) - 2) % M
        print("Processed: {}%".format(100*i//(p-2)))

    if s == 0:
        return True

    else:
        return False