Exercise 1.24 of SICP

2009-06-20

sicp

Exercise 1.24: Modify the timed-prime-test procedure of exercise 1.22 to use fast-prime? (the Fermat method), and test each of the 12 primes you found in that exercise. Since the Fermat test has (log n) growth, how would you expect the time to test primes near 1,000,000 to compare with the time needed to test primes near 1000? Do your data bear this out? Can you explain any discrepancy you find?

I arbitrarily chose to run the fast-prime? test 100 times. As in 1.22 I ran it only larger ranges than the book suggested.

(define (random n) (random-integer n))
(define (runtime) (time->seconds (current-time)))
(define (square x) (* x x))
(define (square-mod n m) (remainder (* n n) m))
(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) #t)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else #f)))

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))
(define (start-prime-test n start-time)
  (if (fast-prime? n 100)
      (report-prime (- (runtime) start-time))))
(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))
(define (search-for-primes beg end)
  (define (search beg end num-primes)
    (cond ((= num-primes 3) num-primes)
          ((> beg end) num-primes)
          ((even? beg) (search (+ beg 1) end num-primes))
          ((fast-prime? beg 100) (timed-prime-test beg)
                        (search (+ beg 2) end (+ 1 num-primes)))
          (else
            (search (+ beg 2) end num-primes))))
  (search beg end 0))

> (search-for-primes (expt 10 10) (- (expt 10 11) 1)) 
10000000019 *** .016000032424926758
10000000033 *** .016000032424926758
10000000061 *** .0160000324249267583

> (search-for-primes (expt 10 11) (- (expt 10 12) 1))

100000000003 *** .016000032424926758
100000000019 *** .016000032424926758
100000000057 *** .0150001049041748053

> (search-for-primes (expt 10 12) (- (expt 10 13) 1)) 
1000000000039 *** .016000032424926758
1000000000061 *** 0.
1000000000063 *** .0159997940063476563

> (search-for-primes (expt 10 13) (- (expt 10 14) 1))
10000000000037 *** .015999794006347656
10000000000051 *** .016000032424926758
10000000000099 *** .0149998664855957033

The test is too fast to give meaningful times to compare against. I would expect numbers of order 106 to take 2 times longer to compute than 103. The reasoning follows the property of logarithms. log( 106 ) = 6 and log( 103 ) = 3.

In my case: log( 1010 ) = .016 I would predict: log( 1020 ) = .032

> (search-for-primes (expt 10 20) (- (expt 10 21) 1))
100000000000000000039 *** .03099989891052246
100000000000000000129 *** .03099989891052246
100000000000000000151 *** .030999898910522463

Contents