Exercise1.20
;; 正規順序
正規順序による (gcd 206 40) の評価は次のように進行する。
if:(= 40 0) => #f
else:(gcd 40 (remainder 206 40))
if:(= (remainder 206 40) 0) => #f
else:(gcd (remainder 206 40)
(remainder 40 (remainder 206 40)))
if:(= (remainder 40 (remainder 206 40)) 0) => #f
else:(gcd (remainder 40 (remainder 206 40))
(remainder (remainder 206 40) (remainder 40 (remainder 206 40))))
if:(= (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) 0) => #f
else:(gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
(remainder (remainder 40 (remainder 206 40))
(remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))
if:(= (remainder (remainder 40 (remainder 206 40))
(remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) 0) => #t
then:(remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
=>2
となる。結局 remainder 演算が実行されるのは、if文の中で14回、最後に簡
約されるとき4回であり、計18回実行される。
;; 作用的順序
(gcd 206 40)
作用的順序による評価は次のように進行する。
(gcd 40 6) ;6: (remainder 206 40)
(gcd 6 4) ;4: (remainder 40 6)
(gcd 4 2) ;2: (remainder 6 4)
(gcd 2 0) ;0: (remainder 4 2)
2
引数が評価されてから作用させるので、remainder は 4回実行される。
by kacchi (Alyssaさんの指摘を受けて修正)
Exercise1.21
199, 1999, 19999 の最小除数
(smallest-divisor 199)
;Value: 199
(smallest-divisor 1999)
;Value: 1999
(smallest-divisor 19999)
;Value: 7
by kacchi
Exercise1.22
runtime 関数がある MIT Scheme を利用しました(他の処理系にはない？)。
指定範囲の連続する奇整数について素数性を調べる手続き search-for-prime を書け
;; 素数でない整数は出力しないようにした。
(define (search-for-prime start limit)
(if (prime? start)
(times-prime-test start))
(if (<= (+ start 2) limit)
(search-for-prime (+ start 2) limit)))
;; 速すぎて計測できないので大きな数で試した。
(search-for-prime 1000001 1000100)
1000003 *** 1.0000000000000009e-2
1000033 *** 1.0000000000000009e-2
1000037 *** 1.0000000000000009e-2
(search-for-prime 10000001 10000200)
10000019 *** .01999999999999602
10000079 *** .03999999999999915
10000103 *** 2.0000000000003126e-2
(search-for-prime 100000001 100000100)
100000007 *** .11999999999999744
100000037 *** 6.0000000000002274e-2
100000039 *** 6.0000000000002274e-2
ひと桁増えると計算時間がほぼ√10倍になると思うので、
・支持する。
・合っている。
by kacchi
Exercise1.23
(define (next n)
(if (= n 2)
3
(+ n 2)))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (next test-divisor)))))
(times-prime-test 1000003)
1000003 *** .00999999999999801
(times-prime-test 10000019)
10000019 *** 3.0000000000001137e-2
(times-prime-test 100000007)
100000007 *** .10999999999999943
速度に変化はないと思う。しかし理由が解らない。
by kacchi
Exercise1.24
解答募集中
Exercise1.25
理論上は正しい。しかし，高速素数テストには使えない。
Hackerのプログラムでは(fast-exp base exp)を計算する。
expが大きな数になると，この計算に時間が掛かりすぎる。
たとえば1001の素数判定を行うとしてaに2を選ぶと，
(fast-exp 2 1001)，すなわち2の1001乗を先に計算する
ことになる。
by chrono
Exercise1.26
Reasonerのプログラムでのexpmod関数の呼び出し回数は，次のように求まる。
nを二進数で表現し，「各ビットに対してビット0なら1，ビット1なら2に
そのビットが表す10進数を掛けた値」の和となる。
ただし，最上位ビットは1にビットが表す10進数を掛ける。
たとえば，nが10の時，
10 = (1010)_2 より 8*1 + 4*1 + 2*2 + 1*1 = 17回となる。
expmod関数の呼び出し関係と照らし合わせると次となることより分かる。
(詳細は割愛します…)
1 : 0 : 1 : 0
: :
expmod(base 1 m)-+ :
expmod(base 1 m)--expmod(base 2 m)+ :
| :
expmod(base 1 m)-+ |
expmod(base 1 m)--expmod(base 2 m)--expmod(base 4 m)--expmod(base 5 m)+
|
expmod(base 1 m)-+ |
expmod(base 1 m)--expmod(base 2 m)+ |
| |
expmod(base 1 m)-+ | |
expmod(base 1 m)--expmod(base 2 m)--expmod(base 4 m)--expmod(base 5 m)--expmod(base 10 m)
ここで，2のべき乗のうちn以下の最大の数を2^kとすると，expmod関数の
呼び出し回数の関係は，明らかに
2^k <= n < 2^(k+1)
となる (ここも割愛します…)。
2^kの呼び出し回数は上述より2^(k+1) - 1となり，2^(k+1)の呼び出し回数は
上述より2^(k+2) - 1となる。
よって，Reasonerのプログラムはθ(n)である。
by chrono
Exercise1.27
問題文
脚注47におけるCarmichael数を実際にfool the Fermat testを行って証明せよ。つまり、整数nを引数に取り∀a < n(a^n≡a (mod n))を満たすかテストする手続きを作れ、そしてそれで与えられたCarmichael数をテストしてみよ。
(define (fool-the-fermat-test n)
(define (iter-fermat a)
(cond ((< a 0) #f)
((= a 0) #t)
((= (expmod a n n) a) (iter-fermat (- a 1)))
(else #f)))
(iter-fermat (- n 1)))
gosh> (fool-the-fermat-test 561)
#t
gosh> (fool-the-fermat-test 1105)
#t
gosh> (fool-the-fermat-test 1729)
#t
gosh> (fool-the-fermat-test 2465)
#t
gosh> (fool-the-fermat-test 2821)
#t
gosh> (fool-the-fermat-test 6601)
#t
by iwk
Exercise1.28
解答募集中
Exercise1.29
;; 合成シンプソン公式を参考にした。
http://ja.wikipedia.org/wiki/%E3%82%B7%E3%83%B3%E3%83%97%E3%82%BD%E3%83%B3%E3%81%AE%E5%85%AC%E5%BC%8F
(define (cube x) (* x x x))
(define (integral f a b n)
(define h (/ (- b a) n))
(define (y k) (f (+ a (* k h))))
(define (next n) (+ n 2))
(/ (* h
(+ (y 0)
(* (sum y 1 next (- n 1)) 4)
(* (sum y 2 next (- n 2)) 2)
(y n)))
3))
(integral cube 0 1 100)
=>1/4
(integral cube 0 1 1000)
=>1/4
by kacchi
Exercise1.30
(define (sum term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (+ (term a) result))))
(iter a 0))
by kacchi
Exercise1.31
(a)
(1)与えられた範囲の点での関数値の積を返す手続き product を定義せよ。
(2)product を使って factorial を定義せよ。
(3)式 π/4 = (2*4*4*6*6*8..)/(3*3*5*5*7*7...) によってπの近似値を
productを使って定義せよ。
(1)
(define (product term a next b)
(if (> a b)
1
(* (term a) (product term (next a) next b))))
(2)
(define (factorial n)
(product identity 1 inc n))
(3)
;; John Wallis
;; http://www.pluto.ai.kyutech.ac.jp/plt/matumoto/pi_small/node5.html
(define (pi-product a b)
(define (pi-term x)
(/ (* (* x 2) (+ (* x 2) 2))
(square (+ (* x 2) 1))))
(define (pi-next x) (+ x 1))
(product pi-term a pi-next b))
gosh> (* 4 (pi-product 1.0 1000))
=>3.1423773650938855
(b) 反復的プロセスを生成する product を書け。
(define (product term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (* (term a) result))))
(iter a 1))
by kacchi
Exercise1.32
(a) sum や product 更に一般的な accumulate の特殊な場合であることを示せ。
;; 再帰的プロセス版
(define (accumulate combiner null-value term a next b)
(if (> a b)
null-value
(combiner (term a)
(accumulate combiner null-value term (next a) next b))))
(define (sum term a next b)
(accumulate + 0 term a next b))
(define (product term a next b)
(accumulate * 1 term a next b))
(b) 反復的プロセスを生成する版
(define (accumulate combiner null-value term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (combiner (term a) result))))
(iter a null-value))
by kacchi
Exercise1.33
;; 再帰版
(define (filtered-accumulate predicate combiner null-value term a next b)
(cond ((> a b) null-value)
((predicate a)
(combiner (term a)
(filtered-accumulate
predicate combiner null-value term (next a) next b)))
(else (filtered-accumulate
predicate combiner null-value term (next a) next b))))
;; 反復版
(define (filtered-accumulate predicate combiner null-value term a next b)
(define (iter a result)
(cond ((> a b) result)
((predicate a) (iter (next a) (combiner (term a) result)))
(else (iter (next a) result))))
(iter a null-value))
(a) 素数の2乗の和
(define (sum-squared-prime-numbers a b)
(filtered-accumulate prime? + 0 square a inc b))
(sum-squared-prime-numbers 2 10)
;Value: 87
(b) i < n で gcd(i,n) = 1 となる全整数の積
(define (product-gcd n)
(define (p i)
(= (gcd i n) 1))
(filtered-accumulate p * 1 identity 1 inc n))
(product-gcd 10)
;Value: 189
(product-gcd 100)
;Value: 426252881942771063138176712755660145456313428952105524817872601
by kacchi
Exercise1.34
(define (f g)
(g 2))
解釈系に (f f) を評価させるとどうなるか。
f の本体を取り出し仮引数 g を f で置き換える。
(f 2)
f の本体を取り出し仮引数 g を 2 で置き換える。
(2 2)
に帰着する。左端の演算子を評価すると値は 2 となる。値は手続きでなければならないが、
数値なのでエラーになる。
MIT scheme での結果。
;The object 2 is not applicable.
Gauche での結果。
*** ERROR: invalid application: (2 2)
by kacchi
Exercise1.35
1.2.2節の黄金比は、x^2 = x + 1 を満たす x である。
これを等価な、x = 1 + 1/x と書けば、平方根の計算と同様、x |-> 1 + 1/x の不動点を
探すことと同じである。
gosh> (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)
=>1.6180327868852458
by kacchi
Exercise1.36
(1) fixed-point を修正して、生成する近似値を順に印字できるようにせよ。
(define (average x y) (/ (+ x y) 2))
(define tolerance 0.00001)
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess step)
(let ((next (f guess)))
(print-step next step)
(if (close-enough? guess next)
next
(try next (+ step 1)))))
(try first-guess 1))
(define (print-step n step)
(display step)
(display ": ")
(display n)
(newline))
(2) x^x = 1000 の解を求めよ。
(expt 4 4) < 1000 < (expt 5 5) なので、4.0 を fixed-point の予測値とした。
gosh> (fixed-point (lambda (x) (/ (log 1000) (log x))) 4.0)
1: 4.9828921423310435
2: 4.301189432497896
(略)
28: 4.555530430629037
29: 4.555539183677709
=>4.555539183677709
gosh> (expt 4.555539183677709 4.555539183677709)
=>1000.0087530953886
(3) 平均緩和法を使った場合とステップ数を比較せよ。
gosh> (fixed-point (lambda (x) (average (/ (log 1000) (log x)) x)) 4.0)
1: 4.491446071165521
2: 4.544974650975552
(略)
6: 4.5555268862194875
7: 4.5555342036887705
=>4.5555342036887705
gosh> (expt 4.5555342036887705 4.5555342036887705)
=>999.9962217021748
平均緩和法を使った場合、ステップ数は 1/4 になった。
by kacchi
Exercise1.37
(a) k項有限連分数を計算する手続きを定義し、kの順次の値で1/φの近似をとり手続きを調べよ。4桁の精度を得るにはkをどのくらいの大きさにしなければならないか。
(1) cont-frac
;; 再帰的プロセス版
(define (cont-frac n d k)
(define (rec i)
(if (= i k)
(/ (n i) (d i))
(/ (n i) (+ (d i) (rec (+ i 1))))))
(rec 1))
(2) kの大きさ
1/φ の計算
gosh> (/ 1 (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0))
=>0.6180344478216819
手続きを調べるため cont-frac-test を定義し、kの値が1から15まで1/φの近似を調べた。
kの増加に伴って精度が上がることを確認した。4桁の精度を得るには、kの値は11程度でよい。
(define (cont-frac-test a b)
(if (<= a b)
(let ((r (cont-frac (lambda (i) 1.0)
(lambda (i) 1.0)
a)))
(display a)
(display ": ")
(display r)
(newline)
(cont-frac-test (+ a 1) b))))
gosh> (cont-frac-test 1 15)
1: 1.0
2: 0.5
3: 0.6666666666666666
4: 0.6000000000000001
5: 0.625
6: 0.6153846153846154
7: 0.6190476190476191
8: 0.6176470588235294
9: 0.6181818181818182
10: 0.6179775280898876
11: 0.6180555555555556
12: 0.6180257510729613
13: 0.6180371352785146
14: 0.6180327868852459
15: 0.6180344478216819
(b) cont-frac の反復的プロセス版
(define (cont-frac n d k)
(define (iter a i)
(if (= i 1)
a
(iter (/ (n (- i 1)) (+ (d (- i 1)) a)) (- i 1))))
(iter (/ (n k) (d k)) k))
by kacchi
Exercise1.38
オイラーの展開による自然対数の底を近似するプログラムを書け。
;; e-2-cfの計算でkが20程度で15桁の精度が得られたので、
;; kを20としてeを近似するプログラムを書いた。
(define (e)
(define (e-2-cf k)
(cont-frac (lambda (i) 1.0)
(lambda (i)
(if (= (remainder i 3) 2)
(* 2.0 (inc (quotient i 3)))
1.0))
k))
(+ (e-2-cf 20) 2))
gosh> (e)
=>2.718281828459045
by kacchi (iwkさんの指摘を受けて修正)
Exercise1.39
正接関数の近似値を計算する手続き(tan-cf x k)を定義せよ。
(define (tan-cf x k)
(cont-frac (lambda (i) (if (= i 1) x (- (* x x))))
(lambda (i) (- (* i 2) 1))
k))
by kacchi
最終更新：2008年01月08日 22:25
