Tuesday, July 09, 2019

SICP in Clojure: Chapter 1, Exercise 13

This is my Clojure solution to Chapter 1, Exercise 13:

(ns sicp.ch1.ex13)

(defn fib
  [n]
  (if (< n 2)
    n
    (+ (fib (- n 1)) (fib (- n 2)))))

(def phi (/ (+ 1 (Math/sqrt 5)) 2))

(def psi (/ (- 1 (Math/sqrt 5)) 2))

(defn fib-exact
  [n]
  (Math/round (/ (- (Math/pow phi n) (Math/pow psi n))
                 (Math/sqrt 5))))

(every? #(= (fib %) (fib-exact %)) (range 10)) ; => true

;; assume f(n) = (phi^n - psi^n)/5^-2
;; assume f(n + 1) = (phi^(n + 1) - psi^(n + 1)/5^-2
;; prove that f(n + 2) = (phi^(n + 2) - psi^(n + 2)/5^-2 where
;; f(n + 2) = f(n + 1) + f(n)

No comments: