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

計算機プログラムの構造と解釈
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.24.を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs
• プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)

問題 1.24.

コード(BBEdit, Emacs)

sample.scm

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

(use srfi-11) ;; runtime手続きで使うsys-gettimeofday手続きのため必要
(use srfi-27) ;; fermat-test手続きで使うrandom-integer手続きのため必要

(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 (random-integer (- n 1)))))

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

;; Fermatテスト回数を1000回とする
(define (start-prime-test n start-time)
  (if (fast-prime? n 1000)
      (report-prime (- (runtime) start-time))))

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

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

(define (runtime)
  (let-values (((a b) (sys-gettimeofday)))
    (+ (* 1000000 a) b)))

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))

(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))

(define primes '(10000000019 10000000033 10000000061
                 100000000003 100000000019 100000000057
                 1000000000039 1000000000061 1000000000063
                 10000000000037 10000000000051 10000000000099
                 100000000000031 100000000000067 100000000000097))

(for-each timed-prime-test primes)

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

$
gosh> (load "./sample")

10000000019 *** 64107
10000000033 *** 68823
10000000061 *** 90062
100000000003 *** 131312
100000000019 *** 87337
100000000057 *** 97408
1000000000039 *** 145733
1000000000061 *** 90992
1000000000063 *** 91824
10000000000037 *** 174043
10000000000051 *** 96148
10000000000099 *** 95866
100000000000031 *** 172429
100000000000067 *** 107017
100000000000097 *** 128780#t
gosh> (/ (log 100000000000000)
         (log 10000000000))
1.4000000000000001
gosh> (/ (+ 172429 107017 128780)
         (+ 64107 68823 90062.0))
1.8306755399296837
gosh> (exit)
$

FermatテストはΦ(log n)の増加なので、それのみを考慮すると、100000000000000(10^14)近くの素数をテストする時間は10000000000(10^10)近くの素数をテストする時間の約1.4倍になると予想される。実際は、Fermatテストを置くなう十分な回数を1000回とした場合、約1.8倍となっている。この違いは、Fermatテストの手続きで、手続き+、手続きrandom-integer、手続き-を適用するという事情で、その分予想より遅くなったと考えられる。