開発環境
- 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.25.を解いてみる。
その他参考書籍
- Instructor's Manual to Accompany Structure & Interpretation of Computer Programs
- プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)
問題 1.25.
いずれの定義のexpmod手続きも手続きの適用結果は同じになる。
baseのexp乗がmより十分に大きい場合を考える。
問題のAlyssa P. Hackerの定義のexpmod手続きの場合、mを法としたmより遥かに大きい値の剰余を求めることになる。(remainder手続きは、mより遥かに大きい数値を扱うことになる。)
一方、本節中の定義のexpmod手続きの場合は、remainder手続きはmより遥かに大きい値を扱うことを回避できる。
square手続きの適用回数は両者とも同じ。
remainder手続きの適用回数は問題の定義のexpmod手続きの場合は1回、本節のexpmod手続きの場合はそれより大きい回数になる。
ということで、両者expmod手続きの速度の違いは、十分に大きな数値を扱えるか、扱える場合はremainder手続きがある数より十分に大きい値をある数で割った剰余を求める速度により違いが出てくる。remainder手続きがある数より十分に大きい値をある数で割った剰余を求める速度が、十分に速い場合は問題のAlyssa P. Hackerの定義のexpmod手続き、遅い場合は本節の定義のexpmod手続きが高速となる。
違いを確認。
コード(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)))
;; 問題 1.25によるexpmod手続きの定義とこの手続きを使ったFermatテスト、素数性のテスト
(define (expmod-1 base exp m)
(remainder (fast-expt base exp) m))
(define (fermat-test-1 n)
(define (try-it a)
(= (expmod-1 a n n) a))
(try-it (+ (random-integer (- n 1)))))
(define (fast-prime-1? n times)
(cond ((= times 0) true)
((fermat-test-1 n) (fast-prime-1? n (- times 1)))
(else false)))
;; Fermatテスト回数を100回とする
;; 本節の場合
(define (start-prime-test n start-time)
(if (fast-prime? n 100)
(report-prime (- (runtime) start-time))))
(define (timed-prime-test n)
(display n)
(start-prime-test n (runtime)))
;; 問題の場合
(define (start-prime-test-1 n start-time)
(if (fast-prime-1? n 1000)
(report-prime (- (runtime) start-time))))
(define (timed-prime-test-1 n)
(display n)
(start-prime-test-1 n (runtime)))
;;
(define true #t)
(define false #f)
(define (square x) (* x x))
(define (runtime)
(let-values (((a b) (sys-gettimeofday)))
(+ (* 1000000 a) b)))
(define (report-prime elapsed-time)
(display " *** ")
(print elapsed-time))
(define (fast-expt b n)
(expt-iter b n 1))
(define (expt-iter b n a)
(cond ((= n 0) a)
((even? n) (expt-iter (square b) (/ n 2) a))
(else (expt-iter b (- n 1) (* a b)))))
(define (even? n)
(= (remainder n 2) 0))
;; 二つの定義での速度を比較
(define n 101)
(print "本節の定義のexpmod手続きの場合")
(timed-prime-test n)
(print "問題の定義のexpmod手続きの場合")
(timed-prime-test-1 n)
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
$ ./sample.scm 本節の定義のexpmod手続きの場合 101 *** 549 問題の定義のexpmod手続きの場合 101 *** 10299 $ ./sample.scm 本節の定義のexpmod手続きの場合 101 *** 551 問題の定義のexpmod手続きの場合 101 *** 11611 $ ./sample.scm 本節の定義のexpmod手続きの場合 101 *** 554 問題の定義のexpmod手続きの場合 101 *** 10345 $ ./sample.scm 本節の定義のexpmod手続きの場合 101 *** 551 問題の定義のexpmod手続きの場合 101 *** 10428 $ ./sample.scm 本節の定義のexpmod手続きの場合 101 *** 550 問題の定義のexpmod手続きの場合 101 *** 10539 $
十分に大きな数値を扱うremainder手続きが遅くなり、Alyssa P. Hackerの主張は正しくない。そして、高速素数テストと同じに使えない。
0 コメント:
コメントを投稿