オンラインSICP読書女子会 #10

[オンラインSICP読書女子会 #10 (1.3.3 〜 1.3.4)](http://ladiespp.connpass.com/event/30416/)

1.3.3 〜 1.3.4 (練習問題1.37 〜 1.41)

## ex-1.37. (a) 無限連分数

```math
1/\phi = \phi - 1 = 0.6180339887 \dots
```

([黄金比 - Wikipedia](https://ja.wikipedia.org/wiki/%E9%BB%84%E9%87%91%E6%AF%94) より)

```scm
; [ex-1.37-a]


(define (ex-1.37-a)
	(define (loop k)
		(cond
			((<= k 20)
				(print ";k=" k ", 1/phi=" (phi-inv-a k))
				(loop (+ k 1)))
			(else #t)))
	(loop 1)
	#t
	)

(define (phi-inv-a k)
	(cont-frac
		(lambda (i) 1.0)
		(lambda (i) 1.0)
		k))

; n :: Num -> Num
; d :: Num -> Num
; k :: Num
(define (cont-frac n d k)
	(define (loop i)
		(if
			(>= i k)
			(/ (n i) (d i))
			(/ (n i) (+ (d i) (loop (+ i 1))))))
	(loop 1))
```

```scm
gosh> (ex-1.37-a)
;k=1, 1/phi=1.0
;k=2, 1/phi=0.5
;k=3, 1/phi=0.6666666666666666
;k=4, 1/phi=0.6000000000000001
;k=5, 1/phi=0.625
;k=6, 1/phi=0.6153846153846154
;k=7, 1/phi=0.6190476190476191
;k=8, 1/phi=0.6176470588235294
;k=9, 1/phi=0.6181818181818182
;k=10, 1/phi=0.6179775280898876
;k=11, 1/phi=0.6180555555555556
;k=12, 1/phi=0.6180257510729613
;k=13, 1/phi=0.6180371352785146
;k=14, 1/phi=0.6180327868852459
;k=15, 1/phi=0.6180344478216819
;k=16, 1/phi=0.6180338134001252
;k=17, 1/phi=0.6180340557275542
;k=18, 1/phi=0.6180339631667064
;k=19, 1/phi=0.6180339985218034
;k=20, 1/phi=0.6180339850173578
#t
```

$k=11, 1/phi=0.6180555555555556$ 以降は
小数点以下4桁以内には正しい値が算出されている模様.

## ex-1.37. (b) 処理プロセスの変換

> あなたが書いた cont-frac が再帰プロセスを生成するのであれば、線形プロセスを生成するものを書け。線形プロセスを生成するのであれば、再帰プロセスを生成するものを書け。

```scm
; [ex-1.37-b]
(define (ex-1.37-b)
	(define (loop k)
		(cond
			((<= k 20)
				(print ";k=" k ", 1/phi=" (phi-inv-b k))
				(loop (+ k 1)))
			(else #t)))
	(loop 1)
	#t
	)

(define (phi-inv-b k)
	(cont-frac-linear
		(lambda (i) 1.0)
		(lambda (i) 1.0)
		k))

; n :: Num -> Num
; d :: Num -> Num
; k :: Num
(define (cont-frac-linear n d k)
	(define (loop result i)
		(if
			(= i 0)
			result
			(loop
				(/
					(n i)
					(+
						(d i)
						result))
				(- i 1))))
	(loop 0 k))
```

```scm
gosh> (ex-1.37-b)
;k=1, 1/phi=1.0
;k=2, 1/phi=0.5
;k=3, 1/phi=0.6666666666666666
;k=4, 1/phi=0.6000000000000001
;k=5, 1/phi=0.625
;k=6, 1/phi=0.6153846153846154
;k=7, 1/phi=0.6190476190476191
;k=8, 1/phi=0.6176470588235294
;k=9, 1/phi=0.6181818181818182
;k=10, 1/phi=0.6179775280898876
;k=11, 1/phi=0.6180555555555556
;k=12, 1/phi=0.6180257510729613
;k=13, 1/phi=0.6180371352785146
;k=14, 1/phi=0.6180327868852459
;k=15, 1/phi=0.6180344478216819
;k=16, 1/phi=0.6180338134001252
;k=17, 1/phi=0.6180340557275542
;k=18, 1/phi=0.6180339631667064
;k=19, 1/phi=0.6180339985218034
;k=20, 1/phi=0.6180339850173578
#t
```

間違い (1):

ひっくり返して

```math
\frac{D_1 + \frac{D_2 + \frac{D_3 + \dots}{N_3}}{N_2}}{N_1} \\
= \frac{D_1}{N_1} + \frac{D_2}{N_1 \cdot N_2} + \frac{D_3}{N_1 \cdot N_2 \cdot N_3} + \dots
```

にしたら求めたい値が逆数で求まるからそれをもう一度ひっくり返せばさっくり算出できそうって思ったけれど,
逆数は正しくは

```math
\frac{D_1 + \frac{N_2}{D_2 + \frac{N_3}{D_3 + \dots}}}{N_1}
```

でした…o__)o
この間違えたパターンだと $1 + \frac{1}{1} + \frac{1}{1 \cdot 1} + \frac{1}{1 \cdot 1 \cdot 1} + \dots$ になっちゃう＞＜

間違い (2):

ある時点の分母を1つの状態変数に固定しようとしても, その分母がどう使われるかが $i+1$ での状態が決まらないと決まらないから
反復プロセスでの実装はできない.

と思ったけれど, $i=1, 2, 3, \cdots, k$ の順で計算するのではなくて逆順で計算すれば問題はなかった…
そして解へ.

## 1.38. e - 2 の値を連分数で

```scm
; [ex-1.38.scm]


(define (ex-1.38)
	(define (loop k)
		(cond
			((<= k 20)
				(print ";k=" k ", e-2=" (euler-2 k))
				(loop (+ k 1)))
			(else #t)))
	(loop 1)
	#t
	)


(load "./ex-1.37-a")


(define (euler-2 k)
	(define (euler-2-d i)
		(cond
			((= (remainder i 3) 2)
				(* (+ (div i 3) 1) 2))
			(else 1)))
	(cont-frac
		(lambda (i) 1.0)
		euler-2-d
		k))
```

```scm
gosh> (ex-1.38)
;k=1, e-2=1.0
;k=2, e-2=0.6666666666666666
;k=3, e-2=0.75
;k=4, e-2=0.7142857142857143
;k=5, e-2=0.71875
;k=6, e-2=0.717948717948718
;k=7, e-2=0.7183098591549296
;k=8, e-2=0.7182795698924731
;k=9, e-2=0.7182835820895522
;k=10, e-2=0.7182817182817183
;k=11, e-2=0.7182818352059925
;k=12, e-2=0.7182818229439497
;k=13, e-2=0.7182818287356957
;k=14, e-2=0.7182818284454013
;k=15, e-2=0.7182818284705836
;k=16, e-2=0.7182818284585635
;k=17, e-2=0.7182818284590651
;k=18, e-2=0.718281828459028
;k=19, e-2=0.7182818284590459
;k=20, e-2=0.7182818284590452
```

> $e - 2 = 2.71828 \space 18284 \space 59045 \space 23536 \space 02874 \space 71352 \cdots - 2$
> ([ネイピア数 - Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%8D%E3%82%A4%E3%83%94%E3%82%A2%E6%95%B0) より)

## ex-1.39. tan x を連分数で

```scm
; [ex-1.39.scm]


(define (ex-1.39)
	(define (loop-45d k)
		(cond
			((<= k 20)
				(print ";k=" k ", tan-cf(pi/4)=" (tan-cf (/ 3.14 4) k))
				(loop-45d (+ k 1)))
			(else #t)))

	(define (loop-30d k)
		(cond
			((<= k 20)
				(print ";k=" k ", tan-cf(pi/6)=" (tan-cf (/ 3.14 6) k))
				(loop-30d (+ k 1)))
			(else #t)))

	(loop-45d 1)
	(newline)
	(loop-30d 1)

	#t
	)


(load "./ex-1.37-a")


(define (tan-cf x k)
	(cont-frac
		(lambda (i) (if (= i 1) x (- (* x x))))
		(lambda (i) (- (* i 2) 1))
		k))
```

```scm
gosh> (ex-1.39)
;k=1, tan-cf(pi/4)=0.785
;k=2, tan-cf(pi/4)=0.9879288103952764
;k=3, tan-cf(pi/4)=0.9989925703264279
;k=4, tan-cf(pi/4)=0.9992018697579907
;k=5, tan-cf(pi/4)=0.9992039767162123
;k=6, tan-cf(pi/4)=0.9992039900467972
;k=7, tan-cf(pi/4)=0.9992039901048574
;k=8, tan-cf(pi/4)=0.9992039901050424
;k=9, tan-cf(pi/4)=0.9992039901050428
;k=10, tan-cf(pi/4)=0.9992039901050428
;k=11, tan-cf(pi/4)=0.9992039901050428
;k=12, tan-cf(pi/4)=0.9992039901050428
;k=13, tan-cf(pi/4)=0.9992039901050428
;k=14, tan-cf(pi/4)=0.9992039901050428
;k=15, tan-cf(pi/4)=0.9992039901050428
;k=16, tan-cf(pi/4)=0.9992039901050428
;k=17, tan-cf(pi/4)=0.9992039901050428
;k=18, tan-cf(pi/4)=0.9992039901050428
;k=19, tan-cf(pi/4)=0.9992039901050428
;k=20, tan-cf(pi/4)=0.9992039901050428

;k=1, tan-cf(pi/6)=0.5233333333333333
;k=2, tan-cf(pi/6)=0.5759096152043399
;k=3, tan-cf(pi/6)=0.5769876838370881
;k=4, tan-cf(pi/6)=0.57699636208848
;k=5, tan-cf(pi/6)=0.5769964002862351
;k=6, tan-cf(pi/6)=0.5769964003926679
;k=7, tan-cf(pi/6)=0.5769964003928727
;k=8, tan-cf(pi/6)=0.5769964003928729
;k=9, tan-cf(pi/6)=0.5769964003928729
;k=10, tan-cf(pi/6)=0.5769964003928729
;k=11, tan-cf(pi/6)=0.5769964003928729
;k=12, tan-cf(pi/6)=0.5769964003928729
;k=13, tan-cf(pi/6)=0.5769964003928729
;k=14, tan-cf(pi/6)=0.5769964003928729
;k=15, tan-cf(pi/6)=0.5769964003928729
;k=16, tan-cf(pi/6)=0.5769964003928729
;k=17, tan-cf(pi/6)=0.5769964003928729
;k=18, tan-cf(pi/6)=0.5769964003928729
;k=19, tan-cf(pi/6)=0.5769964003928729
;k=20, tan-cf(pi/6)=0.5769964003928729
#t
```

```python
>>> tan(pi/4)
0.99999999999999989
>>> tan(pi/6)
0.57735026918962573
```

## 1.3.4 返り値としての手続き

用語再掲: average damping = 平均緩和法

時間切れo__)o