問題解答

問1.26

(* (expmod base (/ exp 2) m)
     (expmod base (/ exp 2) m))

この部分で、expmod が 2 度呼ばれてしまうために (/ exp 2) と、 exp の減少率を半分にしている意味がなくなってしまうため。

Racket 環境構築

問1.27 をやるにあたってコードを書かないといけなかったので、ここで Racket を使ってみるために環境構築。
主に「計算機プログラムの構造と解釈」のためのプログラミング環境を参考に環境構築をおこないます。

ただ、SICP Support for DrRacketの環境構築が私のところ(Racket 6.1.1 x86_64)ではうまくいっていなさそうです。最初のインストール時にエラーメッセージが出たり、Language の選択で SICP が対象にならないです。 #lang planet neil/sicp と入力すれば実行できているっぽいもののちょっと気持ち悪いので、 元記事と同じ 5.3.3 を使用することにしました。

5.3.3+SICP Support でもインストール時にエラーがボロボロ出たんですが、メニューからは選ぶことができるようになっているしとりあえずこれで様子を見てみて、やっぱりおかしそうなら 32bit 版を試したりしてみます。

ちょっと歩みが遅すぎて埒が明かなさそうなので問題に関する方針を変えてみることにします。

これまでは一問一問結構粘って、結果一日一問やったら終わりみたいな感じになってしまっていたので、ちょっとサクサク行くようにしてみます。Lisp のエラーとかそういうところでハマって時間を取られてしまったら答えあわせをしてしまって、写経しつつ自分のコードと比較をして理解をするようにします。

また、問題も一問で最大30分を目安にしてそれでもダメだったら諦めて答えを見ながら理解を進めるようにします。

Lisp 関連のエラーで悩まされて時間を潰すことがほとんどだったので、これで随分進みは良くなるんじゃないかな～?あと、ちょっと Gauche+Meadow の環境が辛いので別の環境を試したほうがいいのかも。 SICP コースだと Racket がお勧めっぽいので、そちらも試してみます。

問題回答

問1.24
gauche には random が無いようなので先人の知恵を拝借。
また、Gauche では true/false は #t/#f のようなのでこれは読み替えて使用。

回答からコードを持ってきて実行しても、素数のはずなのに素数ではないと判定されてしまう。何故～?

gosh> (fast-prime? 1000000000000037 10)
#f

仕方ないので解説を読む。

The timing numbers from the Fermat test start out looking pretty poor compared to what we've seen previously. This has mostly to do with the completely arbitrary number of random values I chose to test each prime with. As we increase the size of the numbers we're testing, you can see that the time using the Fermat test barely increases at all. We can verify that the time increase is logarithmic by observing that as the numbers under test increase by a factor of 10, the ratio column increases by a factor of roughly three. This logarithmic characteristic is due to the fact that the expmod procedure used in fermat-test has a logarithmic time complexity.

値が小さいときには非常に芳しくない結果となり、値が大きくなっても log10 ではなく log3 程度の効率化ししかなっていない。
これは、expmod が対数時間複雑性を持っているから、とのこと(P.29 の頭で説明されていた)。

問1.25
先人の知恵を拝借。

注釈 46 に解説があるのであわせて読む。

巨大な整数を扱うのはコストがかかるため、その影響が出てくるとのこと。なるほどー。

今日は方針を決めたりそれをメモしたりするのに時間をとられたのでここまで。よくわからないままウンウン悩むよりはサクサクと
答えを見ながら理解したほうがいい気はするので当分この流れでいってみる。

問題解答

問1.23
next の定義。

(define (next n)
  (if (= n 2)
      3
      (+ n 2)))

next を使って find-divisor をかきかえる

(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)))))

処理時間の比較。最近の計算機だと処理速度が速すぎて小さい値だと正確な処理時間が測れないようなので、大きめの値を使用。

改良前
1000000021 *** 20519#
100000000003 *** 267726#

