A Better Fibonacci (revisitado)

postado cruzado

Anteriormente, publiquei um algoritmo não recursivo para calcular um número de Fibonacci arbitrário:

PHI = 1.6180339887498948482045868
const_fib
= lambda do |n|
(
( PHI**n - ( 1 - PHI )**n ) /
Math.sqrt(5)
).
floor

end

Como a constante matemática PHI é um decimal infinito e não repetitivo, ela nunca pode ser representada exatamente em código. Na verdade, a série de Fibonacci calculada pelo código acima e a série exata divergem após apenas o 70º valor.

computed = []
(1..1474).each { |n| computed << const_fib[n].to_s }

# list of Fibonnaci number can be downloaded [here](http://oeis.org/A000045/b000045.txt)
exact
= []
File.open('./exact.txt', 'r').each_line do |line|
exact
<< line.split.last
end

exact
.shift # the first entry on the downloaded list is zero, get rid of it

index_of_last_match
= (computed & exact).size
#=> 70

computed
[index_of_last_match] == exact[index_of_last_match]
#=> true

computed
[index_of_last_match + 1] == exact[index_of_last_match + 1]
#=> false

Quando comecei a hackear este exercício de código banal, presumi que usar o PHI constante ainda seria mais eficiente do que um loop ou um algoritmo recursivo. Acontece que o hardware moderno torna a solução baseada em loop bastante tolerável.

loop_fib = lambda do |n|
fib
= []
n
.times do |n|
if n < 2
fib
= [0, 1, 1]
else
fib
<< ( fib[-1] + fib[-2] ).to_s
end
end
return fib.last
end

loop_fib
[70] == exact[70]
#=> true

loop_fib
[71] == exact[71]
#=> true

Meu computador quase não percebe. Que tal o método recursivo?

recur_fib = lambda do |n|
case n
when 0
1
when 1
1
else
recur_fib
[n - 1] + recur_fib[n - 2]
end
end

recur_fib
[70]

Bela matemática; código horrível! Executá-lo rapidamente consumiu minha memória e espaço de troca.

Vou representar um desafio para os leitores aqui. Leia a seção 1.2.1 em Estrutura e Interpretação de Programas de Computador para um modelo recursivo muito mais razoável e tente combinar a abordagem daquele livro com o primeiro algoritmo acima. Especificamente, empacote sua recursão em uma função separada que calcule um valor de precisão arbitrário para PHI. Podemos fazer const fib funcionar mais rápido e com mais eficiência do que loop fib?