開発環境
- 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.26.を解いてみる。
その他参考書籍
- Instructor's Manual to Accompany Structure & Interpretation of Computer Programs
- プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)
問題 1.26.
schemeは作用的順序の評価であるところが注目点。
問題1.24のexpmod手続きの場合、(even? exp)が真の場合、式(expmod base (/ exp 2) m)の計算は一度で済む。
置き換えモデル。(expmod …)の評価結果をaとする。
(square (expmod (base (/ exp 2) m))) (square a) (s* a a)
一方、問題のLouis Reasonerのexpmod手続きの定義だと、式(expmod base (/ exp 2))を2回評価することになる。
置き換えモデル。
(* (expmod base (/ exp 2) m) (expmod base (/ exp 2) m)) (* a a)
よって、増加の程度はΦ(2^n log n) = Φ(n)となり、Φ(log n)のプロセスをΦ(n)のプロセスにしてしまう。
遅くなることを確認。
コード(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 (prime? n)
(= n (smallest-divisor n)))
(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 (start-prime-test n start-time)
(if (prime? n)
(report-prime (- (runtime) start-time))))
(define (timed-prime-test n)
(display n)
(start-prime-test n (runtime)))
;; Fermatテストを使う場合
(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)))
(define (start-prime-test-1 n start-time)
(if (fast-prime? n 1)
(report-prime (- (runtime) start-time))))
(define (timed-prime-test-1 n)
(display n)
(start-prime-test-1 n (runtime)))
;; 問題1.26 Louis Reasonerの定義によるexpmod手続きを使ったFermatテスト
(define (expmod-1 base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (* (expmod-1 base (/ exp 2) m)
(expmod-1 base (/ exp 2) m))
m))
(else
(remainder (* base (expmod-1 base (- exp 1) m))
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)))
(define (start-prime-test-2 n start-time)
(if (fast-prime-1? n 1)
(report-prime (- (runtime) start-time))))
(define (timed-prime-test-2 n)
(display n)
(start-prime-test-2 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))
;;
(print "確率的方法を使わない素数テスト")
(timed-prime-test 10007)
(print "Fermatテストを使った素数テスト")
(timed-prime-test-1 10007)
(print "問題の手続きを使った素数テスト")
(timed-prime-test-2 10007)
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
$ ./sample.scm 確率的方法を使わない素数テスト 10007 *** 57 Fermatテストを使った素数テスト 10007 *** 34 問題の手続きを使った素数テスト 10007 *** 13115 $
0 コメント:
コメントを投稿