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

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

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• Gauche (処理系)

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: 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
• プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)

問題 1.28.

コード(BBEdit, Emacs)

sample.scm

#!/usr/bin/env gosh
;; -*- coding: utf-8 -*-

(use srfi-27) ;; miller-rabin-test手続きで使うrandom-integer手続きのため必要

;; Miller-Rabinテスト
(define (miller-rabin-test n)
  (define (try-it a)
    (= (expmod a (- n 1) n) 1))
  (try-it (+ 1 (random-integer (- n 1)))))

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

(define (root-test a n)
  (if (and (not (or (= a 1)
                    (= a (- n 1))))
           (= (remainder (square a)
                         n)
               1))
      0
      a))

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

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

(define (square x) (* x x))

(define true #t)
(define false #f)

(for-each (lambda (x)
            (print x " *** " (if (fast-prime? x 1000)
                                 "素数の可能性が極めて高い"
                                 "素数ではない")))
          '(10007 561 1105 1729 2465 2821 6001))

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

$ ./sample.scm 
10007 *** 素数の可能性が極めて高い
561 *** 素数ではない
1105 *** 素数ではない
1729 *** 素数ではない
2465 *** 素数ではない
2821 *** 素数ではない
6001 *** 素数ではない
$