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倍に伸びる。つまり、\sqrt{10}であることが確認できた。

問題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をあらかじめ計算してから、ループを回せばもっと効率が良くなると思う。