You are viewing fare

eyes black and white

Fun with Fibonacci

Everyone having studied science has met Fibonacci numbers somewhere or another in his curriculum. And everyone having studied recursion in programming languages has at one moment or another been taught how to "optimize" an exponentially slow recursive implementation of the Fibonacci function into a linearly slow iterative loop. Except they were lied to. For that loop they learnt as a model to emulate is far from "optimal". There exists an algorithm that is (asymptotically) infinitely faster. And to understand how this algorithm may be devised allows us to explore a few ways that expressive languages like Lisp can open your mind to horizons unconceivable using such inexpressive and awkward languages as are mainstream in the industry. Have a look at fibonacci.lisp

Comments

(Anonymous)

broken link to the actual code

Your link and/or script meant to show the Lisp code seems to be broken..

fixed link to the actual code

Oops. I don't use CVS anymore. I uploaded the (now stable) file to a new location and updated the link. Sorry for the trouble and thanks for your interest.
May I offer you another?


(defun fibs-series (n)
	     (let ((fibs (scan-fn '(values :integer :integer)
                                  (lambda () (values 1 1))
                                  (lambda (x y) (values y (+ x y))))))
               (collect-last (subseries fibs (1- n) n))))
Using multiple-value-call instead of (apply function (multiple-value-list ...)) should be better.

multiple-value-call

Thanks! I updated the file with this style improvement.

Re: multiple-value-call

It's not only style actually, it may eliminate consing too.
eyes black and white

December 2014

S M T W T F S
 123456
78910111213
14151617181920
21222324252627
28293031   

Tags

Powered by LiveJournal.com