Scheme - 手続きとその生成するプロセス(木構造再帰(黄金比とフィボナッチ数))

計算機プログラムの構造と解釈[第2版]
(翔泳社)
ハロルド エイブルソン (著)ジュリー サスマン (著)
ジェラルド・ジェイ サスマン (著)
Harold Abelson (原著)Julie Sussman (原著)
Gerald Jay Sussman (原著)和田 英一 (翻訳)

開発環境

• 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.2(木構造再帰)、問題 1.13.を解いてみる。

その他参考書籍

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

問題 1.13.

ѱ= (1 - √5) / 2とする。

n = 0のとき。

(ɸ^0 - ѱ^0) / √5 = 0

n = 1のとき。

(ɸ^1 - ѱ^1) / √5 = (ɸ - ѱ) / √5 = √5 / √5 = 1

また、次が成り立つ。

ѱ^2 = (6 - 2√5) / 4

ѱ^2 = (3 - 2√5) / 2

ѱ^2 = ѱ + 1

このことから次が成り立つ。

(ɸ^(k - 1) - ѱ^(k - 1)) / √5 + (ɸ^(k - 2) - ѱ^(k - 2)) / √5
= (ɸ^(k - 1) - ѱ^(k - 1) + ɸ^(k - 2) - ѱ^(k - 2)) / √5
= ((ɸ + 1) * ɸ^(k - 2) - (ѱ + 1) * ѱ^(k - 2)) / √5
= (ɸ^2 * ɸ^(k - 2) - ѱ^2 * ѱ^(k - 2)) / √5
= (ѱ^k - ѱ^k) / √5

よって帰納法により次が成り立つ。

Fib (n) = (ɸ^n - ѱ^n) / √5

ここまでの証明を使うと次のことが分かる。

0 <= |Fib(n) - ɸ^n / √5|
= |(ɸ^n - ѱ^n) / √5 - ɸ^n / √5|
= |ѱ|^n / √5
= ((√5 - 1) / 2)^ n / √5
< ((3 - 1) / 2)^ n / √5
= (2 / 2)^ n / √5
= 1 / √5
< 1 / 2

よって、Fib(n)は、ɸ^n / √5 に最も近い整数である。

確認。

コード(BBEdit, Emacs)

sample.scm

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

(define phi (/ (+ 1 (sqrt 5)) 2))

(define (fib n)
  (round (/ (expt phi n) (sqrt 5))))

(define (fib-1 n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

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

$ gosh
gosh> (load "./sample.scm")
#t
gosh> (fib 0)
0.0
gosh> (fib 1)
1.0
gosh> (fib 2)
1.0
gosh> (fib 3)
2.0
gosh> (fib 4)
3.0
gosh> (fib 5)
5.0
gosh> (fib 6)
8.0
gosh> (fib 7)
13.0
gosh> (fib 8)
21.0
gosh> (fib 9)
34.0
gosh> (fib 10)
55.0
gosh> (fib 100)
3.542248481792631e20
gosh> (fib-1 0)
0
gosh> (fib-1 1)
1
gosh> (fib-1 2)
1
gosh> (fib-1 3)
2
gosh> (fib-1 4)
3
gosh> (fib-1 5)
5
gosh> (fib-1 6)
8
gosh> (fib-1 7)
13
gosh> (fib-1 8)
21
gosh> (fib-1 9)
34
gosh> (fib-1 10)
55
gosh> (fib-1 100)
354224848179261915075
gosh> (exit)
$