Scheme - 手続きによる抽象の構築(手続きとその生成するプロセス(例: 素数性のテスト(大きな数値について)))

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

その他参考書籍

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

問題 1.25.

問題の手続きだと、remainder手続きの第一引数が高速素数テストの場合のremainder手続きが受け取る第一引数より大きくなるので、remainder手続きの性能が、引数の大きさにより大きなさが出る場合(実際に大きな差が出る。)には、高速素数テストと同じに使えない。

コード(BBEdit, Emacs)

sample25.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 slow-prime?
  (lambda (n times)
    (cond ((= times 0) #t)
          ((fermat-test-slow n)
           (slow-prime? n (- times 1)))
          (else #f))))

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

(define expmod-slow
  (lambda (base exp m)
    (remainder (fast-expt base exp) m)))

(define fast-expt
  (lambda (b n)
    (cond ((= n 0) 1)
          ((even? n) (square (fast-expt b (/ n 2))))
          (else (* b (fast-expt b (- n 1)))))))

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

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

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

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

(search-for-primes-slow 1000 1010)
(newline)
(search-for-primes-fast 1000 1010)
(newline)

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

$ ./sample25.scm

1001
1003
1005
1007
1009 *** 16350

1001
1003
1005
1007
1009 *** 207
$