[SICP] 問題 1.29 : Simpsonの公式

Simpsonの公式は上に示したのより更に正確な数値積分法である.
Simpsonの公式を使えば, aからbまでの関数fの積分は, 偶整数nに対し, h = (b - a)/nまたy_k = f(a + kh)として

(h/3)[y₀ + 4y₁ + 2y₂ + 4y₃ + 2y₄ + ・・・ + 2y_n-2 + 4y_n-1 + y_n]

で近似出来る. (nの増加は近似の精度を増加する.)
引数としてf, a, bとnをとり, Simpson公式を使って計算した積分値を返す手続きを定義せよ. その手続きを使って(n = 100とn = 1000で)0から1までcubeを積分し, またその結果を上のintegral手続きの結果と比較せよ.

Simpsonの公式の大カッコの中身をじっと見つめると, 次のようなパターンが見えてきます.

(y₀ + 4y₁ + y₂) + (y₂ + 4y₃ + y₄) + ・・・ + (y_n-4 + 4y_n-3 + y_n-2) + (y_n-2 + 4y_n-1 + y_n)

y₂に注目してください. 公式では係数が2となっていますが, それを2つに分けています.

つまり, 大カッコの中は３つの項をひとまとめにするとスッキリと書けます. 手続きを定義します.

(require (lib "racket/trace.ss"))

(define (cube x) (* x x x))

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))

(define (integral f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b)
     dx))

(define (simpson f a b n)
  (define h (/ (- b a) n))
  (define (y k) (f (+ a (* k h))))
  (define (term k) (+ (y k) (* 4.0 (y (+ k 1))) (y (+ k 2))))
  (define (next k) (+ k 2))
  (* (/ h 3.0)
     (sum term 0 next (- n 2))))

0から1までのcubeを積分してみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (integral cube 0 1 0.01)
0.24998750000000042
> (integral cube 0 1 0.001)
0.249999875000001
> (simpson cube 0 1 100)
0.2500000000000001
> (simpson cube 0 1 1000)
0.2500000000000001
> 

計算結果を見ると精度が全く異なっています.

[SICP] 問題 1.17 : 対数的ステップ数の乗算手続き（再帰的プロセス）

本節のべき乗アルゴリズムは, 乗算の繰返しによるべき乗の実行に基づいていた. 同様に整数の乗算を加算の繰返しで実行出来る. 次の乗算手続きは(この言語には加算はあるが, 乗算はないと仮定する)expt手続きに似たものである:

(define (* a b)
  (if (= b 0)
      0
      (+ a (* a (- b 1)))))

このアルゴリズムはbに線形のステップ数をとる. 加算の他に整数を二倍するdouble演算と(偶数の)整数を2で割るhalve演算もあるとしよう. これらを使い, fast-exptと類似の対数的ステップ数の乗算手続きを設計せよ.

p.25のfast-exptを参考に手続きを定義します.

(require (lib "racket/trace.ss"))

(define (double x) (* x 2))

(define (halve x) (/ x 2))

(define (fast-mult a b)
  (cond ((< b 0) (* -1 (fast-mult a (abs b))))
        ((= b 0) 0)
        ((= b 1) a)
        ((even? b) (double (fast-mult a (halve b))))
        (else (+ a (fast-mult a (- b 1))))))

(trace fast-mult)

fast-exptと同じような構造をしています. 負の数をかけた場合と０をかけた場合の扱いを追加しています.

a×bの計算について, 奇数と偶数の場合に分けて, 計算をどのように進めるかを考えます.

1) bが奇数の場合, b = m+1とする. 次の式が成立する.

a×(m+1) = a + (a×m)

2) nが偶数の場合, b = 2mとする. 次の式が成立する.

a×(2m) = double(a×m)

実行結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (fast-mult 3 45)
>(fast-mult 3 45)
> (fast-mult 3 44)
> >(fast-mult 3 22)
> > (fast-mult 3 11)
> > >(fast-mult 3 10)
> > > (fast-mult 3 5)
> > > >(fast-mult 3 4)
> > > > (fast-mult 3 2)
> > > > >(fast-mult 3 1)
< < < < <3
< < < < 6
< < < <12
< < < 15
< < <30
< < 33
< <66
< 132
<135
135
> (fast-mult 4 0)
>(fast-mult 4 0)
<0
0
> (fast-mult 5 -8)
>(fast-mult 5 -8)
> (fast-mult 5 8)
> >(fast-mult 5 4)
> > (fast-mult 5 2)
> > >(fast-mult 5 1)
< < <5
< < 10
< <20
< 40
<-40
-40
> 

トレースの結果から、対数的ステップ数で計算していることが分かります.

[SICP] 問題 1.16 : べき乗を求める反復的アルゴリズム

fast-exptのように, 逐次平方を使い, 対数的ステップ数の反復的べき乗プロセスを生成する手続きを設計せよ.

(ヒント: (b^n/2)² = (b²)^n/2に注意し, 指数nと底bの他にもう一つの状態変数aを用意する.
状態の移変りで積abⁿが不変であるように状態遷移を定義する.
プロセス開始時にaを1とし, プロセス終了時にaが結果になるようにする.
一般に, 状態の移変りに不変のままの不変量(invariant quantity)を定義する技法は, 反復的アルゴリズムの設計に有用である.)

問題文のヒントを参考に手続きを定義します.

(require (lib "racket/trace.ss"))

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

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

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

(trace fast-expt-iter)

p×bⁿを考え, pに結果をため込むようにします. 奇数と偶数の場合に分けて, pとbがどのように変化するかを考えます.

1) nが奇数の場合, n = m+1とする. 次の式が成立する.

p×b^m+1 = (p×b)×b^m

右辺のカッコ内の(p×b)が次のステップのpとなる.

2) nが偶数の場合, n = 2mとする. 次の式が成立する.

p×b^2m = p×(b²)^m

右辺のカッコ内の(b²)が次のステップのbとなる.

実行結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (fast-expt 2 8)
>(fast-expt-iter 2 8 1)
>(fast-expt-iter 4 4 1)
>(fast-expt-iter 16 2 1)
>(fast-expt-iter 256 1 1)
>(fast-expt-iter 256 0 256)
<256
256
> 

トレースの結果から, 反復的プロセスを生成しており, 対数的ステップ数で計算していることが分かります.

[SICP] 問題 1.15 : 正弦の計算

(ラジアンで表す)角度の正弦は, xが十分小さい時, sin x ≒ xの近似と, 正弦の引数の値を小さくするための三角関係式

sin(x) = 3sin(x/3) - 4sin³(x/3)

を使って計算出来る. (この問題のためには, 角度の大きさが0.1ラジアンより大きくなければ「十分小さい」と考える.) この方法は次の手続きに採用してある:

(define (cube x) (* x x x))

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

(define (sine angle)
   (if (not (> (abs angle) 0.1))
       angle
       (p (sine (/ angle 3.0)))))

a. (sine 12.15)の評価で, 手続きpは何回作用させられたか.

b. (sine a)の評価で, 手続きsineの生成するプロセスが使うスペースとステップ数の増加の程度は(aの関数として)何か.

問題文の手続きを定義します. 手続きpを作用させた回数を調べるためにトレースを使います.

(require (lib "racket/trace.ss"))

(define (cube x) (* x x x))

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

(define (sine angle)
  (if (not (> (abs angle) 0.1))
      angle
      (p (sine (/ angle 3.0)))))

(trace p)

計算結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (sin 12.5)
-0.06632189735120068
> (sine 12.5)
>(p 0.051440329218107005)
<0.153776521096694
>(p 0.153776521096694)
<0.4467840153484446
>(p 0.4467840153484446)
<0.9836111719853284
>(p 0.9836111719853284)
<-0.8557060643295382
>(p -0.8557060643295382)
<-0.060813768577286265
-0.060813768577286265
> 

