请教我如何优化我的代码。。。
我在寻找方程的斐波那契序列 a*Xn-1 - (c*c)Xn-2
. 我在找 a, c
值,该值将导致从 10th
任期 10,000th
学期但是,我也希望 term + 1
以及 term - 1
也是复合的。
随着数字越来越大,代码需要花费难以置信的时间才能完成。为了测试素性,我使用 from sympy.ntheory import isprime
功能。我没有使用列表,而是使用两个变量来表示斐波那契序列。我使用递归来分析较小的间隔,并逐渐向上移动到最大值。print语句应该有助于理解代码在运行时所做的事情。
这是我的密码:
from math import gcd
from sympy.ntheory import isprime
def check_pairs(a_c_pairs, start_checking_from, increment, max):
end_checking_at = start_checking_from + increment
pairs_that_passed_the_composite_test = [] # list of the successful pairs
print()
print(f"{a_c_pairs = }")
print(f"{start_checking_from = }, {end_checking_at = }, {increment = }, {max = }")
print()
print(f"Number of terms to check: {len(a_c_pairs)}")
count = 1
for a, c in a_c_pairs: # checking for each of the provided pairs
print(f"{count}/{len(a_c_pairs)}: {a=}, {c=}, result=", end="")
count += 1
first_term = 0
second_term = 1
fail = False
# iterating through each term in the sequence without using a list
for i in range(end_checking_at):
third_term = a*second_term - (c*c)*first_term
if not i < start_checking_from: # if the term is in our targeted range, check if that term is prime
if isprime(third_term) or isprime(third_term + 1) or isprime(third_term - 1):
fail = True
print("FAIL")
break
# set values for the loop to calculate the next term in the sequence
first_term = second_term
second_term = third_term
if not fail: # after the entire sequence has been analyzed, if none of the terms were prime
print("pass")
pairs_that_passed_the_composite_test.append([a, c])
if not end_checking_at == max:
check_pairs(pairs_that_passed_the_composite_test,
start_checking_from + increment, increment, max)
else:
print()
print("FINAL LIST OF PAIRS:")
for a, c in pairs_that_passed_the_composite_test:
print(a, c)
return
# these pairs have passed up to 3000 terms
a_c_pairs = [
[11, 3],
[34, 3],
[37, 3],
[38, 3],
[40, 3],
[41, 3],
[53, 3],
[56, 3],
[59, 3],
[61, 3],
[65, 3],
[71, 3],
[77, 3],
[82, 3],
[89, 3],
[94, 3],
[95, 3],
[98, 3],
[37, 5],
[39, 5],
[42, 5],
[43, 5],
[46, 5],
[51, 5],
[54, 5],
[57, 5],
[64, 5],
[73, 5],
[74, 5],
[77, 5],
[86, 5],
[89, 5],
[91, 5],
[98, 5],
[53, 7],
[55, 7],
[64, 7],
[71, 7],
[75, 7],
[79, 7],
[81, 7],
[83, 7],
[87, 7],
[92, 7],
[99, 7],
[100, 7],
[86, 9],
[89, 9],
[94, 9],
[97, 9],
[98, 9]
]
check_pairs(a_c_pairs, 2000, 500, 3000)
1条答案
按热度按时间jhiyze9q1#
检查一个数是否为素数对于大数来说是昂贵的。虽然有像aks这样的多项式复杂度算法可以做到这一点,但多项式的复杂度很大(即。
O(n^7)
哪里n
是被测数字的大小(以位为单位)。非确定性算法的多项式复杂度较低,但仍然相当大。例如,miller-rabin测试可以在O(n^4)
假设未经证实的广义黎曼假设是真的(到目前为止似乎是这样)。对于中等大小的数字,如64位拟合的数字,可以只检查几个基数,从而进行快速素性测试。对于大量的数据,研究人员正在积极地设计更好的算法(尤其是确定性的泛化无条件测试),并找到这种算法的理论算法复杂度边界。不幸的是,阿法克O(n^4)
接近最为人所知的复杂度(没有任何巨大的隐藏常数)来测试一个数字是否是复合的。问题是斐波那契序列增长非常快。对于标准版本,表示第i个元素的位数接近
2 i / 3
. 因此,计算时间将是相当大的i = 10 000
因为它需要处理大约6700位的数字,在最坏的情况下需要数百万次迭代(即质数)。目前还没有主流电脑能很快做到这一点(在未来20年内可能也不会)。解决这个问题的唯一可能的办法是设计一个特定的素性测试来测试生成的数字,乍一看这似乎是一项非常艰巨的任务。如果素数和斐波那契数之间没有关系,那么没有比使用最先进的算法更好的解决方案了(在你的例子中,算法太慢了)。否则,如果存在任何关系,则此类问题在堆栈溢出上是离题的,但您可以在math.stackexchange.com上问这个问题。
少数旁注:如果
third_term-1
是平的,那就只有了third_term
需要检查(因为其他不是素数)。如果third_term-1
很奇怪,third_term
不是质数,也不是质数third_term-1
或third_term+1
不是质数。此外,请注意,gcd和斐波那契数之间存在关系,gcd和素数之间存在关系,因此斐波那契数和素数之间可能存在关系。