計算機プログラムの構造と解釈 第二版 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)