Simples programa de Fibonacci

Fibonacci é série numerica que descreve a seguinte senquencia 1,1,2,3,4,5,8,13…, dessa maneira Leonardo Pisa descreve o crescimento pela seguiente fórmula: \(F_n=F_{n-1}+F_{n-2}\), com a condição inicial \(f(0)=0\) e \(f(1)=1\), então:

Agora descrevemos em common lisp. Obs.: eu implementei no elisp em um emacs-windows.

(require 'cl)

(defun fib(n)
   (if (<= n 2) 1
	 (+ (fib (- n 1)) (fib (- n 2)) )))

(message "Fib(%d):= %d" 5 (fib 8))

Fib(5):= 21

Eu quero verificar o tempo de execução da função fib que implementamos no elisp.

(benchmark-run 1 (fib 40))

(37.093078 0 0.0)

É demorou mais de 30 segundos para executar o fibonacci 40, na lista o primeiro é o tempo real de execução, segundo o número fde coletas de lixos e finalizando o tempo gasto pelo coletor de lixo, agora executar por meio de uma complexão binária.

(benchmark-run-compiled 1 (fib 40))

(36.967577 0 0.0)

Não mudou particamente nada, principalmente se consideramos o erro experimental, estão não ocorreu alteração. Realmente não tivemos um resultado rápido, mas podemos mudar nosso algoritmos para otimizamos o resultado.

Podemos mudar um pouco a nossa função fibonacci, porque nesta função utilizamos a pura recursão, o sistema deverá ultizar bastante a pinha para amazenar os resultados intermediaram e depois recalcular o valor de resposta. Então irei implentar na recursão um acumulador. Como a recursão e dupla, precisaremos de dois acumuladores, vejamos abaixo.

(defun fib-acc(n prev acc)
  (if (<= n 0) acc 
     (fib-acc (- n 1) acc (+ prev acc))))

(defun fib(n)
  (if (<= n 1) n
    (fib-acc n 1 0)))

(funcall (lambda (n) (message "Fib(%d): %d" n (fib n))) 40)

Fib(40): 102334155

(benchmark-run-compiled 1 (fib 40))

(1.4e-05 0 0.0)

Notamos que o tempos foi de 1.4x10⁵, particamente zero, estão é bom trabalhamos com acumulador.

Vemos que podemos otimizar a recursão utilizando acumuladores.