メイン


Lisp Archives

2006年4月 6日

本日のSICP

素数であるかを判定するFermatテストをお勉強。
ほぼ写経なんですが,コードはこんなかんじ。(gauche)


(use math.mt-random)
(define mt-m (make :seed (sys-time))) (define (square x) (* x x))

(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))

(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(try-it (+ 1 (mt-random-integer mt-m (- n 1)))))

(define (fast-prime? n times)
(cond ((= times 0) true)
((fermat-test n) (fast-prime? n (- times 1)))
(else false)))

(display (fermat-test 561))
(newline)


で,これのおもしろいのは確率的に素数判定をおこなうということ。
さらにおもしろいのが,Carmichael numbersというFermatテストを騙すことができる数があることが明らかになっていること。しかも,1105とか明らかに素数でない数でFermatテストが騙される。なぜなぜ?
そのうえ,100,000,000以下のCarmichael numbersは255個ある,と。なんか意味ありげな数字だ。うーん,なにかありそう。

Carmichael numbersは完全疑似素数とよばれるのか。なんかかっこいい。

と,SICPの29Pのお話でした。
博士の愛した数式を読んだ直後ってこともあってめちゃくちゃ興味津々。こういう深追いは楽しいなぁ。
博士の愛した数式


2006年9月21日

SICP Open CourseWare

計算機プログラムの構造と解釈

最近ちょっとサボり気味のSICP読書会でした。
サボると落ちこぼれるので、なんとかならんものかと効率的な予習・復習方法を探していたのですが、
MITのOpen CourseWareの授業資料がとてもよい副読本であることを発見しました。序盤でSchemeの文法的なことをまとめてやって、それから本題のアルゴリズムに進むような流れらしい。SICP本はむしろ問題集みたいな扱い。
これでがんばろう。

# はてなのSICPグループで読書日記を書き始めました。













Powered by
Movable Type 4.25