Re: Fibonacci Recursion, What??



Finally, here's a version by Bradley Lucier, translated by Nicholas Neuss from scheme into common lisp, and only slightly modified by yours truly to handle bogus inputs. It runs faster than any of the other versions posted here so far, and only conses a bit more, but then, it returns two values at every recursive call, fib(n) and fib(n + 1):

(defun fib (n) "Returns f_n f_{n+1}."
(cond ((not (and (integerp n) (>= n 0)))
(error "fibonacci numbers are only defined for integers 0 and greater"))
((zerop n) (values 0 1))
((= n 1) (values 1 1))
((= n 2) (values 1 2)) (t (let ((m (floor n 2))) (multiple-value-bind (f_m f_m+1) (fib m) (let ((f_m^2 (* f_m f_m)) (f_m+1^2 (* f_m+1 f_m+1))) (if (evenp n) (values (- (* 2 f_m+1^2) (* 3 f_m^2) (if (oddp m) -2 2)) (+ f_m^2 f_m+1^2)) (values (+ f_m^2 f_m+1^2) (- (* 3 f_m+1^2) (* 2 f_m^2) (if (oddp m) -2 2))))))))))

btw, Brad's original scheme version:

(define (fib n) ;; returns f_n f_{n+1} (case n ((1) (values 1 1)) ((2) (values 1 2)) (else (let ((m (quotient n 2))) (call-with-values (lambda () (fib m)) (lambda (f_m f_m+1) (let ((f_m^2 (* f_m f_m)) (f_m+1^2 (* f_m+1 f_m+1))) (if (even? n) (values (- (* 2 f_m+1^2) (* 3 f_m^2) (if (odd? m) -2 2)) (+ f_m^2 f_m+1^2)) (values (+ f_m^2 f_m+1^2) (- (* 3 f_m+1^2) (* 2 f_m^2) (if (odd? m) -2 2)))))))))))

computes the 1 millionth fibonacci number (and the million-and-first) in 0.14 seconds under mzscheme compared to the sbcl common lisp time of 1.25 seconds, so mzscheme is still almost 10 times as fast here.


.