Skip to content

Instantly share code, notes, and snippets.

@greymd

greymd/binet.egi

Created June 21, 2016 08:55
Show Gist options
  • Save greymd/16c63541711e2176ab64faef214c5c12 to your computer and use it in GitHub Desktop.
Save greymd/16c63541711e2176ab64faef214c5c12 to your computer and use it in GitHub Desktop.
Download ZIP
Calculate fibonacci numbers with O( log n)
Raw
binet.egi
(define $binet
(lambda [$n]
(* (/ 1 (sqrt 5))
(- (/ (+ 1 (sqrt 5)) 2)^n
(/ (- 1 (sqrt 5)) 2)^n))))
; > (binet 3)
; 2
; > (binet 1)
; 1
; > (binet 2)
; 1
; > (binet 3)
; 2
; > (binet 4)
; 3
; > (binet 5)
; 5
; > (binet 6)
; 8
; > (binet 7)
; 13
; > (binet 8)
; 21
; > (binet 9)
; 34
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment