■

問題 1.19

直感的に行列の変換だと思ったので以下のように解く

ベクトル(a,b)に対して行列を作用させた後のベクトルを
とするとは

となる。
よって、(a, b)にを2回作用させると



となるのでここで
 ... ①
 ... ②
と置くと

と書けるので求めるq'とp'は①、②の通りである。

にをn回作用させる問題はを求める問題と同義であり、それは以下のようなアルゴリズムとなる

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