Scheme - 手続きとその生成するプロセス(素数性のテスト(ステップ数と特殊形式(if)、アルゴリズムの速度))

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

その他参考書籍

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

問題 1.23.

コード(BBEdit, Emacs)

sample.scm

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

(use srfi-11)

(define (next n)
  (if (= next 2)
      3
      (+ n 2)))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (next test-divisor)))))

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

(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (divides? a b)
  (= (remainder b a) 0))

(define (prime? n)
  (= n (smallest-divisor n)))

;; (use srfi-11)が必要
(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 (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (runtime) start-time))))

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

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

$ gosh
gosh> (load "./sample.scm")
#t
gosh> (timed-prime-test 10000000019)

10000000019 *** 18664#<undef>
gosh> (timed-prime-test 10000000033)

10000000033 *** 20809#<undef>
gosh> (timed-prime-test 10000000061)

10000000061 *** 22463#<undef>
gosh> (timed-prime-test 100000000003)

100000000003 *** 75820#<undef>
gosh> (timed-prime-test 100000000019)

100000000019 *** 63284#<undef>
gosh> (timed-prime-test 100000000057)

100000000057 *** 59784#<undef>
gosh> (timed-prime-test 1000000000039)

1000000000039 *** 192510#<undef>
gosh> (timed-prime-test 1000000000061)

1000000000061 *** 197593#<undef>
gosh> (timed-prime-test 1000000000063)

1000000000063 *** 193760#<undef>
gosh> (timed-prime-test 10000000000037)

10000000000037 *** 606741#<undef>
gosh> (timed-prime-test 10000000000051)

10000000000051 *** 611787#<undef>
gosh> (timed-prime-test 10000000000099)

10000000000099 *** 607082#<undef>
gosh> (timed-prime-test 100000000000031)

100000000000031 *** 2064317#<undef>
gosh> (timed-prime-test 100000000000067)

100000000000067 *** 1932842#<undef>
gosh> (timed-prime-test 100000000000097)

100000000000097 *** 2089223#<undef>
gosh> (/ 27414 18664.0)
1.4688169738534076
gosh> (/ 30205 20809.0)
1.4515353933394204
gosh> (/ 27488 22463.0)
1.2237011975248187
gosh> (/ 93219 75820.0)
1.2294777103666579
gosh> (/ 89957 63284.0)
1.421480943050376
gosh> (/ 87753 59784.0)
1.4678342031312726
gosh> (/ 293729 192510.0)
1.525785673471508
gosh> (/ 283460 197593.0)
1.434564989650443
gosh> (/ 285646 193760.0)
1.4742258464079274
gosh> (/ 904050 606741.0)
1.490009740564755
gosh> (/ 893985 611787.0)
1.4612683826233641
gosh> (/ 887987 607082.0)
1.4627134390411838
gosh> (/ 2856818 2064317.0)
1.3839047006830831
gosh> (/ 2840096 1932842.0)
1.46938859979243
gosh> (/ 3103413 2089223.0)
1.4854388449677225
gosh> (exit)
$

問題 1.22と比較。

timed-prime-testによる計測結果

素数	問題 1.22	問題 1.23	比
10000000019	27414	18664	1.4688169738534076
10000000033	30205	20809	1.4515353933394204
10000000061	27488	22463	1.2237011975248187
100000000003	93219	75820	1.2294777103666579
100000000019	89957	63284	1.421480943050376
100000000057	87753	59784	1.4678342031312726
1000000000039	293729	192510	1.525785673471508
1000000000061	283460	197593	1.434564989650443
1000000000063	285646	193760	1.4742258464079274
10000000000037	904050	606741	1.490009740564755
10000000000051	893985	611787	1.4612683826233641
10000000000099	887987	607082	1.4627134390411838
100000000000031	2856818	2064317	1.3839047006830831
100000000000067	2840096	1932842	1.46938859979243
100000000000097	3103413	2089223	1.4854388449677225

ステップ数を半分にしても、二倍速く走らない。比が2と違うのは、ステップ数を減らすために導入したnext手続きは、ifによる判定を行う(その際手続き=を使う)ので、その分速度が落ちるから。