sicp-ex-1.24

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

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.

[torinmr]]: I tested this using much larger numbers (50-200 digits) and obtained slightly different results:

45 digits => 0.04 seconds
90 digits => 0.1 seconds
135 digits => 0.18 seconds
180 digits => 0.27 seconds

If the function ran in logarithmic time, we would expect running time to be linear in the number of digits, but the growth is faster than that. This is probably because performing primitive operations on sufficiently large numbers is not constant time, but grows with the size of the number.