(define -ayalog '())

括弧に魅せられて道を外した名前のないプログラマ

SICPを読む_(9)1章_手続きによる抽象の構築(p26-31)

おはようございます!!ドラクエ7やってますか??
やっとルーメンクリアしたあたりで、主人公が勇者極めちゃってたり、マリベルが天地雷鳴師極めちゃったんで、ローズバトラー極めに行こうかと計画してたりします。*1

2月に入ってSICP読むも、なかなかこっちに書くのが進んでなかったのはドラクエ7のせいです。はい。

さて、今日の範囲が終われば高階手続き*2という楽しい分野について書けるので、今日はその手前まで終わらせたいところです!><

1.2.5最大公約数(p26)

そういえばこの前、ユークリッド互除法とかRubyで書いてたなー…。

  • Euclidのアルゴリズム
  • Lameの定理
    • EuclidのアルゴリズムであるGCDの計算にkステップが必要なら、対の小さい方の数はk番目のFibonacci数に等しいかそれより大きい
(define (gcd a b)
  (cond
   ((zero? b) a)
   (else
    (gcd b (modulo a b)))))

あ、僕がSICPの問題とか例題を書くときにifじゃなくてcond使うのは好みの問題だと思ってます。
というか、Scheme手習い読んでたら、癖がつきました。

Scheme手習い

Scheme手習い

問題1.20

正規順序で評価したら19回かな??
remainderじゃなくてmodulo使ってるけど、意味は同じだと思うから問題ない気がする。
作用的順序なら4回だと思う。trace調べ。

(define (gcd a b)
  (if (zero? b)
      a
      (gcd b (modulo a b))))

(gcd 206 40)

(if (zero? 40)
    206
    (gcd 40 (modulo 206 40)))

(if (zero? (modulo 206 40))
    40
    (gcd (modulo 206 40) (modulo 40 (modulo 206 40))))

(if (zero? (modulo 40 (modulo 206 40)))
    (modulo 206 40)
    (gcd (modulo 40 (modulo 206 40)) (modulo (modulo 206 40) (modulo 40 (modulo 206 40)))))

(if (zero? (modulo (modulo 206 40) (modulo 40 (modulo 206 40))))
    (modulo 40 (modulo 206 40))
    (gcd  (modulo (modulo 206 40) (modulo 40 (modulo 206 40)))
	 (modulo (modulo 40 (modulo 206 40)) (modulo (modulo 206 40) (modulo 40 (modulo 206 40))))))

(if (zero? (modulo (modulo 40 (modulo 206 40)) (modulo (modulo 206 40) (modulo 40 (modulo 206 40)))))
    (modulo (modulo 206 40) (modulo 40 (modulo 206 40)))
    (gcd (modulo (modulo 40 (modulo 206 40)) (modulo (modulo 206 40) (modulo 40 (modulo 206 40))))
	 (modulo (modulo (modulo 206 40) (modulo 40 (modulo 206 40)))
		 (modulo (modulo 40 (modulo 206 40)) (modulo (modulo 206 40) (modulo 40 (modulo 206 40)))))))

1.2.6例:素数性のテスト

最近、ProjectEulerとかで素数の計算するのでためになる…気がする。
Euler解くときは除数探索で確実にやらないとまずいきがするんだけどね。

  • Θ(√n)の増加の程度のものと、Θ(log n)の増加の程度の「確率的」アルゴリズムの2種類を学ぶ
除数の探索
  • 除数を見つけることで素数か分かる
  • nはn自身がその最小除数である時に限り、素数である
    • 平方根を越える素因数が存在する場合、平方根より小さい素因数も必ず存在する
    • つまり1と√nの間のテスト用除数があれば良い
  • Θ(√n)の増加の程度
(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond
   ((> (square test-divisor) n) n)
   ((divides? test-divisor n) test-divisor)
   (else
    (find-divisor n (+ test-divisor 1)))))

(define (divides? a b)
  (zero? (modulo a b)))

;; n自身が最小の除数なら素数である
(define (prime? n)
  (= n (smallest-divisor n)))
Fermatテスト
  • Fermatの小定理:nを素数,aをnより小さい正の任意の整数とすると,aのn乗はnを法としてaと合同である.
    • a^n≡a(mod n)ってこと??
  • nが素数じゃないならa<nなほとんどの数について上の関係は成り立たない*3

プログラムはsicpのp28~29からなんだけど、randomとかなくね!?ってことで、SRFI-27使ってます。

(use srfi-27)

(define (expmed base exp m)
  (cond
   ((zero? exp) 1)
   ((even? exp)
    (modulo (square (expmed base (/ exp 2) m))
	    m))
    (else
     (modulo (* base (expmed base (- exp 1) m))
	     m))))

(define (fermat-test n)
  (define (try-it a)
    (= (expmed a n n) a))
  (try-it (+ 1 (random-integer (- n 1)))))

(define (fast-prime? n times)
  (cond
   ((zero? times) #t)
   ((fermat-test n) (fast-prime? n (- times 1)))
   (else #f)))

ちょっと正直、expmedがわかりにくいと感じてしまったのでたぶん下の書き方でも同じ意味を持つと思う。

(define (my-expmed base exp m)
  (modulo (expt base exp) m))

ただ、Θ(log n)の増加の程度とかうんちゃらかんちゃらと言いたいみたいなので、めんどくさい書き方してる気がする。。

確率的方法

上記のようなFermatテストは、nがテストに失敗したら素数でないことは確かだけど、テストに成功してもn素数であることを保証しない。
あるnに対して十分な回数テストを行い、nが常に合格すれば素数である確率は高くなる。(らしい)

問題1.21(p29)

(smallest-divisor 199) ;;=>199
(smallest-divisor 1999) ;;=>1999
(smallest-divisor 19999) ;;=>7

問題1.22(p29)

runtime手続きは組み込み手続きとして、存在しないので後回し。
やりようはあるけど、めんど(ry
(家に帰ってからやるます。たぶん)

問題1.23(p30)

next手続きを書けという事なんでこれでいいでしょう。

(define (find-divisor n test-divisor)
  (cond
   ((> (square test-divisor) n) n)
   ((divided? test-divisor n) test-divisor)
   (else (let ((next (lambda (n)
		       (if (= n 2) 3 (+ n 2)))))
	   (find-divisor n (+ test-divisor 1))))))

問題1.24(p30)

問題1.22同様に(ry

問題1.25(p30)

これ、問題読んでから驚いたけど、僕が上に書いたのと同じですね…。
どうなんだろう。僕は同じと思ってたんだけど…。
計算量に違いが出てくるんだろうなぁとは問題になってるくらいなので、想像できるけど確認方法…。(誰か教えて><)

問題1.26(p30)

結果を2乗すれば済んでいたのが、もう1度同じ計算をしているからかな。
フィボナッチ数列の計算とかそのあたりと似たような理由かと。


ということで、とりあえず30ページまで進めたので、あと2問くらい次のページにあるけど一先ずここまでで一旦終了ー。
ちなみにこれ書き始めたの、2月頭だったのに書き終わったの今*4で笑えない。
あと回しにした問題と、次のページの2問は帰ってからやります><

*1:現在バーサーカーは極めた

*2:「高階」が一発で変換できなくてもやっとした

*3:"ほとんど"が重要みたい

*4:2013/2/18