Nth Fibonacci number in Emacs Lisp
Posted on January 29, 2012
by Tommy McGuire
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.