sicp-ex-1.22

  
 ;; ex 1.22 
  
 (define (square x) (* x x)) 
  
 (define (smallest-divisor n) 
   (find-divisor n 2)) 
  
 (define (find-divisor n test-divisor) 
   (cond ((> (square test-divisor) n) n) 
         ((divides? test-divisor n) test-divisor) 
         (else (find-divisor n (+ test-divisor 1))))) 
  
 (define (divides? a b) 
   (= (remainder b a) 0)) 
  
 (define (prime? n) 
   (= n (smallest-divisor n))) 
  
 (define (timed-prime-test n) 
   (start-prime-test n (runtime))) 
  
 (define (start-prime-test n start-time) 
   (if (prime? n) 
       (report-prime n (- (runtime) start-time)))) 
  
 (define (report-prime n elapsed-time) 
   (newline) 
   (display n) 
   (display " *** ") 
   (display elapsed-time)) 
  
 (define (search-for-primes first last) 
   (define (search-iter cur last) 
     (if (<= cur last) (timed-prime-test cur)) 
     (if (<= cur last) (search-iter (+ cur 2) last))) 
   (search-iter (if (even? first) (+ first 1) first) 
                (if (even? last) (- last 1) last))) 
  
 (search-for-primes 1000 1019)       ; 1e3 
 (search-for-primes 10000 10037)     ; 1e4 
 (search-for-primes 100000 100043)   ; 1e5 
 (search-for-primes 1000000 1000037) ; 1e6 
  
 ; As of 2008, computers have become too fast to appreciate the time 
 ; required to test the primality of such small numbers. 
 ; To get meaningful results, we should perform the test with numbers 
 ; greater by, say, a factor 1e6. 
 (newline) 
 (search-for-primes 1000000000 1000000021)       ; 1e9 
 (search-for-primes 10000000000 10000000061)     ; 1e10 
 (search-for-primes 100000000000 100000000057)   ; 1e11 
 (search-for-primes 1000000000000 1000000000063) ; 1e12 
  

The output produced by the above code is:

1009 *** 0.
1013 *** 0.
1019 *** 0.
10007 *** 0.
10009 *** 0.
10037 *** 0.
100003 *** 0.
100019 *** 0.
100043 *** 0.
1000003 *** 0.
1000033 *** 0.
1000037 *** 1.0000000000000002e-2

1000000007 *** .13
1000000009 *** .11999999999999997
1000000021 *** .10999999999999999
10000000019 *** .39
10000000033 *** .3799999999999999
10000000061 *** .3700000000000001
100000000003 *** 1.22
100000000019 *** 1.2300000000000004
100000000057 *** 1.2199999999999998
1000000000039 *** 3.829999999999999
1000000000061 *** 4.039999999999999
1000000000063 *** 3.9700000000000006

From our timing data, we can observe that, when increasing the tested number of a factor 10, the required time increases roughly of a factor 3. By noting that 3 ≅ √10, we can confirm both the growth prediction and the notion that programs run in a time proportional to the steps required for the computation.

Notes

1. This exercise requires a Scheme implementations which provides a runtime primitive, such as MIT/GNU Scheme
2. The arguments to (search-for-primes are an integer range. Therefore, to find the first three primes above a certain value, I needed to run the program with an arbitrary upper bound until three primes were found, and then put the third prime as the largest value.
3. In order to get a cleaner output, I modified timed-prime-test to make it print only prime numbers, not each tested number.
4. By using the begin construct, not introduced yet in the book, the inner procedure can be rewritten without repeating the if test:

   (define (search-iter cur last) 
     (if (<= cur last) 
       (begin (timed-prime-test cur) 
              (search-iter (+ cur 2) last)))) 

<< Previous exercise (1.21) | sicp-solutions | Next exercise (1.23) >>