Scheme - 手続きとその生成するプロセス(対数的ステップ数でFibonacci数を計算するアルゴリズム)

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• Gauche (処理系)

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の1(手続きによる抽象の構築)、1.2(手続きとその生成するプロセス)、1.2.4(べき乗)、問題 1.19.を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs
• プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)

問題 1.19.

1回使って出来上がる対を求める。

(bq + aq + ap, bp + aq)

さらにもう1回使って出来上がる対を求める。

((bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p, (bp + aq)p + (bq + aq + ap)q)
(b(2pq + q^2) + 2aq^2 + 2apq + ap^2, b(p^2 + q^2) + a(2pq + q^2))
(b(2pq + q^2) + a(2pq + q^2) + a(p^2 + q^2), b(p^2 + q^2) + a(2pq + q^2))

よって、変換Tpqを2回使うのと同じ効果になる、同じ形式の変換Tp'q'のp'、q'はそれぞれ p' = p^2 + q^2、q' = 2pq + q^2となる。

これで変換を2乗する方法が得られ、逐次平方を使いT^nを計算することが出来るようになり、これらを全てまとめ、対数的ステップ数の以下のフィボナッチ数を対数的ステップ数で計算する手続きを定義することが出来る。

コード(BBEdit, Emacs)

sample.scm

#!/usr/bin/env gosh
;; -*- coding: utf-8 -*-

(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
                   (+ (expt p 2)
                      (expt q 2))
                   (+ (* 2 p q)
                      (expt q 2))
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

(define (expt b n)
  (expt-iter b n 1))

(define (expt-iter b n a)
  (cond ((= n 0) a)
        ((even? n) (expt-iter (square b) (/ n 2) a))
        (else (expt-iter b (- n 1) (* a b)))))

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

(define (square x) (* x x))

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

$ gosh
gosh> (load "./sample.scm")
#t
gosh> (fib 0)
0
gosh> (fib 1)
1
gosh> (fib 2)
1
gosh> (fib 3)
2
gosh> (fib 4)
3
gosh> (fib 5)
5
gosh> (fib 6)
8
gosh> (fib 7)
13
gosh> (fib 8)
21
gosh> (fib 9)
34
gosh> (fib 10)
55
gosh> (fib 100)
354224848179261915075
gosh> (fib 101)
573147844013817084101
gosh> (fib 102)
927372692193078999176
gosh> (exit)
$