トレースの結果から, pを作用させた回数は５回です.

手続きの定義から, aの値が0.1より大きい時は手続きを再帰的に呼び出し, 次のaの値は1/3になっています. 「十分小さい」と判断する値をe, ステップ数をnとすると次の関係が成り立ちます.

(a/3)n	<	e
a/e	<	3n
log3(a/e)	<	n

このことから, ステップ数の増加の程度はlog aであるといえます. また, 手続きは末尾再帰になっていないため, スペースの増加の程度もステップの増加の程度と同じです.

[筋トレ] 2014.10.20の週

今週の記録です。

10/21（火）74.05kg
　スクワット　　　２０、２０　　（5kgの鉄アレイ）
　リアレイズ　　　１５、　８　　（5kgの鉄アレイ）
　レッグレイズ　　１０、　７

10/22（水）73.85kg
　プッシュアップ　１７、　７　　（膝をついた状態）
　ナロースタンス　　０　　　　　（両手の間を拳一つ開けた状態）
　アームカール　　　６、　４　　（10kgのダンベル）

10/24（金）75.40kg
　スクワット　　　２０、２０　　（5kgの鉄アレイ）
　リアレイズ　　　１２、　７　　（5kgの鉄アレイ）
　レッグレイズ　　１３、　５

10/26（日）75.65kg
　プッシュアップ　１６、　４　　（膝をついた状態）
　ナロースタンス　　２、　３　　（両手の間を拳一つ開けた状態）
　アームカール　　　６、　４　　（10kgのダンベル）

スクワットとアームカールに使うウエイトを増やしました。スクワットは20回できてしまうので、ウエイトを増やしても良さそうです。

リアレイズについては、正しいフォームを意識したため、回数が減っています。数をこなせば良いというものではないはずです。

トレーニングは、朝にしており、体重は夜、風呂を上がった後で量っています。金曜日は飲み会だったので、体重は多めです。

更に、土日の夕食がおでんだったので、体重は増える一方です(~_~;)

[SICP] 問題 1.14 : 両替の計算が生成するプロセス

1.2.2節のcount-change手続きが11セントの両替の場合に生成するプロセスを示す木構造を描け. 両替の金額の増加につれ, このプロセスが使うスペースとステップ数の増加の程度は何か.

図を書きます. 木の節点に金額と両替に使えるコインを括弧付きで描いています.

 11 -----------------  -39
(50, 25, 10, 5, 1)     (50, 25, 10, 5, 1)
  |
  |
 11 -----------------  -14
(25, 10, 5, 1)         (25, 10, 5, 1)
  |
  |
 11 --------- 1 ------  -9
(10, 5, 1)  (10, 5, 1) (10, 5, 1)
  |           |
  |           |
  |           1 ------  -4
  |          (5, 1)     (5, 1)
  |           |
  |           |
  |           1  ------  0
  |          (1)        (1)
  |
 11 --------  6 -------  1 ----  -4
 (5, 1)      (5, 1)     (5, 1)   (5, 1)
  |           |          |
  |           |          |
  |           |          1 -----  0
  |           |         (1)      (1)
  |           |          |
  |           |          |
  |           |          1
  |           |         ( )
  |           |
  |           6 -- 5 -- 4 -- 3 -- 2 -- 1 -- 0
  |          (1)  (1)  (1)  (1)  (1)  (1)  (1)
  |           |    |    |    |    |    |
  |           |    |    |    |    |    |
  |           6    5    4    3    2    1
  |          ( )  ( )  ( )  ( )  ( )  ( )
  | 
 11 -- 10 -- 9 -- 8 -- 7 -- 6 -- 5 -- 4 -- 3 -- 2 -- 1 -- 0
 (1)   (1)  (1)  (1)  (1)  (1)  (1)  (1)  (1)  (1)  (1)  (1)
  |     |    |    |    |    |    |    |    |    |    |
  |     |    |    |    |    |    |    |    |    |    |
 11    10    9    8    7    6    5    4    3    2    1
 ( )   ( )  ( )  ( )  ( )  ( )  ( )  ( )  ( )  ( )  ( )

このプロセスが使うスペースとステップ数の増加の程度については後で考えます.

[SICP] 問題 1.13 : フィボナッチ数を求める代数方程式

Φ= (1+√5)/2としてFib(n)がΦⁿ/√5に最も近い整数であることを証明せよ. ヒント: Ψ= (1-√5)/2とする. 帰納法とFibonacci数の定義(1.2.2節参照)を用い, Fib(n)=(Φⁿ-Ψⁿ)/√5を証明せよ.

まず, Fib(n)=(Φⁿ-Ψⁿ)/√5を証明する.

(1) n=1のとき

Fib(1)	=	{Φ1-Ψ1} / √5
	=	{(1+√5)/2 - (1-√5)/2} / √5
	=	2√5 / √5
	=	1

(2) n=2のとき

Φ2	=	{(1+√5)/2}2
	=	{1 + 2√5 + 5} / 4
	=	{2 + 2√5 + 4} / 4
	=	{1 + √5} / 2 + 1
	=	Φ + 1

Ψ2	=	{(1-√5)/2}2
	=	{1 - 2√5 + 5} / 4
	=	{2 - 2√5 + 4} / 4
	=	{1 - √5} / 2 + 1
	=	Ψ + 1

Fib(2)	=	{Φ2-Ψ2} / √5
	=	{(Φ + 1) - (Ψ + 1)} / √5
	=	{Φ - Ψ} / √5
	=	1

(3) n=k, k+1のときFib(n)=(Φⁿ-Ψⁿ)/√5が成立すると仮定する. n=k+2のとき

Fib(k+2)	=	Fib(k+1) + Fib(k)
	=	(Φk+1-Ψk+1)/√5 + (Φk-Ψk)/√5
	=	{(Φk+1+Φk) - (Ψk+1+Ψk)} / √5
	=	{Φk(Φ+1) - Ψk(Ψ+1)} / √5
	=	{ΦkΦ2 - ΨkΨ2} / √5
	=	{Φk+2 - Ψk+2} / √5

(4) 以上より, 1以上の整数nについて, Fib(n)=(Φⁿ-Ψⁿ)/√5が成立する.

次に, Ψ/√5の値を計算する.

Ψ/√5 = (1-√5)/2 ≒ -0.2764

Ψ/√5 < 1/2 であるから, 1以上の整数nについて, Ψⁿ/√5 < 1/2 である.
よって、Fib(n)がΦⁿ/√5に最も近い整数であるといえる.

[SICP] 問題 1.12 : Pascal三角形

