原始测试需要比蛮力方法更长的时间,我该如何改进？

Question

我试图在一台机器上计算素数,大小约为2 ^ 30-2 ^ 100.
对于任何感兴趣的人,我的算法都包含在
我已经针对O(sqrt(n/2))每个数字优化了这个Python代码(我相信):它只接受奇数,并且我确保传递给它的数字在另一个方法中是奇数.

我使用费马素性测试来尝试加快这个过程.但是,对于内置math.pow()方法,数字太大,所以我使用了Squaring的Exponentiation.
然而,对于更大的数字来说这需要很长时间 - 使用蛮力会更快.

我的实施错了吗？
时间来自平方算法,它的重复堆栈也占用了我的记忆,我应该研究一个更快的算法吗？

要计算数字35184372088967是否为素数,使用我的强力算法需要.00100111秒,但需要.40608秒来运行素数测试.

蛮力素数检查:

def isPrime(n):
    for i in range(3,int(math.sqrt(n)),2):
        if(n%i==0):
            return False
    return True

Fermat算法的实现:

def couldBePrime(n):
        if(n>308):
            return power(2,n-1)%n==1
        else:
            return math.pow(2,n-1)%n==1

通过平方算法的指数化(耗时部分):

def power(base,exp):
    if exp == 0:
        return 1
    elif exp == 1:
        return base
    elif (exp & 1) != 0:
        return base * power(base * base, exp // 2)
    else:
        return power(base * base, exp // 2)

Answer 1

错误:math.pow计算浮点值.浮点计算是近似的,在这里会给你无意义的结果.您需要进行整数计算,例如在power函数中执行(效率低下).Python的内置**运算符和pow函数(不是math.pow,它是一个不同的函数)都在整数上运行.

在Python中,与许多编程语言一样,所调用的库math特别是关于浮点计算,而不是关于其他类型的数学计算,例如对整数进行的计算.

低效:计算b ^ e mod n,执行算术模n更有效,而不是先计算b ^ e然后将结果除以n.计算b ^ e需要构建一个非常大的数字,这将是缓慢的,因为随着计算越来越高的b次数,数字变得非常快.(计算b ^ e的最佳方法不容易确定,但所有方法都涉及计算b的中间幂,唯一的实际不确定性是以什么顺序.)当你想要结果模n时,做所有连续乘法模数n:计算b ^ 2 mod n,然后使用square和reduce modulo n来获得b ^ 4 mod n等.每次执行乘法运算时,在执行任何其他操作之前,请将除数的余数除以n.

在Python中,标准库函数pow(记住,不是 math.pow)将为您做到这一点.这很简单

def couldBePrime(n):
    return pow(2, n-1, n) == 1

如果Python没有这个函数,那么你的power函数是一种合理的方法来实现它,如果你减少每个中间结果的模数n.

def power(base, exp, mod):
    if exp == 0:
        return 1
    elif exp == 1:
        return base % mod
    elif (exp & 1) != 0:
        return (base * power((base * base) % mod, exp // 2, mod)) % mod
    else:
        return power((base * base) % mod, exp // 2)

当然,调用内置函数要快得多,因为这是执行操作的一种不错但不是非常好的方法,并且因为Python更易于编写而不是速度,因此最好将其保留为as尽可能将数字重载提升到内置函数.

另外要注意的是:要计算2的幂,有比乘法更快的方法 - 进行位移.但这在这里没有用,因为你想要计算2 ^ e mod n而不是2 ^ e.