<jupyter_start><jupyter_text>練習問題1.19フィボナッチ数を対数的ステップ数で計算する巧妙なアルゴリズムがある。  1.2.2節のfib-iterプロセスでの状態変数$a$と$b$の変換、  $a \leftarrow a+b$、  $b \leftarrow a$  を思い出そう。  この変換を$T$ と呼ぶことにする。  すると、$1$と$0$から始めて$T$を繰り返し$n$回適⽤すると  $Fib(n + 1)$と$Fib(n)$というペアができることになる。  ⾔い換えれば、フィボナッチ数はペア$(1, 0)$に対して  $T_{n}$(変換$T$の$n$乗)を適⽤することで求められるということだ。  ここで、$(a,b)$というペアを  $a \leftarrow bq + aq + ap$  と$b \leftarrow bp + aq$  に変換するような変換族$T_{p,q}$の特殊な場合  $(p=0,q=1)$として$T$を考えることにする。  このような変換$T_{p,q}$を⼆回適⽤すると、  その効果は同じ形 式を持つ$T_{p',q'}$を⼀回適⽤するのと同じであることを⽰し、$p$と$q$に対する$p'$と$q'$を求めよ。  こうすると、この種の変換に対する⼆乗を明⽰的に⾏うことができるようになり、  fast-expt⼿続きと 同じように、$T^n$を⼆乗の連続によって求められるようになる。   これらをすべて組み合わせて、対数的ステップ数で動く次の⼿続きを完成させよ。    (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'を計算する                          ; q'を計算する                (/ count 2)))            (else (fib-iter (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q)) p q (- count 1)))       )      ) **問題の解説**  $T_{p,q}(a,b)$の変換の定義  $a \leftarrow bq + aq + ap$  $b \leftarrow bp + aq$  $p=0,q=1$とすると、$T_{p,q}(a,b)=T_{0,1}(a,b)$の変換は、以下のようになる。  $a \leftarrow a+b$  $b \leftarrow a$  これは反復プロセスでフィボナッチ数を算出する際の式となっている。  よって、ペア$(a,b)=(1,0)$に対して、この変換を$n$回繰り返すことで、$n$番目のフィボナッチ数を得ることができる。  ペア$(a,b)=(1,0)$に対して$n$回繰り返すということを$T_{p,q}(a,b)$を使って、  $T_{0,1}(\cdots T_{0,1}(T_{0,1}(1,0))\cdots)=T_{0,1}^n(1,0)$    と書くことができる。  （これは、フィボナッチ数の計算が、指数計算の要領で計算できることを示している！)  $n$が奇数のときは、$T_{p,q}(a,b)$を1回施すことで  $T_{p,q}^n(a,b)=T_{p,q}^{n-1}(bq + aq + ap,bp + aq)$となり、べき数を下げることができる。  $n$が偶数のとき、  $T_{p,q}^n(a,b)=(T_{p,q}^{\frac{n}{2}}(a,b))^2=T_{p',q'}^{\frac{n}{2}}(a,b))$   と変形できれば、べき数下げることができ、計算量を下げることができる。  これがこの問題で求められている$p',q'$である。 **回答**  $T_{p,q}(a,b)$を2回行うと以下のようになる。  ($a$に$bq + aq + ap$を、$b$に$bp + aq$を代入)    1つ目の式：$(bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p=b(q^2+2pq)+a(q^2+2pq)+a(p^2+q^2)$  2つ目の式：$(bp + aq)p + (bq + aq + ap)q=b(p^2+q^2)+a(q^2+2pq)$  よって、  $p'=p^2+q^2$  $q'=q^2+2pq$  となる。  $n$が偶数のときは、  $T_{p,q}^n(a,b)=(T_{p,q}^{\frac{n}{2}}(a,b))^2=T_{p',q'}^{\frac{n}{2}}(a,b))=T_{p^2+q^2,q^2+2pq}^{\frac{n}{2}}(a,b))$  を求めることでべき数を下げることができる。<jupyter_code>(define (fib n)
  (fib-iter 1 0 0 1 n)
  )
(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
           (begin
               (display "fib-iter(")
               (display a)
               (display ",")
               (display b)
               (display ",")
               (display (+ (* p p) (* q q)))
               (display ",")
               (display (+ (* q q) (* 2 p q)))
               (display ",")
               (display (/ count 2))
               (display ")")
               (newline)
               (fib-iter a b 
                     (+ (* p p) (* q q)) ; p'を計算する
                     (+ (* q q) (* 2 p q)) ; q'を計算する
                     (/ count 2))
             )
           )
        (else (begin 
               (display "fib-iter(")
               (display (+ (* b q) (* a q) (* a p)))
               (display ",")
               (display (+ (* b p) (* a q)))
               (display ",")
               (display p)
               (display ",")
               (display q)
               (display ",")
               (display (- count 1))
               (display ")")
               (newline)
               (fib-iter (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q)) p q (- count 1))
               )
          )
    )
  )

; 偶数かどうか判定
(define (even? n)
  (= (remainder n 2) 0)
  )
; 動作確認
(fib 64)
; 動作確認
(fib 13)
; 動作確認
(+ 0.0 (/ (fib 64) (fib 63)))<jupyter_output>fib-iter(1,0,1,1,32)
fib-iter(1,0,2,3,16)
fib-iter(1,0,13,21,8)
fib-iter(1,0,610,987,4)
fib-iter(1,0,1346269,2178309,2)
fib-iter(1,0,6557470319842,10610209857723,1)
fib-iter(17167680177565,10610209857723,6557470319842,10610209857723,0)
fib-iter(1,1,0,1,62)
fib-iter(1,1,1,1,31)
fib-iter(3,2,1,1,30)
fib-iter(3,2,2,3,15)
fib-iter(21,13,2,3,14)
fib-iter(21,13,13,21,7)
fib-iter(987,610,13,21,6)
fib-iter(987,610,610,987,3)
fib-iter(2178309,1346269,610,987,2)
fib-iter(2178309,1346269,1346269,2178309,1)
fib-iter(10610209857723,6557470319842,1346269,2178309,0)
{'fraction_non_alphanumeric': 0.2299043062200957, 'fraction_numerical': 0.09114832535885167, 'mean_word_length': 2.5552721088435373, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '392685', 'license': 'CC0-1.0', 'n_tokens_mistral': 2638, 'n_tokens_neox': 2329, 'n_words': 286, 'path': 'exercises/1.19.ipynb', 'repo_name': 'tokits/sicp-study', 'size': '4180'}