開発環境
- 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.21、1.22を解いてみる。
その他参考書籍
問題 1.21.
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
$ scheme
MIT/GNU Scheme running under MacOSX
Type `^C' (control-C) followed by `H' to obtain information about interrupts.
Copyright (C) 2011 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Image saved on Friday April 13, 2012 at 9:02:52 AM
Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118
Edwin 3.116
1 ]=>
(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))
(smallest-divisor 199)
(smallest-divisor 1999)
(smallest-divisor 19999)
;Value: smallest-divisor
1 ]=>
;Value: find-divisor
1 ]=>
;Value: divides?
1 ]=>
;Value: 199
1 ]=>
;Value: 1999
1 ]=>
;Value: 7
1 ]=> ^D
End of input stream reached.
Moriturus te saluto.
$
最小除数はそれぞれ199は199、1999は1999、19999は7。
問題 1.22.
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
$ scheme
MIT/GNU Scheme running under MacOSX
Type `^C' (control-C) followed by `H' to obtain information about interrupts.
Copyright (C) 2011 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Image saved on Friday April 13, 2012 at 9:02:52 AM
Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118
Edwin 3.116
1 ]=>
(define (search-for-primes start stop)
(if (even? start)
(search-for-primes-inner (+ start 1) stop 0)
(search-for-primes-inner start stop 0)))
(define (search-for-primes-inner start stop n)
(cond ((or (> start stop)
(= n 3)))
(else (timed-prime-test start)
(if (prime? start)
(search-for-primes-inner (+ start 2) stop (+ n 1))
(search-for-primes-inner (+ start 2) stop n)))))
(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 (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 (divi
;Value: search-for-primes
1 ]=>
;Value: search-for-primes-inner
1 ]=>
;Value: timed-prime-test
1 ]=>
;Value: start-prime-test
1 ]=>
;Value: report-prime
1 ]=>
;Value: smallest-divisor
1 ]=>
;Value: find-divisor
1 ]=> ))
(define (prime? n)
(= n (smallest-divisor n)))
(search-for-primes 10000000000 100000000000)
(search-for-primes 100000000000 1000000000000)
(search-for-primes 1000000000000 10000000000000)
(search-for-primes 10000000000000 100000000000000)
;Value: divides?
1 ]=>
;Value: prime?
1 ]=>
10000000001
10000000003
10000000005
10000000007
10000000009
10000000011
10000000013
10000000015
10000000017
10000000019 *** .24
10000000021
10000000023
10000000025
10000000027
10000000029
10000000031
10000000033 *** .2400000000000001
10000000035
10000000037
10000000039
10000000041
10000000043
10000000045
10000000047
10000000049
10000000051
10000000053
10000000055
10000000057
10000000059
10000000061 *** .22999999999999998
;Value: #t
1 ]=>
100000000001
100000000003 *** .7399999999999998
100000000005
100000000007
100000000009
100000000011
100000000013
100000000015
100000000017
100000000019 *** .7399999999999998
100000000021
100000000023
100000000025
100000000027
100000000029
100000000031
100000000033
100000000035
100000000037
100000000039
100000000041
100000000043
100000000045
100000000047
100000000049
100000000051
100000000053
100000000055
100000000057 *** .7400000000000002
;Value: #t
1 ]=>
1000000000001
1000000000003
1000000000005
1000000000007
1000000000009
1000000000011
1000000000013
1000000000015
1000000000017
1000000000019
1000000000021
1000000000023
1000000000025
1000000000027
1000000000029
1000000000031
1000000000033
1000000000035
1000000000037
1000000000039 *** 2.339999999999999
1000000000041
1000000000043
1000000000045
1000000000047
1000000000049
1000000000051
1000000000053
1000000000055
1000000000057
1000000000059
1000000000061 *** 2.34
1000000000063 *** 2.34
;Value: #t
1 ]=>
10000000000001
10000000000003
10000000000005
10000000000007
10000000000009
10000000000011
10000000000013
10000000000015
10000000000017
10000000000019
10000000000021
10000000000023
10000000000025
10000000000027
10000000000029
10000000000031
10000000000033
10000000000035
10000000000037 *** 7.93
10000000000039
10000000000041
10000000000043
10000000000045
10000000000047
10000000000049
10000000000051 *** 8.030000000000001
10000000000053
10000000000055
10000000000057
10000000000059
10000000000061
10000000000063
10000000000065
10000000000067
10000000000069
10000000000071
10000000000073
10000000000075
10000000000077
10000000000079
10000000000081
10000000000083
10000000000085
10000000000087
10000000000089
10000000000091
10000000000093
10000000000095
10000000000097
10000000000099 *** 8.230000000000004
;Value: #t
1 ]=> ^D
End of input stream reached.
Moriturus te saluto.
$
1000、10,000、100,000、1,000,000だと時間小さかったので、それぞれ1.e+10、1.e+11、1.e+12、1.e+13で計測してみる事に。3つの平均をそれぞれ比べてみると、だいだい10倍ごとに√10倍(約3.16…倍)になってるっぽいのから時間のデータはΘ(√n)の増加の程度を支持する。(メモ: 最初、1.e+10と書いたけど、その指数計算自体も時間がかかるみたいだったから、そのまま10000000000と書き直して実行。)
結果はプログラムが計算に必要なステップ数に比例した時間で走るという考えに合っている。(ステップ数が√10倍になるごとに、時間も√10倍になっている。)
0 コメント:
コメントを投稿