Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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

This comment has been minimized.

Copy link
Owner Author

enigmaticape commented Nov 16, 2012

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
You can’t perform that action at this time.