Re: Fibonacci Recursion, What??
 From: Raffael Cavallaro <raffaelcavallaro@pasd'espams'ilvousplaitmac.com>
 Date: Wed, 26 Sep 2007 01:39:40 0400
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))) (multiplevaluebind (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))) (callwithvalues (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 millionandfirst) 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.
.
 FollowUps:
 Re: Fibonacci Recursion, What??
 From: J. I. Gyasu
 Re: Fibonacci Recursion, What??
 From: Nicolas Neuss
 Re: Fibonacci Recursion, What??
 References:
 Fibonacci Recursion, What??
 From: qikink
 Re: Fibonacci Recursion, What??
 From: KT
 Re: Fibonacci Recursion, What??
 From: J. I. Gyasu
 Re: Fibonacci Recursion, What??
 From: J. I. Gyasu
 Re: Fibonacci Recursion, What??
 From: Raffael Cavallaro
 Re: Fibonacci Recursion, What??
 From: J. I. Gyasu
 Re: Fibonacci Recursion, What??
 From: Raffael Cavallaro
 Re: Fibonacci Recursion, What??
 From: Thomas A. Russ
 Re: Fibonacci Recursion, What??
 From: Raffael Cavallaro
 Re: Fibonacci Recursion, What??
 From: Raffael Cavallaro
 Re: Fibonacci Recursion, What??
 From: J. I. Gyasu
 Re: Fibonacci Recursion, What??
 From: Raffael Cavallaro
 Fibonacci Recursion, What??
 Prev by Date: Re: Notational Convention for BNF in HyperSpec
 Next by Date: Re: Using format to produce the expansion of a macro
 Previous by thread: Re: Fibonacci Recursion, What??
 Next by thread: Re: Fibonacci Recursion, What??
 Index(es):
Relevant Pages
