Scheme - 手続きによる抽象の構築(手続きとその生成するプロセス(例: 素数性のテスト(確率的方法, Fermatテスト)))

計算機プログラムの構造と解釈[第2版]
(翔泳社)
ハロルド エイブルソン (著) ジュリー サスマン (著)
ジェラルド・ジェイ サスマン (著)
Harold Abelson (原著) Julie Sussman (原著)
Gerald Jay Sussman (原著) 和田 英一 (翻訳)

開発環境

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

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

その他参考書籍

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

問題 1.24.

Fermatテストで1,000,000素数をテストする時間は、1000近くの素数をテストする時間と比べ、約2倍速と予想。

コード(BBEdit, Emacs)

sample24.scm

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

(use srfi-27)                           ; random-integer

(define square (lambda (x) (* x x)))
(define (runtime)
  (use srfi-11)
  (let-values (((a b) (sys-gettimeofday)))
    (+ (* a 1000000) b)))

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

(define fast-prime?
  (lambda (n times)
    (cond ((= times 0) #t)
          ((fermat-test n)
           (fast-prime? n (- times 1)))
          (else #f))))

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

(define expmod
  (lambda (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 (timed-prime-test-fast n)
  (newline)
  (display n)
  (start-prime-test-fast n (runtime)))

(define (start-prime-test-fast n start-time)
  (if (fast-prime? n 10)
      (report-prime (- (runtime) start-time))))

(define search-for-primes-fast
  (lambda (a b)
    (if (= (remainder a 2) 0)
        (search-for-primes-iter-fast (+ a 1) b)
        (search-for-primes-iter-fast a b))))

(define search-for-primes-iter-fast
  (lambda (a b)
    (if (< a b)
        (begin  (timed-prime-test-fast a)
                (search-for-primes-iter-fast (+ a 2) b)))))


(define primes (list 1009 1013 1019
                     10007 10009 10037
                     100003 100019 100043
                     1000003 1000033 1000037))

(for-each (lambda (n)
            (timed-prime-test-fast n))      
          primes)
(newline)

(search-for-primes-fast 1000000 1000050)
(newline)

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

$ ./sample24.scm

1009 *** 371
1013 *** 407
1019 *** 256
10007 *** 353
10009 *** 375
10037 *** 272
100003 *** 311
100019 *** 505
100043 *** 555
1000003 *** 585
1000033 *** 516
1000037 *** 533

1000001
1000003 *** 352
1000005
1000007
1000009
1000011
1000013
1000015
1000017
1000019
1000021
1000023
1000025
1000027
1000029
1000031
1000033 *** 625
1000035
1000037 *** 572
1000039 *** 576
1000041
1000043
1000045
1000047
1000049
$