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.


.



Relevant Pages

  • Re: porting a Forth program
    ... surely prefer Common Lisp (at least PLT Scheme is not the way to ... On the other hand, while PLT is a slow environment, Scheme does have ... (module fib scheme/base ...
    (comp.lang.lisp)
  • Re: Scheme vs Common Lisp: war stories
    ... When you switch from programming in Common Lisp to programming in Scheme ... that could have worked just as well -- techniques that look almost exactly ...
    (comp.lang.lisp)
  • Re: Python syntax in Lisp and Scheme
    ... dislike blatantly arguing with people over language choice. ... I think that if you can get over S-exps then Scheme and Common Lisp ... feel very like python. ...
    (comp.lang.lisp)
  • Re: Noob Wonders: Lisp-1 vs. Lisp-2
    ... “Now, the question is, why do Lisps before Common Lisp have this multi- ... language that is characterized by uncommon or pretentious ... losing the debate, and I felt it wasn't for reasons I considered "fair". ... using the term "Scheme" as the opponent position. ...
    (comp.lang.lisp)
  • Re: the jargon lisp1 vs lisp2
    ... it's no accident that Scheme is on the side of 1 ... multiple, arguably redundant, conditional constructs [sorted out by ... term (Common Lisp wise) might be that scheme has sterile macros. ... I'm reminded of the old joke about an MIT student and a Harvard ...
    (comp.lang.lisp)