Skip to content

Instantly share code, notes, and snippets.

@jld

jld/fast-fib.sch

Created February 4, 2019 02:29
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 jld/a5c6a17d57b94a87de73ad4ca00ef78b to your computer and use it in GitHub Desktop.
Save jld/a5c6a17d57b94a87de73ad4ca00ef78b to your computer and use it in GitHub Desktop.
Download ZIP
Raw
fast-fib.sch
(define (m5 x y)
(cons (+ (* (car x) (car y)) (* 5 (cdr x) (cdr y)))
(+ (* (car x) (cdr y)) (* (cdr x) (car y)))))
(define (q5 x) (m5 x x))
(define (p5 x n)
(cond ((zero? n) '(1 . 0))
((even? n) (q5 (p5 x (/ n 2))))
(#t (m5 x (q5 (p5 x (/ (- n 1) 2)))))))
(define (ffi n) (/ (cdr (p5 '(1 . 1) n)) (expt 2 (- n 1))))
;; --
(define phi (+ 1/2 (sqrt 5/4)))
(define (lbp x) (/ (log x) (log phi)))
(define (unfi x) (inexact->exact (round (+ (lbp x) (lbp (sqrt 5))))))
(define (fib? x) (= x (ffi (unfi x))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment