No trabalho do curso, foi necessário escrever um algoritmo com complexidade logarítmica, que encontrará o enésimo número da sequência de Fibonacci.
Algoritmo
Encontrei vários artigos sobre esse assunto, todos tratando da clássica série de números de Fibonacci. Para ele, você pode aplicar esta fórmula:
Mas em meu trabalho, foram usadas séries generalizadas, nas quais os dois primeiros números são zero e algum parâmetro. Depois de horas de pesquisa, encontrei um comentário interessante no qual o autor fornece uma fórmula para a descoberta cíclica de qualquer sequência linear recorrente (incluindo uma série de números de Fibonacci).
Aqui, Q é uma matriz 2x2 cujos elementos podem ser facilmente calculados.
Substituindo alguns poucos números de Fibonacci, descobrimos que a matriz Q = [[0,1], [1,1]].
A fórmula final da matriz, que contém o enésimo número da série generalizada de Fibonacci, pode ser escrita da seguinte forma:
Fn é o número de Fibonacci desejado,
C é a chave,
n é o número ordinal do número
Obviamente, para a eficiência de todo o algoritmo, é necessário usar o algoritmo mais rápido para elevar a matriz Q à potência n. Este artigo me ajudou a lidar com isso. Isso explica que, para elevar uma matriz à potência de n, você pode dividir n em potências de dois e, em seguida, elevar as matrizes apenas a essas potências. Esta abordagem fornece a complexidade O (log N).
Então resta apenas multiplicar pela matriz [[C, C], [C, 0]] e obter o elemento com o índice [0,1].
Implementação Python
class FiboMatrix:
key = 0
matrix_cur = [[0,0], [0,0]]
matrix_one = [[0,1], [1,1]]
def __init__(self, key):
self.key = key
self.matrix_cur = [[key, key], [key, 0]]
self.PowsBuffer = {}
#
def MultiplyMatrix(self, M1, M2):
"""
2x2 ."""
a11 = M1[0][0] * M2[0][0] + M1[0][1] * M2[1][0]
a12 = M1[0][0] * M2[0][1] + M1[0][1] * M2[1][1]
a21 = M1[1][0] * M2[0][0] + M1[1][1] * M2[1][0]
a22 = M1[1][0] * M2[0][1] + M1[1][1] * M2[1][1]
return [[a11, a12], [a21, a22]]
def PowMatrix(self, M: list, p: int):
""" .
2x2 .
"""
if p == 1:
return M
if p in self.PowsBuffer:
return self.PowsBuffer[p]
K = self.PowMatrix(M, int(p / 2))
R = self.MultiplyMatrix(K, K)
self.PowsBuffer[p] = R
return R
def GetNum(self, n):
if n == 0:
return 0
if n == 1:
return 1
# n
powers = []
p = 0
for digit in reversed(bin(n)[2:]):
if digit == '1':
powers.append(int(pow(2, p)))
p += 1
matrices = [self.PowMatrix(FiboMatrix.matrix_one, p)
for p in powers]
#
while len(matrices) > 1:
M1 = matrices.pop()
M2 = matrices.pop()
R = self.MultiplyMatrix(M1, M2)
#
matrices.append(R)
self.matrix_cur = self.MultiplyMatrix(self.matrix_cur, matrices[0])
# F1 F2 ,
return self.matrix_cur[0][1]
Para comparar a eficiência, o análogo mais simples deste algoritmo foi escrito usando um loop:
def Fib(num, key):
fib_1 = 0
fib_2 = key
for dec in range(num):
fib_1, fib_2 = fib_2, fib_1+fib_2
return fib_2
Os benchmarks confirmam nossas expectativas: o algoritmo clássico leva várias vezes mais tempo já no décimo número.
