Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

SICP exercise 1.24

From Drewiki
Jump to: navigation, search

Problem

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 θ(logn) 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?

Solution

Here is the Fermat test, as given in the text (with a couple of extra definitions to make the code portable to a few more Scheme implementations):

(define true #t)
 
(define false #f)
 
(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)))

Here is timed-prime-test from my answer to exercise 1.22, adapted to use fast-prime? See the notes in that answer for information about this code and executing it on various Scheme implementations.

(define runtime current-milliseconds)
 
(define (square x)
  (* x x))
 
(define (timed-prime-test n)
  (start-prime-test n (runtime)))
 
(define (start-prime-test n start-time)
  (if (fast-prime? n 1)
      (report-prime n (- (runtime) start-time))
      #f))
 
(define (report-prime n elapsed-time)
  (display n)
  (display " (")
  (display elapsed-time)
  (display "ms)\n")
  #t)
 
(define (search-for-primes a n)
  (search-for-primes-helper (next-odd a) 0 n))
 
(define (search-for-primes-helper a found n)
  (if (= found n)
      0
      (search-for-primes-helper (+ a 2)
                                (if (timed-prime-test a)
                                    (+ found 1)
                                    found)
                                n)))
 
(define (next-odd n)
  (if (even? n)
      (+ n 1)
      n))
 
(define (even? n)
  (= 0 (remainder n 2)))

Unfortunately, many Scheme implementations cannot compute the Fermat test for the primes I computed in my answer to exercise 1.22 because the computations performed by expmod are too large to fit in a machine register, and few Scheme implementations implement arbitrary-precision arithmetic. MIT Scheme is one implementation that does, but its runtime primitive is accurate only to about one one-hundredth of a second, and the Fermat test for primes is so effective that, running MIT Scheme on the 2.4GHz Apple MacBook Pro I used for the previous examples, the time required to determine the primality of the first prime after 1e50 is much less than the runtime primitive can measure accurately.

However, to answer (partially, at least) the question posed in the exercise, since the Fermat test has θ(logn) growth, we'd expect the time needed to test primes near 1e6 to be about twice as long as the time needed to test primes near 1e3, since logn2 = 2logn.

Personal tools