Scheme - 手続きとその生成するプロセス(正弦と近似、プロセスが使うスペースとステップ数の増加の程度)

計算機プログラムの構造と解釈
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.3(増加の程度)、問題 1.15.を解いてみる。

その他参考書籍

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

問題 1.15.

a.

1. 4.05
2. 1.35
3. 0.45
4. 0.15
5. 0.05

5回作用させられた。

確認。

コード(BBEdit, Emacs)

sample.scm

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

(load "./compound_procedures.scm")

(define (sine angle counter)
  (if (not (> (abs angle) 0.1))
      (begin (print counter) angle)
      (p (sine (/ angle 3.0) (inc counter)))))

(define (p x) (- (* 3 x) (* 4 (cube x))))

(print (sine 12.15 0))

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

$ ./sample.scm
5
-0.39980345741334
$

b.

a / 3^n <= 0.1

3^n = 10 * a

log3 3^n = log3 (10 * a)

n = log3 (10 * a)

また、プロセスが使うスペース数はステップ数と同じ。

よって、スペースとステップ数の増加の程度はΦ(log a)。