Scheme - 手続きによる抽象の構築(手続きとその生成するプロセス(例: 素数性のテスト(Miller-Rabinテスト)))

計算機プログラムの構造と解釈[第2版]
原著

開発環境

• OS X El Capitan - Apple (OS)
• Emacs(Text Editor)
• Scheme (プログラミング言語)
• kscheme (ksi)(github) (処理系)

計算機プログラムの構造と解釈[第2版](ハロルド エイブルソン (著)、ジュリー サスマン (著)、ジェラルド・ジェイ サスマン (著)、Harold Abelson (原著)、Julie Sussman (原著)、Gerald Jay Sussman (原著)、和田 英一 (翻訳)、翔泳社、原著: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の第1章(手続きによる抽象の構築)、1.2(手続きとその生成するプロセス)、1.2.6(例: 素数性のテスト)、問題1.28.を取り組んでみる。

その他参考書籍

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

問題1.28.

コード(Emacs)

(begin
  (newline)
  (load "procedures.scm")

  (define primes '(1009 1013 1019 1000003 1000033 1000037))
  (define carnichael-numbers '(561 1105 1729 2465 2821 6601))
  
  (define (expmod base exp m)
    (if (= exp 0)
         1
         (if (even? exp)
             ((lambda ()
                (define t1 (expmod base (/ exp 2) m))
                (define t2 (square t1))
                (if (and (not (= t1 1))
                         (not (= t1 (- m 1)))
                         (= (remainder t2 m) 1))
                    0
                    (remainder t2 m))))
             (remainder (* base (expmod base (- exp 1) m)) m))))
  
  (define (fermat-test n)
    (define (try-it a)
      (= (expmod a n n) a))
    (try-it (+ 1 (random (- n 1)))))
  
  (define (miller-rabin-test n)
    (define (try-it a)
      (= (expmod a (- n 1) n) 1))
    (try-it (+ 1 (random (- n 1)))))
  
  (define (fast-prime? n times)
    (if (= times 0)
        #t
        (if (miller-rabin-test n)
            (fast-prime? n (- times 1))
            #f)))

  (for-each (lambda (n)
              (display n)
              (display ": ")
              (display (fast-prime? n 1))
              (newline))
            (append primes carnichael-numbers))
  (newline)
  'done)

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

$ ksi < sample28.scm
ksi> 
1009: #t
1013: #t
1019: #t
1000003: #t
1000033: #t
1000037: #t
561: #f
1105: #f
1729: #f
2465: #f
2821: #f
6601: #f

=> done
ksi> $