如何使我的斐波那契与模块化算术更有效地找到皮萨诺循环？
How to make my Fibonacci with Modular Arithmetic more efficient to find the pisano cycle?
出于教育目的，我正在 Python3 中构建代码以实现此目标：
我认为我在这个问题上做得很好，因为我处于 beginner/intermediate 级别。这个问题是高级的，不是强制性的。
我使用 slow-but-saffer 函数作为 "control group" 进行了压力测试。在那之后，我能够创建一个更快的函数。
但是，我的实施对于某些 pisano 循环 是有问题的。
正如您在这里看到的那样：
http://webspace.ship.edu/msrenault/fibonacci/fiblist.htm
一些 mod 可以创造巨大的皮萨诺 periodic-cycles...
我的函数对于像 <249 这样的 mods 工作得非常快......但是，我不知道如何处理像 1570 这样的 mods，它会生成一个 pattern/cycle 总长度为 4740 个数字...这是一个循环模式，涉及的不是 001 我们的 12113，而是 4740 个数字...
我试着寻找解决这个问题的方法。我能够找到解决问题的不同方法。尽管如此，我还是想尝试修复我的实现，使其在 cycle-recognition 部分更快 - 如果可能的话....
这是我的代码。
coursera_input = (input())
coursera_input = (coursera_input.split())
n_in = int(coursera_input[0])
mod_in = int(coursera_input[1])
import random
def my_fibo_iter(x):
if x<=1:
return x
else:
bef_previous_elem = 0
previous_elem = 1
current = 0
count = 1
while count<x:
count = count + 1
current = bef_previous_elem + previous_elem
bef_previous_elem = previous_elem
previous_elem = current
return (current)
def fibo_iter_mod_slow(n,mod):
if n==0:
return n%mod
elif n==1:
return n%mod
else:
previous = 1%mod
bef_previous = 0%mod
count = 1
while count<(n):
current = bef_previous%mod + previous%mod
bef_previous = previous%mod
previous = current%mod
count = count + 1
return current%mod
#preciso construir um algoritmo para identificar a pisano period/cycle
def pisano_cycle(big_list):
promising_list = []
for i in big_list:
promising_list.append(i)
p_l_len = len(promising_list)
p_l_final_index = 2*p_l_len
if promising_list == big_list[p_l_len:p_l_final_index]:
break
return promising_list
def generate_big_pisano_list(mod):
big_list = []
if mod<249:
limit = 700
if 249<=mod<1000:
limit = 3001
else:
limit = 6000
for i in range(0,limit):
big_list.append(fibo_iter_mod_slow(i,mod))
return big_list
#agora eu sei gerar uma lista pisano
#sei identificar uma lista de pisano
#preciso de uma outra função
#ela deve, sabendo o padrão CÍCLICO, identificar o nth elemento desse padrão
def fibo_iter_mod_fast(n,mod):
big_pisano_list = generate_big_pisano_list(mod)
pattern = pisano_cycle(big_pisano_list)
length_patt = len(pattern)
index_analogous = (n%length_patt)
output_in_mod = pattern[index_analogous]
return output_in_mod
print (fibo_iter_mod_fast(n_in,mod_in))
如果您输入如下内容：
2816213588 30524
得到正确的输出：
10249
但是需要5秒多...
发生的另一个问题是当我有一个巨大的数字作为 mod 的输入时，例如：
失败案例 #12/22：（错误答案）
输入：99999999999999999 100000
你的输出：69026
正确输出：90626
（使用时间：0.04/5.00，使用内存：24100864/536870912。）
我的代码 returns 由于这一部分输出不正确：
def generate_big_pisano_list(mod):
big_list = []
if mod<249:
limit = 700
if 249<=mod<1000:
limit = 3001
else:
limit = 6000
我将皮萨诺循环的范围限制在 60000 个数字的范围内，显然，有些皮萨诺循环可以超出这个范围...
您应该使用模运算计算斐波那契数，而不是计算循环长度，因为循环长度有对数算法。
为此所需的迭代总数肯定低于显式计算皮萨诺循环长度所需的迭代次数。
你要利用的关系是
fib(2n) = fib(n) * ( 2 * fib(n+1) - fib(n) )
fib(2n+1) = fib(n+1) ^ 2 + fib(n) ^ 2
如果您在模运算中进行乘法和加法运算，则可以使用整数数据类型 (10^5 < 2^17) 以获得精确结果。
出于教育目的，我正在 Python3 中构建代码以实现此目标：
我认为我在这个问题上做得很好，因为我处于 beginner/intermediate 级别。这个问题是高级的，不是强制性的。
我使用 slow-but-saffer 函数作为 "control group" 进行了压力测试。在那之后，我能够创建一个更快的函数。
但是，我的实施对于某些 pisano 循环 是有问题的。 正如您在这里看到的那样： http://webspace.ship.edu/msrenault/fibonacci/fiblist.htm 一些 mod 可以创造巨大的皮萨诺 periodic-cycles...
我的函数对于像 <249 这样的 mods 工作得非常快......但是，我不知道如何处理像 1570 这样的 mods，它会生成一个 pattern/cycle 总长度为 4740 个数字...这是一个循环模式，涉及的不是 001 我们的 12113，而是 4740 个数字...
我试着寻找解决这个问题的方法。我能够找到解决问题的不同方法。尽管如此，我还是想尝试修复我的实现，使其在 cycle-recognition 部分更快 - 如果可能的话....
这是我的代码。
coursera_input = (input())
coursera_input = (coursera_input.split())
n_in = int(coursera_input[0])
mod_in = int(coursera_input[1])
import random
def my_fibo_iter(x):
if x<=1:
return x
else:
bef_previous_elem = 0
previous_elem = 1
current = 0
count = 1
while count<x:
count = count + 1
current = bef_previous_elem + previous_elem
bef_previous_elem = previous_elem
previous_elem = current
return (current)
def fibo_iter_mod_slow(n,mod):
if n==0:
return n%mod
elif n==1:
return n%mod
else:
previous = 1%mod
bef_previous = 0%mod
count = 1
while count<(n):
current = bef_previous%mod + previous%mod
bef_previous = previous%mod
previous = current%mod
count = count + 1
return current%mod
#preciso construir um algoritmo para identificar a pisano period/cycle
def pisano_cycle(big_list):
promising_list = []
for i in big_list:
promising_list.append(i)
p_l_len = len(promising_list)
p_l_final_index = 2*p_l_len
if promising_list == big_list[p_l_len:p_l_final_index]:
break
return promising_list
def generate_big_pisano_list(mod):
big_list = []
if mod<249:
limit = 700
if 249<=mod<1000:
limit = 3001
else:
limit = 6000
for i in range(0,limit):
big_list.append(fibo_iter_mod_slow(i,mod))
return big_list
#agora eu sei gerar uma lista pisano
#sei identificar uma lista de pisano
#preciso de uma outra função
#ela deve, sabendo o padrão CÍCLICO, identificar o nth elemento desse padrão
def fibo_iter_mod_fast(n,mod):
big_pisano_list = generate_big_pisano_list(mod)
pattern = pisano_cycle(big_pisano_list)
length_patt = len(pattern)
index_analogous = (n%length_patt)
output_in_mod = pattern[index_analogous]
return output_in_mod
print (fibo_iter_mod_fast(n_in,mod_in))
如果您输入如下内容：
2816213588 30524
得到正确的输出：
10249
但是需要5秒多...
发生的另一个问题是当我有一个巨大的数字作为 mod 的输入时，例如：
失败案例 #12/22：（错误答案）
输入：99999999999999999 100000
你的输出：69026
正确输出：90626
（使用时间：0.04/5.00，使用内存：24100864/536870912。）
我的代码 returns 由于这一部分输出不正确：
def generate_big_pisano_list(mod):
big_list = []
if mod<249:
limit = 700
if 249<=mod<1000:
limit = 3001
else:
limit = 6000
我将皮萨诺循环的范围限制在 60000 个数字的范围内，显然，有些皮萨诺循环可以超出这个范围...
您应该使用模运算计算斐波那契数，而不是计算循环长度，因为循环长度有对数算法。
为此所需的迭代总数肯定低于显式计算皮萨诺循环长度所需的迭代次数。
你要利用的关系是
fib(2n) = fib(n) * ( 2 * fib(n+1) - fib(n) )
fib(2n+1) = fib(n+1) ^ 2 + fib(n) ^ 2
如果您在模运算中进行乘法和加法运算，则可以使用整数数据类型 (10^5 < 2^17) 以获得精确结果。