開発環境
- OS X Lion - Apple(OS)
- Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
- プログラミング言語: MIT/GNU Scheme
計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション)の1(手続きによる抽象の構築)、1.2(手続きとその生成するプロセス)、1.2.6(例: 素数性のテスト)の問題1.23、問1.24を解いてみる。
その他参考書籍
問題 1.23.
コード
sample.scm
(define (slow-timed-prime-test n)
(newline)
(display n)
(slow-start-prime-test n (runtime)))
(define (timed-prime-test n)
(newline)
(display n)
(start-prime-test n (runtime)))
(define (slow-start-prime-test n start-time)
(if (slow-prime? n)
(report-prime (- (runtime) start-time))))
(define (start-prime-test n start-time)
(if (prime? n)
(report-prime (- (runtime) start-time))))
(define (report-prime elapsed-time)
(display " *** ")
(display elapsed-time))
(define (slow-smallest-divisor n)
(slow-find-divisor n 2))
(define (smallest-divisor n)
(find-divisor n 2))
(define (slow-find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (slow-find-divisor n (+ test-divisor 1)))))
(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 (next n)
(if (= n 2)
3
(+ n 2)))
(define (divides? a b)
(= (remainder b a) 0))
(define (slow-prime? n)
(= n (slow-smallest-divisor n)))
(define (prime? n)
(= n (smallest-divisor n)))
(define (ratio a b c d e f)
(/ (average a b c) (average d e f)))
(define (average a b c)
(/ (+ a b c) 3.0))
(slow-timed-prime-test 10000000019)
(slow-timed-prime-test 10000000033)
(slow-timed-prime-test 10000000061)
(slow-timed-prime-test 100000000003)
(slow-timed-prime-test 100000000019)
(slow-timed-prime-test 100000000057)
(slow-timed-prime-test 1000000000039)
(slow-timed-prime-test 1000000000061)
(slow-timed-prime-test 1000000000063)
(slow-timed-prime-test 10000000000037)
(slow-timed-prime-test 10000000000051)
(slow-timed-prime-test 10000000000099)
(timed-prime-test 10000000019)
(timed-prime-test 10000000033)
(timed-prime-test 10000000061)
(timed-prime-test 100000000003)
(timed-prime-test 100000000019)
(timed-prime-test 100000000057)
(timed-prime-test 1000000000039)
(timed-prime-test 1000000000061)
(timed-prime-test 1000000000063)
(timed-prime-test 10000000000037)
(timed-prime-test 10000000000051)
(timed-prime-test 10000000000099)
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
*** .25 ;Unspecified return value 1 ]=> 10000000033 *** .24 ;Unspecified return value 1 ]=> 10000000061 *** .26 ;Unspecified return value 1 ]=> 100000000003 *** .7399999999999999 ;Unspecified return value 1 ]=> 100000000019 *** .7500000000000002 ;Unspecified return value 1 ]=> 100000000057 *** .7399999999999998 ;Unspecified return value 1 ]=> 1000000000039 *** 2.38 ;Unspecified return value 1 ]=> 1000000000061 *** 2.3500000000000005 ;Unspecified return value 1 ]=> 1000000000063 *** 2.38 ;Unspecified return value 1 ]=> 10000000000037 *** 7.369999999999999 ;Unspecified return value 1 ]=> 10000000000051 *** 7.510000000000002 ;Unspecified return value 1 ]=> 10000000000099 *** 7.359999999999996 ;Unspecified return value 1 ]=> 10000000019 *** .15000000000000568 ;Unspecified return value 1 ]=> 10000000033 *** .14999999999999858 ;Unspecified return value 1 ]=> 10000000061 *** .14999999999999858 ;Unspecified return value 1 ]=> 100000000003 *** .46000000000000085 ;Unspecified return value 1 ]=> 100000000019 *** .46000000000000085 ;Unspecified return value 1 ]=> 100000000057 *** .46000000000000085 ;Unspecified return value 1 ]=> 1000000000039 *** 1.5700000000000003 ;Unspecified return value 1 ]=> 1000000000061 *** 1.5899999999999963 ;Unspecified return value 1 ]=> 1000000000063 *** 1.480000000000004 ;Unspecified return value 1 ]=> 10000000000037 *** 4.850000000000001 ;Unspecified return value 1 ]=> 10000000000051 *** 5.099999999999994 ;Unspecified return value 1 ]=> 10000000000099 *** 5.32 ;Unspecified return value 1 ]=> (ratio .25 .24 .26 .15000000000000568 .14999999999999858 .14999999999999858) ;Value: 1.6666666666666563 1 ]=> (ratio .7399999999999999 .7500000000000002 .7399999999999998 .46000000000000085 .46000000000000085 .46000000000000085) ;Value: 1.6159420289855042 1 ]=> (ratio 2.38 2.3500000000000005 2.38 1.5700000000000003 1.5899999999999963 1.480000000000004) ;Value: 1.5323275862068964 1 ]=> (ratio 7.369999999999999 7.510000000000002 7.359999999999996 4.850000000000001 5.099999999999994 5.32) ;Value: 1.4564505566470203 1 ]=> ^D End of input stream reached. Moriturus te saluto.
速度比は2になっていない。
テストのステップを半分にしたのに、二倍速く走らない、2と違う事情は、手続きnextでifの述語(= n 2)の評価が加わるから。(その後の(+ n 2)の評価は元の(+ n 1)の評価と数は一致。)
元のステップ数はsquare、divides?、+の3つ掛ける総数nで3n。nextを使うように修正した場合のステップ数はsquare、divides、next(=、+)の4つ掛ける総数n/2で2n。なので、計算上は速度は約3n/2n = 1.5倍になる。(ってことでいいのかな。。なんか結果と少しずれてるけど。)
問題 1.24.
Θ(log n)の増加なので、1,000,000近くの素数をテストする時間は、1,000近くの素数をテストする時間の約2倍(log 1000000 / log 1000)と予想。
実際に計測。(1000の近くの素数は1009、1000000近くの素数は1000003。
コード
sample.scm
(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))
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(try-it (+ 1 (random (- n 1)))))
(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 (prime? n)
(fermat-test n))
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (timed-prime-test 1009) 1009 *** 0. ;Unspecified return value 1 ]=> (timed-prime-test 1000003) 1000003 *** 0. ;Unspecified return value 1 ]=> ^D End of input stream reached. Moriturus te saluto.
値が小さすぎてデータを確認できず。なので値1000、1000000をもっと大きく取ってみたら、今度は素数を時間がかかって求める事が出来ず。。ということで、とりあえず次に進む事に。
0 コメント:
コメントを投稿