Skip to content

Instantly share code, notes, and snippets.

@enigmaticape
Created November 4, 2012 13:22
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save enigmaticape/4011882 to your computer and use it in GitHub Desktop.
Save enigmaticape/4011882 to your computer and use it in GitHub Desktop.
Some code to go with an exploration of SICP exercise 1.13, a proof of closed form of Fibonacci function.
;; expt is three characters too long on the REPL
;; I use on my iPhone
(define (^ x n) (expt x n))
;; Golden Ratio, phi and the conjugate, psi
(define psi (/ (- 1 (sqrt 5)) 2))
(define phi (/ (+ 1 (sqrt 5)) 2))
;; Linear recursive Fib
(define (fib n)
(cond ( (= n 0) 0)
( (= n 1) 1)
( else ( + (fib (- n 1) )
(fib (- n 2) )))))
;; Approximation of Fib via Golden Ratio,
;; (phi^n)/sqrt( 5 )
(define (golden-fib n)
(/ (^ phi n) (sqrt 5)))
;; Fib by the closed form equation we just proved
(define (closed-fib n)
(/ (- (^ phi n) (^ psi n)) (sqrt 5)))
@enigmaticape
Copy link
Author

Supporting scheme code to compute Fibonacci in various ways, from a discussion of the solution to exercise 1.13 in SICP at http://www.enigmaticape.com/blog/sicp-exercise-1-13/

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment