Exercise 1.24 asks us to once again modify the
timed-prime-testprocedure from exercise 1.22, this time using
fast-prime?(which uses the Fermat test), then test the improvement using the timing statistics we gathered before.
The Fermat test is a probabilistic method for testing primality, meaning that if a given number passes the Fermat test, the best we can say is that the number is very probably prime. It's based on Fermat's Little Theorem which states:
If n is a prime number and a is any positive integer less than n, then a raised to the nth power is congruent to a modulo n.So to test n for primality, we select a number, a, which is less than n, and raise it to the nth power. We then divide an by n to get the remainder. If n is prime, then the remainder will be equal to a, the base we selected.
Fermat's Little Theorem says that this property will always hold true if n is prime, but it doesn't say anything about when n isn't prime. If an mod n is not equal to a, then we know for certain that n is not prime. However, there are values of n and a that will pass the Fermat test even when n is not prime. If we test enough values of a for a given n, we can increase our confidence that n is prime. Unfortunately, there are extremely rare values of n called Carmichael numbers that pass the Fermat test for any value of a. There are variations on the Fermat test that cannot be fooled. We'll look at one of those variations, the Miller-Rabin test, in a later exercise.
The complete code listing below shows what modifications were necessary to use the Fermat test in the
fast-prime?procedure takes two arguments,
times. The first argument is the number to test, the second argument tells the procedure how many random values to test with. The more random values we use, the higher our confidence that
nis prime, so we should test a lot of values. I've (rather arbitrarily) chosen to test 100 random values.
One other change that you may notice is the inclusion of a library module in the first line of code. When testing the original code listing from the book, I found that Scheme's primitive
randomprocedure has a limit of 4,294,967,087. This won't do for the values we're testing, so I replaced it with the
random-integerprocedure, which doesn't have this limitation. I found out about this procedure and library through the Scheme Cookbook.
(require (lib "27.ss" "srfi"))
(define (timed-prime-test n)
(start-prime-test n (current-inexact-milliseconds)))
(define (start-prime-test n start-time)
(cond ((fast-prime? n 100)
(report-prime (- (current-inexact-milliseconds) start-time)))))
(define (report-prime elapsed-time)
(display " *** ")
(define (square x)
(* x x))
(define (even? n)
(= (remainder n 2) 0))
(define (expmod base exp m)
(cond ((= exp 0) 1)
(remainder (square (expmod base (/ exp 2) m))
(remainder (* base (expmod base (- exp 1) m))
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(try-it (+ 1 (random-integer (- n 1)))))
(define (fast-prime? n times)
(cond ((= times 0) true)
((fermat-test n) (fast-prime? n (- times 1)))
We need to run
timed-prime-testagain with the new modifications using the same set of inputs that we found in the previous exercises, then compare the results to see how much we improved the run time. The following table compares the original data we gathered in exercise 1.22, the improved algorithm we used in exercise 1.23 (improved time column), and the new results we got using the Fermat test (all three time columns are in milliseconds). The ratio column is the ratio of the improved values from exercise 1.23 to the fermat time column.
|prime||original time||improved time||fermat time||ratio|
The timing numbers from the Fermat test start out looking pretty poor compared to what we've seen previously. This has mostly to do with the completely arbitrary number of random values I chose to test each prime with. As we increase the size of the numbers we're testing, you can see that the time using the Fermat test barely increases at all. We can verify that the time increase is logarithmic by observing that as the numbers under test increase by a factor of 10, the ratio column increases by a factor of roughly three. This logarithmic characteristic is due to the fact that the
expmodprocedure used in
fermat-testhas a logarithmic time complexity.
For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.