計算機プログラムの構造と解釈 第二版 P29 問題1.23
教科書通りでだいたい、2倍程度はやくなった。
計算時間が、60%になったってとこか。
10%はなんかのオーバーヘッドとか、1の加算の方が、2の加算より早いとか云々。
変えたのは、21行目から25行目
1 #!/usr/local/bin/gosh 2 ;; -*- coding: utf-8 -*- 3 4 (use ggc.debug.trace) 5 6 ;;runtime;;;;;;;;;;;;;;;;;;;;;; 7 (define (runtime) 8 (use srfi-11) 9 (let-values (((a b) (sys-gettimeofday))) 10 (+ 1000000 b))) 11 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 12 13 ;;1-21;;;;;;;;;;;;;;;;;;;;;;;;; 14 (define (square n) 15 (* n n)) 16 17 18 (define (smallest-divisor n) 19 (find-divisor n 2)) 20 21 (define (find-divisor n test-divisor) 22 (cond ((> (square test-divisor) n) n) 23 ((divides? test-divisor n) test-divisor) 24 (else (find-divisor n (cond ((= test-divisor 2) 3 ) 25 (else (+ test-divisor 2))))))) 26 27 (define (divides? a b) 28 (= (remainder b a) 0)) 29 30 (define (prime? n) 31 (= n (smallest-divisor n))) 32 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 33 34 35 (define (timed-prime-test n) 36 (newline) 37 (display n) 38 (start-prime-test n (runtime))) 39 40 (define (start-prime-test n start-time) 41 (if (prime? n) 42 (report-prime (- (runtime) start-time)))) 43 44 (define (report-prime elapsed-time) 45 (display " *** ") 46 (display elapsed-time)) 47 48 (define (search-for-primes-iter num counter) 49 (cond ((= counter 3)) 50 ((prime? num) (print num) (search-for-primes-iter (+ num 2) (+ counter 1))) 51 (else (search-for-primes-iter (+ num 2) counter)))) 52 53 54 (define (search-for-primes num) 55 (cond ((divides? 2 num) (search-for-primes-iter (+ num 1) 0)) 56 (else (search-for-primes-iter num 0)))) 57 58 59 ;; main 60 (define (main args) 61 (search-for-primes 1000) 62 (search-for-primes 10000) 63 (search-for-primes 100000) 64 (search-for-primes 1000000) 65 (search-for-primes 10000000) 66 (search-for-primes 100000000) 67 (search-for-primes 1000000000) 68 (search-for-primes 10000000000) 69 (search-for-primes 100000000000) 70 71 72 (timed-prime-test 1009) 73 (timed-prime-test 1013) 74 (timed-prime-test 1019) 75 76 (timed-prime-test 10007) 77 (timed-prime-test 10009) 78 (timed-prime-test 10037) 79 80 (timed-prime-test 100003) 81 (timed-prime-test 100019) 82 (timed-prime-test 100043) 83 84 (timed-prime-test 1000003) 85 (timed-prime-test 1000033) 86 (timed-prime-test 1000037) 87 88 (timed-prime-test 10000019) 89 (timed-prime-test 10000079) 90 (timed-prime-test 10000103) 91 92 (timed-prime-test 100000007) 93 (timed-prime-test 100000037) 94 (timed-prime-test 100000039) 95 96 (timed-prime-test 1000000007) 97 (timed-prime-test 1000000009) 98 (timed-prime-test 1000000021) 99 100 (timed-prime-test 10000000019) 101 (timed-prime-test 10000000033) 102 (timed-prime-test 10000000061) 103 104 (timed-prime-test 100000000003) 105 (timed-prime-test 100000000019) 106 (timed-prime-test 100000000057) 107 108 (newline) 109 0)