Scheme - 手続きとその生成するプロセス(例: 素数性のテスト(Carmichael数とFermatテスト))

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション)の1(手続きによる抽象の構築)、1.2(手続きとその生成するプロセス)、1.2.6(例: 素数性のテスト)の問1.27を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 1.27.

コード

sample.scm

(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-all-inner n b)
  (define (try-it a)
    (= (expmod a n n) a))
  (cond ((= b 0) try-it 0)
        ((try-it b) (try-it (- b 1)))
        (else false)))

(define fermat-test-all n)
  (fermat-test-all-inner n (- n 1)))

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

1 ]=> (fermat-test-all 2)

;Value: #t

1 ]=> (fermat-test-all 3)

;Value: #t

1 ]=> (fermat-test-all 4)

;Value: #f

1 ]=> (fermat-test-all 5)

;Value: #t

1 ]=> (fermat-test-all 6)

;Value: #f

1 ]=> (fermat-test-all 7)

;Value: #t

1 ]=> (fermat-test-all 8)

;Value: #f

1 ]=> (fermat-test-all 9)

;Value: #f

1 ]=> (fermat-test-all 10)

;Value: #f

1 ]=> (fermat-test-all 100)        

;Value: #f

1 ]=> (fermat-test-all 101)

;Value: #t

1 ]=> (fermat-test-all 102)

;Value: #f

1 ]=> (fermat-test-all 103)

;Value: #t

1 ]=> (fermat-test-all 104)

;Value: #f

1 ]=> (fermat-test-all 105)

;Value: #f

1 ]=> ; Carmichael数
(fermat-test-all 561)

;Value: #t

1 ]=> (fermat-test-all 1105)

;Value: #t

1 ]=> (fermat-test-all 1729)

;Value: #t

1 ]=> (fermat-test-all 2465)

;Value: #t

1 ]=> (fermat-test-all 2821)

;Value: #t

1 ]=> (fermat-test-all 6601)

;Value: #t

1 ]=> ^D
End of input stream reached.
Moriturus te saluto.

ということで、試したCarmichael numbersは素数ではないけど、Fermatテスト(randomな数を与えられた回数だけテストするのではなく、a < nなる全てのaでa^nがnをほうとしてaの合同になるかどうかみる手続き版)を通る。ということで、Carmichael数はFermatテストをだます数。