ログ

見る価値ありません

SICP 練習問題1.19 フィボナッチ数を対数時間で求める

技術 Lisp

a \leftarrow a + b, b \leftarrow a

から


\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} a + b \\ a \end{pmatrix}

また


T\begin{pmatrix} a \\ b \end{pmatrix}
= \begin{pmatrix} bp + ap + aq \\ bp + aq \end{pmatrix} \\
T = \begin{pmatrix} p + q & q \\ q & p \end{pmatrix}

から


T^2 = \begin{pmatrix} p + q & q \\ q & p \end{pmatrix}^2
= \begin{pmatrix} (p + q)^2 + q^2 & q(2p + q) \\ q(2p + q) & p^2 + q^2 \end{pmatrix}

よって

(define (even? x) (= (remainder x 2) 0))

(define (fib n)
  (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   (+ (* p p) (* q q))
                   (* q (+ (* p 2) q))
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))