François-René Rideau (fare) wrote,
François-René Rideau
fare

  • Music:

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

Tags: code, en, lisp, mathematics
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 6 comments