Nth Fibonacci number in Emacs Lisp

Posted on January 29, 2012 by Tommy McGuire
Labels: emacs, toy problems, lisp, math

Following a post by Phil, a video game developer in Orange County, this is the Fibonacci function in Emacs Lisp:


;;; Define some constants
(defconst s5 (sqrt 5) "square root of 5")
(defconst is5 (/ 1 s5) "inverse of the square root of 5")
(defconst ps52 (/ (+ 1 s5) 2) "1 plus sqrt(5) over 2")
(defconst ns52 (/ (- 1 s5) 2) "1 minus sqrt(5) over 2")

;;; The fibonacci function
(defun fibonacci (n)
"Nth fibonacci number"
(truncate (* is5
(- (expt ps52 n)
(expt ns52 n)))))

I'll leave the proof of it to Phil (and it is pretty damn nice), but here are some quick examples:


(fibonacci 0)
0
(fibonacci 1)
1
(fibonacci 2)
1
(fibonacci 3)
2
(fibonacci 4)
3
(fibonacci 5)
5
(fibonacci 6)
8
(fibonacci 8)
21
(fibonacci 10)
55

And yes, I know it is using limited precision floating point numbers and will break six ways from Sunday.

Still, this is now my favorite answer to an interview question.

active directory applied formal logic ashurbanipal authentication books c c++ comics conference continuations coq data structure digital humanities Dijkstra eclipse virgo electronics emacs goodreads haskell http java job Knuth ldap link linux lisp math naming nimrod notation OpenAM osgi parsing pony programming language protocols python quote R random REST ruby rust SAML scala scheme shell software development system administration theory tip toy problems unix vmware yeti
Member of The Internet Defense League
Site proudly generated by Hakyll.