さあ面白くなってきた。
素数を求めるのに必要な時間を調べ、考察せよ
C言語なら単純なforループになるコードだが、Lispだと末尾再帰を使って解く必要がある。
残念ながら自力で書くことは出来なかっので、AnswerBookをコピーしてコード読み。
(define (search-for-primes from n) (cond ((= n 0) (newline) 'done) ((even? from) (search-for-primes (+ from 1) n)) ((timed-prime-test from) (search-for-primes (+ from 2) (- n 1))) (else (search-for-primes (+ from 2) n)))) (define (timed-prime-test n) (newline) (display n) (start-prime-test n (get-internal-real-time))) (define (start-prime-test n start-time) (if (prime-loop n 500) (report-prime (- (get-internal-real-time) start-time)))) (define (prime-loop n try-num) (define (iter i) (cond ((= i 0) 'done) ((prime? n) (iter (- i 1))) (else (iter (- i 1))))) (iter try-num) (prime? n)) (define (report-prime elapsed-time) (display " *** ") (display elapsed-time))
なるほど、
(cond ((= n 0) (newline) 'done)
のように書くと、
guile> (search-for-primes 100 30) . . 159 done
対話モードの最後に'done'が出力されるのか。
所で
(define (search-for-primes from n) (cond ((= n 0) (newline) 'done) ((even? from) (search-for-primes (+ from 1) n)) ((timed-prime-test from) (search-for-primes (+ from 2) (- n 1))) (else (search-for-primes (+ from 2) n))))
の、timed-prime-testは何が返り値として返ってくるんだろ？
素数の場合も、そうじゃない場合も最後に実行されるのはdisplay関数のはず。
- とりあえず、自分のマシンだと素数計算が早くて時間が正確に計測できなかったので、prime-loopで複数回(自分の環境では501回)繰り返す事にした。AnswerBookでは、time-differenceという関数を使ってさらに正確に測っている。
- guileにruntimeという関数は無かったのでget-internal-real-timeという関数を使っている。ドキュメントが少なくて、こういう関数があるということを調べるのが大変だった...。
とりあえず実行結果は以下。
長くなってきたので詳しい解析は次の記事で。
guile> (search-for-primes 1000 30) 1001 1003 1005 1007 1009 *** 62 1011 1013 *** 63 1015 1017 1019 *** 62 1021 *** 63 1023 1025 1027 1029 1031 *** 63 1033 *** 47 1035 1037 1039 *** 62 1041 1043 1045 1047 1049 *** 46 1051 *** 63 1053 1055 1057 1059 done