改良後
1000000021 *** 18565#
100000000003 *** 164153#

処理時間はそれぞれ 0.9 倍、 0.61 倍となっており、 半分にはならない。

明確な理由がわからなかったので先人の知恵を借りる。
計算以外の、処理系のオーバーヘッドが大きな影響を及ぼしているっぽい。言われてみれば確かにそうか。

本文

1.2.6 例:素数性のテスト

Fermat テスト : ある数が素数か否かを確率的に求める。

テストに失敗すれば素数ではなく、テストに成功すれば高い確率で素数となる。更にテストを繰り返すと正確性が上がっていく。

このようなテストの存在が確率的アルゴリズムとして知られるようになった。

問題解答

問1.21
本のプログラムを写経して実行するだけ。

gosh> (smallest-divisor 199)
199
gosh> (smallest-divisor 1999)
1999
gosh> (smallest-divisor 19999)
7
gosh>

問1.22
gauche には runtime が無いようなので、まずはそれを解決。

prime? などは本をそのまま流用して、search-for-primes はこのような感じ。

(define (search-for-primes n)
  (define (search-for-primes-iter i k)
    (cond ((= k 0))
          ((prime? i)
           (display i)
           (newline)
           (search-for-primes-iter (+ i 2) (- k 1)))
          (else (search-for-primes-iter (+ i 2) k))))
                                
  (search-for-primes-iter n 3))

入力された値の偶奇判断とかモロモロ盛り込もうとするともっと複雑になってしまいそう。
あと、Meadow 上で gosh を走らせてコードを実行すると Stack Trace がきちんと表示されなかったり、ステップ実行できなかったりしてエラーが起きたときの対応が辛い。もっとちゃんとした環境を作らないと効率が悪すぎる。

問題解答

問1.17, 1.18
1.17 をやっていたらついでに 1.18 もやってしまったのでまとめて回答。

(define (even? n)
  (= (remainder n 2) 0))

(define (double a)
  (+ a a))

(define (halve a)
  (/ a 2))

(define (mult a n)
  (define (mult-iter a n t)
    (cond ((= n 0) 0)
          ((= n 1) a)
          ((even? n) (mult-iter (double a) (halve n) t))
          (else (+ (mult-iter a (- n 1) t) a))))

  (mult-iter a n 0))

正直、ビット演算とシフトを使いたい。。。

問1.19
プログラム的にやることはこれまでと変わらないのと、Fibonacchi 数の計算についての内容が主なのでパス。

本文

1.2.5 最大公約数
Euclid のアルゴリズムを使用して最大公約数(GCD)を求める

問題解答

問1.20

(gcd 206 40)
((gcd 40 (remainder 206 40)))
(((gcd (remainder 206 40) (remainder 40 (remainder 206 40))))))
:
:

正規順序評価を用いると gcd が延々展開されてしまって正常に評価がおこなわれない
→答え合わせをしたらそんなことなかった。めんどくさがらずにきちんと展開すればできた。

作用的順序評価は以下の通り

