August 19th, 2004

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