SICPを読む(16) 問題1.21 - 1.23 Schemeは案外早い。
どうやら、現代のPCはかなり性能がいいらしい。
問題1.21
(smalltest-divisor 19) ; 19 (smalltest-divisor 199) ; 199 (smalltest-divisor 1999) ; 1999 (smalltest-divisor 19999) ; 7
簡単!
問題1.22
テスト時間を計る問題。
MzSchemeにはruntimeが無いので、代わりにcurrent-millisecondsを使った。current-millisecondsはマイナスの値を返すので注意。
(define (runtime) (current-milliseconds)) (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 (search-for-prime n m) (define (iter i) (cond ((<= i m) (timed-prime-test i) (iter (+ i 1))))) (iter n))
非力なノートPC(1.5 GHz)のはずなんですが。。。
やっと1秒突破。
(search-for-prime 100000000000 100000000010) 100000000000 ...(略 100000000003 *** 1184 ...(略 100000000010
高速化とかどうでもいい感じになってきた(笑
Schemeは案外早い。
解答を見たら、奇数のみだったので、修正。
(define (search-for-prime from n) (cond ((< n 0) (newline) 'done) ((even? from) (search-for-prime (+ from 1) (- n 1))) (else (timed-prime-test from) (search-for-prime (+ from 2) (- n 2))))) (search-for-prime 1000000000000 100)
引数をちょっと変更した。解答とはちょっと違う方法。
桁を10倍に増やすと、計算時間が約3倍に伸びる。つまり、であることが確認できた。
問題1.23
(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 (find-divisor n test-divisor) (cond ((> (square test-divisor) n) n) ((even? test-divisor) (find-divisor n (+ test-divisor 1))) ((divides? test-divisor n) test-divisor) (else (find-divisor n (+ test-divisor 2)))))
経過時間は、約半分。正確には55%位。別解答の方もあんまり変わらず。
2をあらかじめ計算してから、ループを回せばもっと効率が良くなると思う。