(gcd 206 40)
(gcd 40 (remainder 206 40))
(gcd 40 6)
(gcd 6 (remainder 40 6))
(gcd 6 4)
(gcd 4 (remainder 6 4))
(gcd 4 2)
(gcd 2 (remainder (4 2))
(gcd 2 0)

よって、remainder は 4 回呼ばれる。

問題解答

問1.15 a
(sine 12.15)
(sine 4.05)
:

と、sine が呼ばれる度に angle が 1/3 になり、それが 0.1 未満になるまで続くのだから

12.15*(1/3^n) < 0.1 が解ければよい。 121.5 < 3^n log(121.5) < n(log(3)) log(121.5)/log(3) < n 4.369 < n より、n は 5。 問1.15 b 反復的操作のため、スペースは O(1) ステップ数は n が三倍になると一つ増えるので O(log3(n))

本文

1.2.4 べき乗
再帰的プロセス、反復的プロセスを使用した場合のオーダーと、更に逐次平方を利用した場合のオーダーの比較。
O(log n) にできた場合の効果。

問題解答

問1.16
自分の書いたコードは以下。

(define (fast-expt b n)
  (define (even? v)
    (= (remainder v 2) 0))

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

  (expt-iter 1 b n))

答え合わせをして気づいたのだが、 even? が真だった場合に評価されるところが末尾最適化されないので解答としては不正解。

生活習慣が(今のところ)ガラッと変わって夜に寝るのがものすごく早くなったので、当分は朝に勉強時間を設けるようにしてみます。
どういうペースでやるのがいいのか、当分は試行錯誤が続きそうです。

問題解答

問題1.14
木の展開はひたすら手を動かす問題。
オーダーについてはよくわからなかったので先人の記録を頼る(ただ、ちょいちょい間違いがあるような気がするので後述のサイトを参考にした方がよさそう)。また、そこから先に更に詳しい解説が。

cc が呼ばれる度に、 1,0 もしくは二つのサブツリーの和を返す。そして、ツリー中の各ノードでは一処理をおこなう。
amount n と kinds-of-coints が 5 の場合、処理の数は (1 + (cc n 4) の処理の数 + (cc (-n 50 5)) の処理の数)。以後、
N(n,m) を subtree (cc n m) によっておこなわれる処理の数とする。

これを踏まえて N について考える。

N(n,　5) = 1 + N(n,　4) + N((n-50), 5)
N(n,　4) = 1 + N(n,　3) + N((n-25), 4)
N(n,　3) = 1 + N(n,　2) + N((n-10), 3)
N(n,　2) = 1 + N(n,　1) + N((n-5), 2)
N(n,　1) = 1 + N(n,　0) + N((n-1), 1)

N(n,　0) = 1
N((n-1),　1) = N(n, 0) + N((n-2), 1)

(n　-　n) まで展開される。

これを後ろからのぼっていく。

N((n-n, 1) = N(0, 1) = 1
N((n-(n-1), 1) = N(1, 1) = 1 + N(1, 0) + N(0, 1) = 1 + 1 + 1 = 3
N((n-(n-2), 1) = N(2, 1) = 1 + N(2, 0) + N(1, 1) = 1 + 1 + 3 = 5
N((n-(n-3), 1) = N(3, 1) = 1 + N(3, 0) + N(2, 1) = 1 + 1 + 5 = 7

つまり、 N(n, 1) = 2n+1

よって、オーダーは Θ(n)。

同様にして N(n, 2) について考える。

N(n, 2) = 1 + N(n, 1) + N((n-5) 2)
= 1 + N(n, 1) + N(n, 1) + N((n-10) 2)

n-5x <= 0 になるまで展開されるので、ざっくり n/5 回繰り返される。 そして、N(n, 1) は Θ(n) なので Θ(n*n/5) = Θ(n^2)。 同様に N(n, 3), N(n, 4), N(n, 5) を考えると N(n, 5) のオーダーは Θ(n^5)。 うはー。一問、2行に二時間かけてもうた。。。

何だかんだモロモロ終って今日から通常営業に戻ります。数日休んだだけでタスクが山盛り積もってて、これを崩すだけでかなーり大変そうなんですが(汗

問題解答

問1.12
再帰ということで、効率を考えなければさくっと書ける。

(define (pascalTriangle i j)
  (cond ((= j 0) 1)
        ((= i j) 1)
        ((< i j) 0)
        (else (+ (pascalTriangle (- i 1) (- j 1)) (pascalTriangle (- i 1) j)))))

問1.13
問題だけだとどこから手をつけたら。。。という感じだったものの、ヒントをそのまま実装したら確認できた。

(define (fib n)
  (cond ((= n 0) 0)
         ((= n 1) 1)
         (else (+ (fib (- n 1))
                  (fib (- n 2))))))

(define (phi i)
  (define (phi-iter count)
    (if (= count 1)
        (/ (+ 1 (sqrt 5)) 2)
        (* (/ (+ 1 (sqrt 5)) 2) (phi-iter (- count 1)))))

  (phi-iter i))

(define (psi i)
  (define (psi-iter count)
    (if (= count 1)
        (/ (- 1 (sqrt 5)) 2)
        (* (/ (- 1 (sqrt 5)) 2) (psi-iter (- count 1)))))

  (psi-iter i))

(define (checkFib n)
  (- (/ (- (phi n) (psi n)) (sqrt 5)) (fib n)))

というか、、、、SICP、問題が多いな(汗。問題をマメにやってるとなかなか進まない。そんなものなんだろうか?

本文

1.2.3 増加の程度
一般的には計算量 O が注目されがちな、オーダーの話。ここでは計算量に限らずメモリの使用量や一般的なリソースの消費の度合いを示す概念として説明されている。

今日はここまで。一日一ページづつしか進められていないのがまどろっこしい気はするものの、やり続けることに価値があるということで亀の歩みで続けるようにする。

本文

反復アルゴリズムに慣れるために両替が例に上がっている。ただ、ここで書かれている日本語がよくわからない(汗。
しかたないので原文もあわせて読みつつ何を言っているのか解釈(実際には不安に思ったところに曖昧さはなかった)。

註33の内容を試しにやってみる。両替を cc 、d を使用する硬貨とすると

(cc d 10)
(cc 1 10) + (cc 5 5)
(cc 1 9) + (cc 5 5) → (cc 1 n) は (cc 1 0) になり、条件より 1 に置きかわる
1 + (cc 5 5)
1 + (cc 1 5) + (cc 5 0) → (cc 1 5) は先の計算の途中にも出て、1 に置きかわる。また、(cc 5 0) は条件より 1
1 + 1+ 1 = 3

という感じ。硬貨の額面金額を取得するために配列が使えないと、それだけで問題が難しくなるような気がする。

問題解答

問題1.11
再帰は簡単。

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

反復でやっぱりハマるものの、うっすらといつも使っているループとの対応が取れてきた気がする。
自分の解答は以下の通り。

(define (f n)
    (define (f-iter i v0 v1 v2)
        (cond ((< n 3) n)
                 ((= i (- n 3)) (+ v0 v1 v2))
                 (else (f-iter (+ i 1) v1 v2 ))))
    (f-iter 0 0 1 2))

。。。と思って回答を見たら全然違う(そもそも問題を間違えていた)

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

(define (f-iter a b c n)
    (cond ((= n 0) c)
            ((= n 1) b)
            ((= n 2) a)
            (else (f-iter (+ a b b c c c) a b (- n 1)))))

ループだとカウントアップしていくのに、反復だとカウントダウンしていく感覚が何だかなじめない。
ただ、確かに数学的にはこっちの方がそれっぽい気はする。
頭の中に値が変化するモデルが組み立てられれば、反復の方が簡潔かつ柔軟に記述できそうな気はする。

問題解答

問題1.9

前者は (+ a b) が (inc (+ (a-1) b)) と展開できるので、a が 0 になるまで繰り返し展開された後で集約されていきます。そのため再帰的。後者は (+ a b) が (+ (a-1) (b+1)) と置き換えられ、a が 0 になるまで繰り返し置き換えられるので反復的。

問題1.10
(A 1 10) は手で何とか展開できたものの、 (A 2 4) は大変すぎるので実行して動作確認しました。
回答っぽいのには辿り着いたけど、2^..^n の計算の仕方が。。。。 f の時って 2n なので、その時でも一般化された (A m n) って成り立つのかがわからない。ざっくりした流れはつかめたので置いておくことにします。

本文

1.1.2 木構造再帰
再帰版の fib は一瞬で書けたものの、反復版でつまづく(というか、今もモヤッとしている)。反復の書き方がどうも慣れない。
明日、反復の復習をします。