Create a gist now

Instantly share code, notes, and snippets.

@evanberkowitz /3 fibs Secret
Last active Dec 18, 2015

3 different (fib n) implementations.
;;; Works in DrRacket Pretty Big language
(define fibRecursive (lambda (n) (cond ((= n 0) 1)
((= n 1) 1)
(else (+ (fibRecursive (- n 1)) (fibRecursive (- n 2)))))))
(define range (lambda (n m) (cond ((= n m) (list n)) (else (cons n (range ((if (< n m) + -) n 1) m))))))
(define fibLinear (lambda (n) (car (foldr (lambda (foo pair) (list (cadr pair) (+ (car pair) (cadr pair)))) '(0 1) (range 0 n)))))
(define square (lambda (x) (* x x)))
(define pow (lambda (base exp) (cond ((= exp 0) 1)
((= exp 1) base)
((even? exp) (square (pow base (/ exp 2))))
(else (* base (square (pow base (/ (- exp 1) 2))))))))
(define phi (/ (+ 1 (sqrt 5)) 2)) ; Finite floating point precision renders fibLog inaccurate for large n
(define fibLog (lambda (n) (inexact->exact (round (/ (pow phi (+ n 1)) (sqrt 5))))))
(map fibRecursive (range 0 10))
(map fibLinear (range 0 10))
(map fibLog (range 0 10))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment