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))))