次の数のパターンをPascal三角形(Pascal's triangle)という.

       1
      1 1
     1 2 1
    1 3 3 1
   1 4 6 4 1
      ...

三角形の辺上の数はすべて1, 三角形の内部の数はその上の二つの数の和である. 再帰的プロセスの方法でPascal三角形の要素を計算する手続きを書け.

Pascal三角形を計算する手続きを定義します. 結果の確認を容易にするための手続きも定義します.

(define (pascal x y)
  (cond ((= x 0) 1)
        ((= y 0) 1)
        ((= x y) 1)
        (else (+ (pascal (- x 1) (- y 1))
                 (pascal (- x 1) y)))))

;; 1からnまでの整数のリストを求める.
(define (int-list n)
  (define (loop result counter)
    (if (< counter 0)
        result
        (loop (cons counter result) (- counter 1))))
  (loop '() n))

;; 9行分のPascal三角形を求める.
(map (lambda (x)
       (map (lambda (y) (pascal x y)) (int-list x)))
     (int-list 8))

実行した結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
((1)
 (1 1)
 (1 2 1)
 (1 3 3 1)
 (1 4 6 4 1)
 (1 5 10 10 5 1)
 (1 6 15 20 15 6 1)
 (1 7 21 35 35 21 7 1)
 (1 8 28 56 70 56 28 8 1))
> 

Pascal三角形を計算できていることを確認できます.

[SICP] 問題 1.11 : f(n)=f(n-1)+2f(n-2)+3f(n-3)

n<3に対して

  f(n)=n, n ≥ 3に対してf(n)=f(n - 1) + 2f(n - 2) + 3f(n - 3)

なる規則で定義する関数fがある. 再帰的プロセスの方法でfを計算する手続きを書け. 反復的プロセスの方法でfを計算する手続きを書け.

Fibonacci数を計算する手続きを参考にして問題文の関数fを定義します.

(require (lib "racket/trace.ss"))

(define (f-r n)
  (if (< n 3)
      n
      (+ (* 1 (f-r (- n 1)))
         (* 2 (f-r (- n 2)))
         (* 3 (f-r (- n 3))))))

(define (f-iter counter x y z)
  (if (= 0 counter)
      z
      (f-iter (- counter 1)
              (+ x (* 2 y) (* 3 z))
              x 
              y)))

(define (f-i n)
  (f-iter n 2 1 0))

;;(trace f-r f-iter)

実行して, 結果を確認します.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (map f-r '(0 1 2 3 4 5 6 7))
(0 1 2 4 11 25 59 142)
> (map f-i '(0 1 2 3 4 5 6 7))
(0 1 2 4 11 25 59 142)
> 

手続きf-rとf-iterをトレースして, 手続きが生成するプロセスを確認します.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (f-r 5)
>(f-r 5)
> (f-r 4)
> >(f-r 3)
> > (f-r 2)
< < 2
> > (f-r 1)
< < 1
> > (f-r 0)
< < 0
< <4
> >(f-r 2)
< <2
> >(f-r 1)
< <1
< 11
> (f-r 3)
> >(f-r 2)
< <2
> >(f-r 1)
< <1
> >(f-r 0)
< <0
< 4
> (f-r 2)
< 2
<25
25
> (f-i 5)
>(f-iter 5 2 1 0)
>(f-iter 4 4 2 1)
>(f-iter 3 11 4 2)
>(f-iter 2 25 11 4)
>(f-iter 1 59 25 11)
>(f-iter 0 142 59 25)
<25
25
> 

トレースの結果から, f-rが再帰的プロセスを生成し, f-iが反復的プロセスを生成していることが分かります.

[SICP] 問題 1.10 : Ackermann関数

次の手続きはAckermann関数という数学関数を計算する.

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

次の式の値は何か.

(A 1 10)

(A 2 4)

(A 3 3)

Aを上で定義した手続きとして, 次の手続きを考える.

(define (f n) (A 0 n))

(define (g n) (A 1 n))

(define (h n) (A 2 n))

(define (k n) (* 5 n n))

正の整数nに対して手続きf, gおよびhが計算する関数の簡潔な数学的定義を述べよ. 例えば(k n)は5n²を計算する.

Ackermann関数を定義します.

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

問題文の例を計算してみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (A 1 10)
1024
> (A 2 4)
65536
> (A 3 3)
65536
> 

次の手続きf, g, hが計算する関数の簡潔な数学的定義を考えます. まず, 手続きを定義します.

(define (f n) (A 0 n))

(define (g n) (A 1 n))

(define (h n) (A 2 n))

手続きを使っていくつかの例を計算して結果を観察します. 見通しを良くするために, ２章で扱う手続きを使ってズルをします.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (map f '(1 2 3 4 5 6 7 8))
(2 4 6 8 10 12 14 16)
> (map g '(1 2 3 4 5 6 7 8))
(2 4 8 16 32 64 128 256)
> (map h '(1 2 3 4))
(2 4 16 65536)
> 

計算結果とAckermann関数の定義から, 次のような関係がありそうです.

関数の表記を一般的な表記で書きます.

  f(n) = A(0, n) 
       = 2 * n

Ackermann関数の引数xが0の場合に相当するため, 引数yの値を2倍した結果を返します. このことから, f(n)=2nといえます.

Ackermann関数の定義とf(n)の結果から, g(n)は次のように変形できます.

  g(n) = A(1, n)
       = A(0, A(1, (n - 1)))
       = 2 * A(1, (n - 1))
       = 2 * A(0, A(1, (n - 2)))
       = 2 * 2 * A(1, (n - 2))
       = 2 * 2 * ・・・・・ * 2 * A(1, 1)
       = 2 * 2 * ・・・・・ * 2 * 2

この結果から, g(n)は2をn回掛けています. このことから, g(n)=2ⁿといえます.

Ackermann関数の定義とg(n)の結果から, h(n)は次のように変形できます. ここでは, 2ⁿを2^nと記述しています.

  h(n) = A(2, n)
       = A(1, A(2, (n - 1)))
       = 2 ^ A(2, (n - 1))
       = 2 ^ A(1, A(2, (n - 2)))
       = 2 ^ 2 - A(1, (n - 2))
       = 2 ^ 2 ^ ・・・・・ ^ 2 ^ A(2, 1)
       = 2 ^ 2 ^ ・・・・・ ^ 2 ^ 2

この結果から, h(n)は2の2乗の2乗の・・・・をn回繰り返したものです. 例えば, h(5)は上で求めたh(4)の結果を使うと次のようになります.

  h(5) = A(2, 5)
       = A(1, 65536)
       = 2 ^ 65536

つまり, 2⁶⁵⁵³⁶を計算することになります. 実際に計算してみた結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (A 2 5)
2003529930406846464979072351560255750447825475569751419265016973710894
0595563114530895061308809333481010382343429072631818229493821188126688
6950636476154702916504187191635158796634721944293092798208430910485599
0570159318959639524863372367203002916969592156108764948889254090805911
4570376752085002066715637023661263597471448071117748158809141357427209
6719015183628256061809145885269982614142503012339110827360384376787644
9043205960379124490905707560314035076162562476031863793126484703743782
9549756137709816046144133086921181024859591523801953310302921628001605
6867010565164675056803874152946384224484529253736144253361437372908830
3794601274724958414864915930647252015155693922628180691650796381064132
2753072671439981585088112926289011342377827055674210800700652839633221
5507783121428855167555407334510721311242739956298271976915005488390522
3804357045848197956393157853510018992000024141963706813559840464039472
1940160695176901561197269823378900176415171900511334663068981402193834
8143542638730653955296969138802415816185956110064036211979610185953480
2787167200122604642492385111393400464351623867567078745259464670903886
5477434832178970127644555294090920219595857516229733335761595523948852
9757995402847194352991354376370598692891375715374000198639433246489005
2543106629669165243419174691389632476560289415199775477703138064781342
3095961909606545913008901888875880847336259560654448885014473357060588
1709016210849971452956834406197969056546981363116205357936979140323632
8496233046421066136200220175787851857409162050489711781820400187282939
9434461862243280098373237649318147898481194527130074402207656809103762
0399920349202390662626449190916798546151577883906039772075927937885224
1294301017458086862263369284725851403039615558564330385450688652213114
8136384083847782637904596071868767285097634712719888906804782432303947
1865052566097815072986114143030581692792497140916105941718535227588750
4477592218301158780701975535722241400019548102005661773589781499532325
2085897534635470077866904064290167638081617405504051176700936732028045
4933902799249186730653993164072049223847481528061916690093380573212081
6350707634351669869625020969023162859350071874190579161241536897514808
2619048479465717366010058924766554458408383347905441448176842553272073
1558634934760513741977952519036503219802010876473836868253102518337753
3908861426184800374008082238104076468878471647552945326947661700424461
0633112380211345886945322001165640763270230742924260515828110703870183
4532456763562595143003203743274078087905628366340696503084422585596703
9271869461158513793386475699748568670079823960604393478850861649260304
9450617434123658283521448067266768418070837548622114082365798029612000
2744132443843240233125740354501935242877643088023285085588608996277445
8164680857875115807014743763867976955049991643998284357290415378143438
8473034842619033888414940313661398542576355771053355802066221855770600
8255128889333222643628198483861323957067619140963853383237434375883085
9233722284644287996245605476932428998432652677378373173288063210753211
2386806046747084280511664887090847702912081611049125555983223662448685
5665140268464120969498259056551921618810434122683899628307165486852553
6914850299539675503954938371853405900096187489473992880432496373165753
8036735867101757839948184717984982469480605320819960661834340124760966
3951977802144119975254670408060849934417825628509272652370989865153946
2193004607364507926212975917698293892367015170992091531567814439791248
4757062378046000099182933213068805700465914583872080880168874458355579
2625846512476308714856631352893416611749061752667149267217612833084527
3936469244582892571388877839056300482483799839692029222215486145902373
4782226825216399574408017271441461795592261750838890200741699262383002
8228624928418267124340575142418856999427233160699871298688277182061721
4453142574944015066139463169197629181506579745526236191224848063890033
6690743659892263495641146655030629659601997206362026035219177767406687
7746354937531889958786628212546979710206574723272137291814466665942187
2003474508942830911535189271114287108376159222380276605327823351661555
1493693757784666701457179719012271178127804502400263847587883393968179
6295069079881712169068692953824852983002347606845411417813911064856023
6549754227497231007615131870024053910510913817843721791422528587432098
5249578780346837033378184214440171386881242499844186181292711985333153
8256732187042153063119774853521467095533462633661086466733229240987984
9256691109516143618601548909740241913509623043612196128165950518666022
0307156136847323646608689050142639139065150639081993788523183650598972
9912540447944342516677429965981184923315155527288327402835268844240875
2811283289980625912673699546247341543333500147231430612750390307397135
2520693381738433229507010490618675394331307847980156551303847581556852
3621801041965025559618193498631591323303609646190599023611268119602344
1843363334594927631946101716652913823717182394299216272538461776065694
5422978770713831988170369645886898118632109769003557358846244648357062
9145305275710127887202796536447972402540544813274839179412882642383517
1949197209797145936887537198729130831738033911016128547415377377715951
7280841116275971863849242228023734419254699919836721921312870355853079
6694271341639103388275431861364349010094319740904733101447629986172542
4423355612237435715825933382804986243892498222780715951762757847109475
1190334822414120251826887137281931042534781961284401764795315050571107
2297431456991522345164312184865757578652819756484350895838472292353455
9464521215831657751471298708225909292655638836651120681943836904116252
6687100445602437042006637090019411855571604720446436969328500600469281
4050711906926139399390273553454556747031490388602202463994826050176243
1969305640666366626090207048887438898907498152865444381862917382901051
8208699363826618683039152732645812867828066013375000965933646251460917
2318031293034787742123467911845479131110989779464821692250562939995679
3483801699157439700537542134485874586856047286751065423341893839099110
5864655951136460610551568385412174598018071331636125730796111683438637
6766730735458349478978831633012924080083635682593915711313097803051644
1716682518346573675934198084958947940983292500086389778563494693212473
4261030627137450772861569225966285738579055332406418490184513282846327
0926975383086730840914224765947443997334813081098639941737978965701068
7026734161967196591599588537834822988270125605842365589539690306474965
5841479813109971575420432563957760704851008815782914082507777385597901
2912940730946278594450585941227319481275322515232480150346651904822896
1406646890305102510916237770448486230229488966711380555607956620732449
3733740278367673002030116152270089218435156521213792157482068593569207
9021450227713309998772945959695281704458218195608096581170279806266989
1205061560742325686842271306295009864421853470810407128917646906550836
1299166947780238225027896678434891994096573617045867862425540069425166
9397929262471452494540885842272615375526007190433632919637577750217600
5195800693847635789586878489536872122898557806826518192703632099480155
8744555751753127364714212955364940843855866152080121150790750685533444
8925869328385965301327204697069457154695935365857178889486233329246520
2735853188533370948455403336565356988172582528918056635488363743793348
4118455801683318276768346462919956055134700391478768086403226296166415
6066750815371064672310846196424753749055374480531822600271021640098058
4497526023035640038083472053149941172965736785066421400842696497103241
9191821212132069397691439233683747092282677387081322366800869247034915
8684099115309831541206356612318750430546753698323082796645741762080659
3177265685841681837966106144963432544111706941700222657817358351259821
0807691019610522292638797450490192543119006205619065774524161919131875
3398404934397682331029846589331837301580959252282920682086223033258528
0119266496314441316442773003237792274712330696417149945532261035475145
6312906688543454268697884477429817774937101176146516241836166802548152
9633530849084994300676365480610294009469375060984558855804397048591444
9584445079978497045583550685408745163316464118083123079704389849190506
5875864258107384224205911919416741824904527002882639830579500573417114
8703118714283418449915345670291528010448514517605530697144176136858238
4102787659324662689978418319620312262421177391477208004883578333569204
5339359532545648970285585897355057512351295365405028420810227852487766
0357424636667314868027948605244578267362623085297826505711462484659591
4210278122788941448163994973881884622768244851622051817076722169863265
7016543169197426512300417573299044735376725368457927543654128265535818
5804684006936771860502007054724754840080553042495185449526724726134731
8174742180078574693465447136036975884118029408039616746946288540679172
1386012254195038197045384172680063988206563287928395827085109199588394
4829777564715202613287108952616341770715164289948795356485455355314875
4978134009964854498635824847690590033116961303766127923464323129706628
4113074270462020320133683503854253603136367635752126047074253112092334
0283748294945310472741896928727557202761527226828337674139342565265328
3068469997597097750005560889932685025049212884068274139881631540456490
3507758716800740556857240217586854390532281337707074158307562696283169
5568742406052772648585305061135638485196591896864959633556821697543762
1430778665934730450164822432964891270709898076676625671517269062058815
5496663825738292741820822789606844882229833948166709840390242835143068
1376725346012600726926296946867275079434619043999661897961192875051944
2356402644303271737341591281496056168353988188569484045342311424613559
9252723300648816274667235237512343118934421188850850793581638489944875
4475633168921386967557430273795378526254232902488104718193903722066689
4702204258836895840939998453560948869946833852579675161882159410981624
9187418133647269651239806775619479125579574464714278686240537505761042
0426714936608498023827468057598259133100691994190465190653117190892607
7949119217946407355129633864523035673345588033313197080365457184791550
4326548995597058628882868666066180218822486021449999731221641381706534
8017551043840662441282280361664890425737764095632648282525840766904560
8439490325290526337532316509087681336614242398309530806549661879381949
1200339194894940651323988166420800883955549422370967348400726427057011
6508907519615537018626479745638118785617545711340047381076276301495330
9735174180655479112660938034311378532532883533352024934365979129341284
8549709468263290758301930726653377825593143311109638480539408592839889
0779621047984791968687653998747709591278872747587443980677982496827827
2200926449944559380414608770641941810440758269805688038949654616587983
9046605876453418102899071942930217745199761044950431968415034555140448
2092893337865736305283061999007774872692299860827905317169187657886090
8941817057993404890218441559791092676862796597583952483926734883634745
6516870161662406424242412289611180106156823425393921800524834547237792
1991122859591419187749179382334001007812832650671028178139602912091472
0100947878752551263372884222353869490067927664511634758101193875319657
2421214760382847747745717045786104173857479113019085838778901523343430
1300528279703858035981518292960030568261209195094373732545417105638388
7047528950563961029843641360935641632589408137981511693338619797339821
6707610046079800960160248230969430438069566201232136501405495862506152
8258803302290838581247846931572032323360189946943764772672187937682643
1828382603564520699468630216048874528424363593558622333506235945002890
5585816112753417837504559361261308526408280512138731774902002495527387
3458595640516083058305377073253397155262044470542957353836111367752316
9972740292941674204423248113875075631319078272188864053374694213842169
9288629404796353051505607881263662064972312575790195988730411956262273
4372890051656111109411174527796548279047125058199907749806382155937688
5546498822938985408291325129076478386322494781016753491693489288104203
0156102833861438273781609463413353835783407653143214171506558775478202
5245478065730134227747061674424196895261316427410469547462148375628829
9771804186785084546965619150908695874251184435837306590951460980451247
4094113738999278224929833677960110153870961297497055663016373072027507
3475992294379239382442742118615823616131788639255309511718842129850830
7238259729144142251579403883011359083331651858234967221259621812507058
1137594955250227472746743698871319266707692991990844671612287388584575
8462272657333075373557282395161696417519867501268174542932373829414382
4814377139861906716657572945807804820559511881687188075212971832636442
1553367877512747669407901170575098195750845635652173895441798750745238
5445520013357203333237989507439390531291821225525983379090946363020218
5353848854825062897715616963860712382771725621313460549401770413581731
9317633701363322528191275471914434509207118488383668181742633429496118
7009150304916533946476371776643912079834749462739782217150209067019030
2469762151278521956142070806461631373236517853976292092025500288962012
9701413796400380557349492690735351459612086747965477336929587736286356
6014376796403843079686413856344780132826128458918489852804804884418082
1639423974014362903481665458114454366460032490618763039502356402044530
7482102413668951966442213392007574791286838051751506346625693919377402
8351207566626082989049187728783385217852279204577184696585527879044756
2192663992008409302075673925363735628390829817577902153202106409617373
2835984940666521411981838108845154597728951645721318977979074919410131
4836854463961690460703010759681893374121757598816512700076126278916951
0406315857637534787420070222051070891257612361658026806815858499852631
4658780866168007332646768302063916972030648944056281954061906852420030
5346315662189132730906968735318164109451428803660599522024824888671155
4429104721929134248346438705368508648749099178812670565665387191049721
8200423714927401644609434598453925367061322106165330856620211889682340
0575267548610147699368873820958455221157192347968688816085363161586288
0150395949418529489227074410828207169303387818084936204018255222271010
9856534448172074707560192459155994310729495781978785905789400525401228
6751714251118435643718405356302418122547326609330271039796809106493927
2722683035410467632591355279683837705019855234621222858410557119921731
7179698043393177077507556270560478317798444476375602546370333692471142
2081551997369137197516324130274871219986340454824852457011855334267526
4715978310731245663429805221455494156252724028915333354349341217862037
0072603152798707718724912344944771479095207347613854254853115527733010
3034247683586549609372232400715451812973269208105842409055772564580368
1462234493189708138897143299831347617799679712453782310703739151473878
6921191875667003193212818968033226965944592862106074388274169194651622
6763254066507088107103039417886056489376981673415902592519461182364294
5652669372203155504700213598846292758012527715422016629954863130324912
3110296279237238997664168034971412265279319076363261368141455163766565
5983978848938173308266877990196288693229659737995193162118721545528739
4170243669885593888793316744533363119541518404088283815193421234122820
0309503133410507047601599879854725291906652224793197154403317948368373
7322082188577334162385644138070054191353024594391350255453188645479625
2260251762928374330465102361057583514550739443339610216229675461415781
1271970017386114942795014112532806212547758105129720884652631580948066
3368767014731073354071771087661593585681409821296773075919738297344144
5256688770855324570888958320993823432102718224114763732791357568615421
2528496579033350931527769255058456440105521926445053120737562877449981
6364633283581614033017581396735942732769044892036188038675495575180689
0058532927201493923500525845146706982628548257883267398735220457228239
2902071448222198855871028969919358730742778151597576207640239512438602
0203259659625021257834995771008562638611823381331850901468657706401067
6278617583772772895892746039403930337271873850536912957126715066896688
4938808851429436099620129667590792250822753138128498515269029317002631
3632894209579757795932763553116206675348865131732387243874806351331451
2644889967589828812925480076425186586490241111127301357197181381602583
1785069322440079986566353715440884548663931817083957357807990597308390
9488180406093595919090747396090441015051632174968141210076571917748376
7355751000733616922386537429079457803200042337452807566153042929014495
7806296341383835517835997647088513490048569736979652386958459945955920
9070905895689145114141268450546211794502661175016692826025095077077821
1950432617383223562437601776799362796099368975191394965033358507155418
4364568526166742436889203710374953284259271316105378349807407391586338
1796765842525803673720646935124865223848134166380806150570482905989069
6451936440018597120425723007316410009916987524260377362177763430621616
7448849308109299010095179745415642512048220867145868492551324442667771
2786372821133153622430109182439124338021404624222334915355951689081628
8487989988273630445372432174280215755777967021666317047969728172483392
8410156422745072717792693999297403080727703950135815451424940490265361
0582540937311465310494338248437971860693721444460082679800247122948940
5761853892203425608302697052876621377373594394224114707074072902725461
3073585417456914194464876243576823970657031841684675407334663462936739
8362000404140071405427763248013274220268539369886978760700959004868465
0626771363070979821006557285101306601010780633743344773073478653881742
6812307437660666433127753564665786037151929227684404582732832438082128
4121877613204246046490080105473142674926082692215563740548624171703102
7919996942645620955619816454547662045022411449404749349832206807191352
7679867478134582038595704134661779372285349400316315995440936840895725
3343870298671782977037333280680176463950209002394193149911500910527682
1119510999063166150311585582835582607179410052528583611369961303442790
1738117874120612881820620232638498615156564512300477929675636183457681
0504334176954306753804111392855379252924134733948105053202570872818630
7291158911335942014761872664291564036371927602306283840650425441742335
4645499870553187268879264241021473636986254637471597443549434438997300
5174252511087735788639094681209667342815258591992485764048805507132981
4299359911463239919113959926752576359007446572810191805841807342227734
7213977232182317717169164001088261125490933611867805757223910181861685
4910850088527227437421208652485237245624869766224538481929867112945294
5515497030585919307198497105414181636968976131126744027009648667545934
5670599369954645005589216280479763656861333165639073957032720343891754
1526750091501119885687270884819553167693168127289214303137681801644547
7367518353497857924276463354162433601125960252109501612264110346083465
6482355979342740568688492244587454937767521203247038030354911575448312
9527589193989368087632768543876955769488142284431199859570072752139317
6837831770339130423060958999137314684569010422095161967070506420256733
8734461156552761759927271518776600102389447605397895169457088027287362
2512107622409181006670088347473760515628553394356584375627124124445765
1663064085939507947550920463932245202535463634444791755661725962187199
2791865754908578529500128402290350615149373101070094461510116137124237
6142672254173205595920278212932572594714641722497732131638184532655527
9604270541871496236585252458648933254145062642337885651464670604298564
7819684615936632889542997807225422647904006160197519750074605451500602
9180663827149701611098795133663377137843441619405312144529185518013657
5558667615019373029691932076120009255065081583275508499340768797252369
9870235679310268041367457189566414318526790547171699629903630155456450
9004480278905570196832831363071899769915316667920895876857229060091547
2919636381673596673959975710326015571920237348580521128117458610065152
5988838431145118948805521291457756991465775300413847171245779650481758
56395072895337539755822087777506072339445587895905719156736
> 

何も準備せずにこういう計算をできるので, Schemeは便利＼(^o^)／

[SICP] 問題 1.09 : 反復的プロセスと再帰的プロセス

次の二つの手続きはどちらも, 引数を1増やす手続きincと, 引数を1減らす手続きdecを使って, 二つの正の整数を足す方法を定義している.

(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))

(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

置換えモデルを使い, それぞれの手続きが(+ 4 5)を評価する時に生成するプロセスを示せ. そのプロセスは反復的か再帰的か.

置き換えモデルを使い, 生成するプロセスを書いてみます. まず1つ目の手続きが生成するプロセスです.

  (+ 4 5)
= (inc (+ 3 5))
= (inc (inc (+ 2 5)))
= (inc (inc (inc (+ 1 5))))
= (inc (inc (inc (inc (+ 0 5)))))
= (inc (inc (inc (inc 5))))
= (inc (inc (inc 6)))
= (inc (inc 7))
= (inc 8)
= 9

次に, 2つ目の手続きが生成するプロセスです.

  (+ 4 5)
= (+ 3 6)
= (+ 2 7)
= (+ 1 8)
= (+ 0 9)
= 9

処理系を使って生成するプロセスを確認します. 問題文の手続きを定義します. 手続き「+」は定義済みのため, １つ目の手続きを「+#」, ２つ目の手続きを「+$」としています. また, 手続きが生成するプロセスを観察するためにtraceを使用します.

(require (lib "racket/trace.ss"))

(define (inc x)
  (+ x 1))

(define (dec x)
  (- x 1))

(define (+# a b)
  (if (= a 0)
      b
      (inc (+# (dec a) b))))

(define (+$ a b)
  (if (= a 0)
      b
      (+$ (dec a) (inc b))))

(trace +# +$)

実行結果は次のようになりました.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (+# 4 5)
>(+# 4 5)
> (+# 3 5)
> >(+# 2 5)
> > (+# 1 5)
> > >(+# 0 5)
< < <5
< < 6
< <7
< 8
<9
9
> (+$ 4 5)
>(+$ 4 5)
>(+$ 3 6)
>(+$ 2 7)
>(+$ 1 8)
>(+$ 0 9)
<9
9

実行結果から, +#は再帰的プロセスを生成し, +$は反復的プロセスを生成することが分かります. +$の定義が末尾再帰的であるため, +$は反復的プロセスを生成します.

+#は, aが0でなかったとき+#を呼び出し, その結果をincの引数として与えています. このことから, +#は再帰的プロセスを生成します.

一方, +$では, aが0でなかったとき+$を呼び出しますが, その結果を使って計算する式となっていません. つまり, 末尾再帰の形をしています. よって, +$は再帰的プロセスを生成します.

[筋トレ] 2014.10.13の週

出勤前に筋トレをしました。その記録です。

10/14（火）
　スクワット　　　２０
　リアレイズ　　　１０、１０　（5kgの鉄アレイ）
　クランチ　　　　２０

10/15（水）
　プッシュアップ　１２　　　　（膝をついた状態）
　ナロースタンス　　４　　　　（手を重ねた状態）
　アームカール　　１５　　　　（5kgの鉄アレイ）

10/17（金）　74.05kg
　スクワット　　　２０、２０
　リアレイズ　　　１２、１０　（5kgの鉄アレイ）
　クランチ　　　　２０、２０

10/18（土）　75.10kg
　プッシュアップ　１２、　５　（膝をついた状態）
　ナロースタンス　　０　　　　（手を重ねた状態）
　アームカール　　２０、２０　（5kgの鉄アレイ）

[SICP] 問題 1.08 : 立方根の計算

立方根をとるNewton法はyがxの立方根の近似値なら, よりよい近似は

 x / y^2 + 2y  
--------------
      3 

の値で与えられるという事実によっている. この式を使い平方根の手続きと似た立方根の手続きを実装せよ. (1.3.4節で平方根と立方根の手続きの抽象化として, 一般的なNewton法の実装法を学ぶ.)

平方根を求めるプログラムを修正して, 立方根を求めるプログラムに作り変えます. 立方根を求められるように手続きimproveを修正します. また, 手続き名に現れるsqrtをcubeに変更します. プログラムの全体は次のようになります.

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

(define (improve guess x)
  (/ (+ (/ x (square guess))
        (* 2 guess))
     3))

(define (good-enough? guess x)
  (< (abs (/ (- (improve guess x) guess)
             guess))
     0.001))

(define (cube-iter guess x)
  (if (good-enough? guess x)
      guess
      (cube-iter (improve guess x)
                 x)))

(define (cube x)
  (cube-iter 1.0 x))

実行してみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (cube 8)
2.000004911675504
> (cube 10)
2.1544959251533746
> (cube 27)
3.001274406506175
> 

[SICP] 問題 1.07 : good-enough?の改良

平方根の計算で使ったgood-enough?テストは, 非常に小さい数の平方根をとる時には効果的ではない. また, 実際の計算機では, 算術演算は殆んどの場合, 限られた精度で実行される. それでわれわれのテストは非常に大きい数にも不適切である. 小さい数, 大きい数の場合, どのようにテストが失敗するかの例を使ってこのことを説明せよ. good-enough?を実装するもう一つの戦略は, ある繰返しから次へのguessの変化に注目し, 変化が予測値に比べ非常に小さくなった時に止めるのである. こういう終了テストを使う平方根手続きを設計せよ. これは小さい数, 大きい数に対してうまく働くか.

問題文にあるように, 小さい数と大きい数の平方根を求め, 組み込みの平方根を求める手続きの結果と比較します。

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (my-sqrt 10000.01)
100.00005025489767
> (sqrt 10000.01)
100.0000499999875
> (my-sqrt 0.0001)
0.03230844833048122
> (sqrt 0.0001)
0.01
> 

大きな数の場合は、組み込みの手続きと同等の結果が得られていますが, 小さな数の場合は正しい結果といえません.

ループの回数を調べるためにtraceを使います. 手続きsqrt-iterの呼び出され方を調べてみます. プログラムは次のようになります. １行目でtraceのためのライブラリを呼び出し, 最後の行でトレースする手続きを指定しています。

(require (lib "racket/trace.ss"))

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

(define (average x y)
  (/ (+ x y) 2))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (improve guess x)
  (average guess (/ x guess)))

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))

(define (my-sqrt x)
  (sqrt-iter 1.0 x))

(trace sqrt-iter)

平方根を求めると次のような結果が得られました.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (my-sqrt 10000.01)
>(sqrt-iter 1.0 10000.01)
>(sqrt-iter 5000.505 10000.01)
>(sqrt-iter 2501.252400010099 10000.01)
>(sqrt-iter 1252.6252005857104 10000.01)
>(sqrt-iter 630.3042212483191 10000.01)
>(sqrt-iter 323.08479587589 10000.01)
>(sqrt-iter 177.0182267724306 10000.01)
>(sqrt-iter 116.75482057222084 10000.01)
>(sqrt-iter 101.20223735102081 10000.01)
>(sqrt-iter 100.00719042723898 10000.01)
>(sqrt-iter 100.00005025489767 10000.01)
<100.00005025489767
100.00005025489767
> (my-sqrt 0.0001)
>(sqrt-iter 1.0 0.0001)
>(sqrt-iter 0.50005 0.0001)
>(sqrt-iter 0.2501249900009999 0.0001)
>(sqrt-iter 0.12526239505846617 0.0001)
>(sqrt-iter 0.06303035962394366 0.0001)
>(sqrt-iter 0.03230844833048122 0.0001)
<0.03230844833048122
0.03230844833048122
> (my-sqrt 0.000001)
>(sqrt-iter 1.0 1e-006)
>(sqrt-iter 0.5000005 1e-006)
>(sqrt-iter 0.250001249999 1e-006)
>(sqrt-iter 0.12500262498950004 1e-006)
>(sqrt-iter 0.06250531241075212 1e-006)
>(sqrt-iter 0.031260655525445276 1e-006)
<0.031260655525445276
0.031260655525445276
> 

実行結果から, 小さい数の場合は手続きの呼び出し回数に差がないことが分かります. 手続きgood-enough?は, 予測値guessの二乗と被開平数xの差が0.001より小さい場合に「十分よい」と判定しています. 被開平数が基準となる0.001より小さい場合, good-enough?の判定に与える影響が少なくなります. 例えば, 被開平数を0.000001, guessを0.03としgood-enough?を計算してみます.

  (< (abs (- (square guess) x)) 0.001)
= (< (abs (- (square 0.03) 0.000001)) 0.001)
= (< (abs (- (square 0.03) 0.000001)) 0.001)
= (< (abs (- 0.0009 0.000001)) 0.001)
= (< (abs 0.000899) 0.001)
= (< 0.000899 0.001)
= #t

この結果から, 被開平数が0.0001より小さいと予測値を2乗した結果だけで「十分よい」と判断し, 約0.03を求める平方根として返してしまいます.

問題文にあるように予測値の変化に着目し, 変化が少なくなった時に「十分に良い」と判定するように手続きを修正します. i番目の予測値の値をg_iとすると, 予測値の変化が次の式を満たせば予測値の変化が小さくなったと言えます.

| (gi+1 - gi) / gi | < 0.001

この式を使って手続きgood-enough?を改良します。 上の式でg_iはguessに相当し, g_i+1は手続きimproveを用いて計算出来ます. プログラムの全体は次のようになります.

(require (lib "racket/trace.ss"))

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

(define (average x y)
  (/ (+ x y) 2))

(define (improve guess x)
  (average guess (/ x guess)))

(define (good-enough? guess x)
  (< (abs (/ (- (improve guess x) guess)
             guess))
     0.001))

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))

(define (my-sqrt x)
  (sqrt-iter 1.0 x))

(trace sqrt-iter)

実行結果は次のようになりました.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (my-sqrt 0.0001)
>(sqrt-iter 1.0 0.0001)
>(sqrt-iter 0.50005 0.0001)
>(sqrt-iter 0.2501249900009999 0.0001)
>(sqrt-iter 0.12526239505846617 0.0001)
>(sqrt-iter 0.06303035962394366 0.0001)
>(sqrt-iter 0.03230844833048122 0.0001)
>(sqrt-iter 0.017701806998329746 0.0001)
>(sqrt-iter 0.011675473894984788 0.0001)
>(sqrt-iter 0.010120218365353947 0.0001)
>(sqrt-iter 0.010000714038711746 0.0001)
<0.010000714038711746
0.010000714038711746
> (my-sqrt 0.000001)
>(sqrt-iter 1.0 1e-006)
>(sqrt-iter 0.5000005 1e-006)
>(sqrt-iter 0.250001249999 1e-006)
>(sqrt-iter 0.12500262498950004 1e-006)
>(sqrt-iter 0.06250531241075212 1e-006)
>(sqrt-iter 0.031260655525445276 1e-006)
>(sqrt-iter 0.015646322308953218 1e-006)
>(sqrt-iter 0.007855117545897352 1e-006)
>(sqrt-iter 0.003991211544161647 1e-006)
>(sqrt-iter 0.0021208810160681787 1e-006)
>(sqrt-iter 0.0012961915927068783 1e-006)
>(sqrt-iter 0.0010338412392442034 1e-006)
>(sqrt-iter 0.0010005538710539446 1e-006)
<0.0010005538710539446
0.0010005538710539446
> (my-sqrt 0.00000001)
>(sqrt-iter 1.0 1e-008)
>(sqrt-iter 0.500000005 1e-008)
>(sqrt-iter 0.25000001249999987 1e-008)
>(sqrt-iter 0.12500002624999892 1e-008)
>(sqrt-iter 0.06250005312499106 1e-008)
>(sqrt-iter 0.03125010656242753 1e-008)
>(sqrt-iter 0.015625213280668165 1e-008)
>(sqrt-iter 0.007812926635966154 1e-008)
>(sqrt-iter 0.003907103283034967 1e-008)
>(sqrt-iter 0.001954831361974762 1e-008)
>(sqrt-iter 0.0009799734463768973 1e-008)
>(sqrt-iter 0.0004950889022510404 1e-008)
>(sqrt-iter 0.0002576436474057565 1e-008)
>(sqrt-iter 0.00014822847335384218 1e-008)
>(sqrt-iter 0.00010784594750729777 1e-008)
>(sqrt-iter 0.00010028540197249 1e-008)
>(sqrt-iter 0.00010000040611237676 1e-008)
<0.00010000040611237676
0.00010000040611237676
> 

期待通りの結果が得られました.

[SICP] 問題 1.06 : ifが特殊形式である理由

Alyssa P. Hackerはifが特殊形式である理由が分らない. 「cond を利用し, 普通の手続きとして定義してはいけないの?」と聞いた. Alyssaの友人のEva Lu Atorはそうすることはもちろん出来るといって, ifの新版を定義した:

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

EvaはAlyssaにプログラムを見せた:

(new-if (= 2 3) 0 5)
5

(new-if (= 1 1) 0 5)
0

Alyssaは喜び, 平方根のプログラムを書き直すのにnew-ifを使った:

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
          guess
          (sqrt-iter (improve guess x)
                     x)))

Alyssaが平方根を計算するのにこれを使おうとすると, 何が起きるか, 説明せよ.

new-ifを使って平方根を求める手続きを定義します. 手続き名sqrtは解釈系で定義済みであるため, my-sqrtとしています.

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

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

(define (average x y)
  (/ (+ x y) 2))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (improve guess x)
  (average guess (/ x guess)))

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))

(define (my-sqrt x)
  (sqrt-iter 1.0 x))

この手続を使って平方根を求めてみると, 解釈系は停止しません. その理由は, new-ifが特殊形式ではなく, 解釈系が作用的順序で評価しているためです.

new-ifは特殊形式ではないため, new-ifを評価するために三つの引数を評価します. ３つ目の引数でsqrt-iterを呼び出しているため無限ループに入り, 解釈系は停止しません.

ifは特殊形式であるため, まずguessの値が「十分よい」か判定します. 「十分よい」を場合は, sqrt-iterを評価せずguessを返すので解釈系は停止します.

[SICP] 問題 1.05 : 作用的順序と正規順序

Ben Bitdiddleは, 彼の対面している解釈系が, 作用的順序の評価を使っているか, 正規順序の評価を使っているか決定するテストを発明した. 次の二つの手続きを定義した:

(define (p) (p))

(define (test x y)
  (if (= x 0)
      0
      y))

彼は次に式

(test 0 (p))

を評価してみた. 作用的順序の評価を使う解釈系で, Benはどういう振舞いを見るか. 正規順序の評価を使う解釈系で, 彼はどういう振舞いを見るか. 説明せよ. (特殊形式ifの評価規則は, 解釈系が正規順序と作用的順序のどちらを使うかに無関係に同じとする: 述語式を最初に評価し, その結果が帰結式と代替式のいずれを評価するかを決める.)

問題文の手続きを定義します.

(define (p) (p))

(define (test x y)
  (if (= x 0)
      0
      y))

式(test 0 (p))を評価すると, 解釈系は停止しません. その理由を考えます.

まず, この問題を理解するためには, 手続きpが無限ループを表していることに気づかなくてはなりません. 手続きpの本体で式(p)を呼び出しているので, 式(p)を評価すると式(p)を評価し続けるため, 解釈系は停止しません.

作用的順序で評価すると次のようになります.

1. 式(test 0 (p))を評価します.
2. 引数である0と(p)を評価します.
3. 式(p)を評価すると無限ループに入ります.
4. その結果, 解釈系は停止しません.

正規順序で評価すると次のようになります.

1. 式(test 0 (p))を評価します.
2. 手続きの定義に従いif式に展開します.
   (if (= 0 0) 0 (p))
3. if式は特殊形式であるため, まず述語部分を評価します.
4. 述語部は(= 0 0)であるためtrueとなります.
5. 述語部がtrueであるため, 帰結部のみが評価されます.
6. 帰結部は0であるため, 0を返します.

引数yの値は式(p)ですがif式の代替部に相当し, 述語部がtureとなるため評価されません. そのため、解釈系が正規順序で評価するのであれば, 無限ループに入らず評価結果として0を返します.

[SICP] 問題 1.04 : 合成式を演算子として使う

われわれの評価モデルは, 演算子が合成式である組合せでも使えることを観察せよ. それに従って, 次の手続きの振舞いを述べよ.

(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))

問題文の手続きをエディタに入力します.

(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))

「+」などの演算子が入る箇所にif式が入っているので、奇妙な感じがします. この手続を評価してみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (a-plus-abs-b 4 3)
7
> (a-plus-abs-b 4 -3)
7
> 

評価結果から, aにbの絶対値を加えていることが分かります. こういう事ができるからといって, 何が嬉しいのかは今の時点ではよくわかりませんが, テキストを読み進めると, こういうことができないと苦労する例が出てきます＼(^o^)／

[SICP] 問題 1.03 : 三つの数を引数として取り、大きい二つの数の二乗の和を返す手続き

三つの数を引数としてとり, 大きい二つの数の二乗の和を返す手続きを定義せよ.

問題文を計算する手続きを定義します.

1. 手続きは, 三つの引数x, y, zを取ることとします.
2. xが最小であればyとzをそれぞれ二乗し,その和を返します.
3. 同様に, yが最小である場合, zが最小である場合もそれぞれ計算します.

これを手続きとして定義します.

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

(define (sum-square-large-2 x y z)
  (cond ((and (<= x y) (<= x z)) (+ (square y) (square z)))
        ((and (<= y z) (<= y x)) (+ (square z) (square x)))
        ((and (<= z x) (<= z y)) (+ (square x) (square y)))))

計算してみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (sum-square-large-2 1 2 3)
13
> (sum-square-large-2 4 2 3)
25
> (sum-square-large-2 1 5 3)
34
> (sum-square-large-2 1 3 3)
18
> (sum-square-large-2 2 2 2)
8
> 

計算結果から, 手続きはうまく定義できているようです.

手続きの定義をよく眺めると, 同じような構造が繰り返されており, 引数が循環していることが分かります. この構造に着目することで, 手続きの定義をもっと簡潔にできます. 手続名をsum-square-large-2-rとして定義します.

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

(define (sum-square-large-2-r x y z)
  (if (and (<= x y) (<= x z))
      (+ (square y) (square z))
      (sum-square-large-2-r y z x)))

この手続定義で何をしているかを説明します.

1. 引数xの値が最も小さい場合は, yの2乗とzの2乗の和を求めます.
2. それ以外の場合は, 引数の順序を入替えて自分自身を呼び出します.
3. 引数x, y, zのどれかが最小になるので, 残りの引数のそれぞれを2乗し, その和を返します.

手続きのテストをするため, 同じ条件で計算してみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
(13 25 34 18 8)
> (sum-square-large-2-r 1 2 3)
13
> (sum-square-large-2-r 4 2 3)
25
> (sum-square-large-2-r 1 5 3)
34
> (sum-square-large-2-r 1 3 3)
18
> (sum-square-large-2-r 2 2 2)
8
> 

結果は一致しています.

[SICP] 問題 1.02 : 前置記法

次の式を前置記法に翻訳せよ.

 5 + 4 + (2 - (3 - (6 + 4/5)))
-------------------------------
       3(6 - 2)(2 - 7)

Lispでは前置記法を採用しているため, 前置記法に慣れるための問題です. p.5の図のように数式の構造を把握できれば, 前置記法に書き表せます.

Racketのエディタは, カッコを閉じた時に対応する開きカッコを調べてくれます. また, タブキーを押すとインデント量を適切に設定してくれます. これらの機能をうまく使えば, 入力した式の構造を理解しやすくなります.

前置記法に翻訳した式は次のとおりです.

(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))
   (* 3 (- 6 2) (- 2 7)))

式を評価した結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))
     (* 3 (- 6 2) (- 2 7)))
-37/150
> 

結果が有理数の場合, 分数のまま返してくれるので驚きです.

手で計算した結果と合っていました(^o^)

[SICP] 問題 1.01 : 解釈系を使う

式の列がある. それぞれの式で解釈系が印字する結果は何か. 列は示した順に評価するものとする.

10

(+ 5 3 4)

(- 9 1)

(/ 6 2)

(+ (* 2 4) (- 4 6))

(define a 3)

(define b (+ a 1))

(+ a b (* a b))

(= a b)

(if (and (> b a) (< b (* a b)))
    b
    a)

(cond ((= a 4) 6)
      ((= b 4) (+ 6 7 a))
      (else 25))

(+ 2 (if (> b a) b a))

(* (cond ((> a b) a)
         ((< a b) b)
         (else -1))
   (+ a 1))

DrRacketに式を入力し, その応答を観察します. Racketを起動し, 画面の下側に式を入力した結果は次の通りです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> 10
10
> (+ 5 3 4)
12
> (- 9 1)
8
> (/ 6 2)
3
> (+ (* 2 4) (- 4 6))
6
> (define a 3)
> (define b (+ a 1))
> (+ a b (* a b))
19
> (= a b)
#f
> (if (and (> b a) (< b (* a b)))
      b
      a)
4
> (cond ((= a 4) 6)
        ((= b 4) (+ 6 7 a))
        (else 25))
16
> (+ 2 (if (> b a) b a))
6
> (* (cond ((> a b) a)
           ((< a b) b)
           (else -1))
     (+ a 1))
16
> 

最後の２つの式で, ifやcondの結果をそのまま式の値として使用しています. Schemeでは, 式と文の区別がありません.

カラマーゾフの妹（高野 文緒 著、講談社文庫）

カラマーゾフの妹 (高野 文緒 著、講談社文庫)

ドストエフスキーの「カラマーゾフの兄弟」の続編として書かれています。もともと、「カラマーゾフの兄弟」は2部構成の第1部にあたり、第2部の伏線と思われる記述があります。結局、ドストエフスキーは第2部を書かずに死んだため、中途半端な状態のままになっています。

著者は、第2部に相当する「カラマーゾフの妹」を書くことで、第1部の伏線や矛盾点を解決しようと試みています。こういう見方があるのかと感心しましたが、第1部の詳細は忘れました＼(^o^)／

この本を読む前に、「カラマーゾフの兄弟」を一通り読むことをオススメします。



何が言いたいかというと、

私はカラマーゾフの兄弟を読んだ＼(^o^)／

と、いうことです。