## **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

## 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
θ(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?

## 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 θ(log*n*) 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 log*n*^{2} = 2log*n*.