sicp-ex-1.24

This exercise is based on sicp-ex-1.22. Please read the notes therein.

  
 ;; ex 1.24 
  
 (define (square x) (* x x)) 
  
 (define (expmod base exp m) 
   (cond ((= exp 0) 1) 
         ((even? exp) 
          (remainder (square (expmod base (/ exp 2) m)) 
                     m)) 
         (else 
          (remainder (* base (expmod base (- exp 1) m)) 
                     m))))         
  
 (define (fermat-test n) 
   (define (try-it a) 
     (= (expmod a n n) a)) 
   (try-it (+ 1 (random (- n 1))))) 
  
 (define (fast-prime? n times) 
   (cond ((= times 0) true) 
         ((fermat-test n) (fast-prime? n (- times 1))) 
         (else false))) 
  
 (define (prime? n) 
   ; Perform the test how many times? 
   ; Use 100 as an arbitrary value. 
   (fast-prime? n 100)) 
  
 (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)) 
  
 (timed-prime-test 1009) 
 (timed-prime-test 1013) 
 (timed-prime-test 1019) 
 (timed-prime-test 10007) 
 (timed-prime-test 10009) 
 (timed-prime-test 10037) 
 (timed-prime-test 100003) 
 (timed-prime-test 100019) 
 (timed-prime-test 100043) 
 (timed-prime-test 1000003) 
 (timed-prime-test 1000033) 
 (timed-prime-test 1000037) 
  
 ; See comments in exercise 1.22 
 (newline) 
 (timed-prime-test 1000000007) 
 (timed-prime-test 1000000009) 
 (timed-prime-test 1000000021) 
 (timed-prime-test 10000000019) 
 (timed-prime-test 10000000033) 
 (timed-prime-test 10000000061) 
 (timed-prime-test 100000000003) 
 (timed-prime-test 100000000019) 
 (timed-prime-test 100000000057) 
 (timed-prime-test 1000000000039) 
 (timed-prime-test 1000000000061) 
 (timed-prime-test 1000000000063) 
  

The output produced by the above code is:

1009 *** .01
1013 *** 0.
1019 *** 9.999999999999998e-3
10007 *** 0.
10009 *** 1.0000000000000002e-2
10037 *** 1.0000000000000002e-2
100003 *** 9.999999999999995e-3
100019 *** 1.0000000000000009e-2
100043 *** 9.999999999999995e-3
1000003 *** 9.999999999999995e-3
1000033 *** 1.0000000000000009e-2
1000037 *** .01999999999999999

1000000007 *** 1.0000000000000009e-2
1000000009 *** .01999999999999999
1000000021 *** 2.0000000000000018e-2
10000000019 *** .01999999999999999
10000000033 *** 1.0000000000000009e-2
10000000061 *** .01999999999999999
100000000003 *** .03
100000000019 *** 2.0000000000000018e-2
100000000057 *** 1.9999999999999962e-2
1000000000039 *** 3.0000000000000027e-2
1000000000061 *** 2.0000000000000018e-2
1000000000063 *** .02999999999999997

From the collected timing data, we can observe that testing a number with twice as many digits (1e12 vs. 1e6) is roughly twice as slow. This supports the theory of logarithmic growth.

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