SICP Exercise 1.23: Improved Prime Test

From SICP section 1.2.6 Example: Testing for Primality

Exercise 1.23 asks us to add a modification to the smallest-divisor procedure, then test the improvement using the timing statistics we gathered in exercise 1.22.

We start with the observation that smallest-divisor inefficiently finds the divisor of n by checking every candidate value from 2 to √n. The number of candidates can easily be cut nearly in half by simply not checking even numbers greater than 2.

Our first task is to define a procedure next that returns 3 if its input is equal to 2 and otherwise returns its input plus 2. The code is as straightforward as the description:

(define (next x)
  (if (= x 2) 3 (+ x 2)))

Our next task is to modify the find-divisor procedure to use (next test-divisor) instead of (+ test-divisor 1). This is a straight substitution, and no other changes to the code from exercise 1.22 are necessary.

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (next test-divisor)))))

Finally, we need to run timed-prime-test with these modifications using the same set of inputs that we found in the previous exercise, then compare the results to see if we really did cut the run time in half. The following table compares the original data to new timing data gathered using the improved algorithm. (Values in the new time column are averaged from three runs of the procedure.)

prime	old time (ms)	new time (ms)	ratio
10000000019	141	103	1.37
10000000033	172	101	1.70
10000000061	154	112	1.38
100000000003	516	310	1.67
100000000019	493	295	1.67
100000000057	527	305	1.73
1000000000039	1627	861	1.89
1000000000061	1559	884	1.76
1000000000063	1549	873	1.77
10000000000037	5014	2671	1.88
10000000000051	4932	2668	1.85
10000000000099	4855	2697	1.80
100000000000031	15745	8531	1.85
100000000000067	16022	8264	1.94
100000000000097	15861	8530	1.86
1000000000000037	48950	26346	1.86
1000000000000091	48836	26210	1.86
1000000000000159	49008	26256	1.87

Analysis

We're seeing a clear improvement in the new procedure, but it's not quite as fast as we expected. The first thing that needs to be explained in this data is the fact that the first three values shows very little performance gain, the next three a little more, then fairly consistent results for the remaining data. I think this can be explained by other processes running on the computer. Measuring shorter runs of the procedure (those in the 100-500 millisecond range) is going to be much more sensitive to measurement error due to being interrupted by background processes. These errors will be a less significant proportion of the total run time for longer runs of the procedure.

We're also seeing that the procedure is only running approximately 1.85 times as fast, instead of the expected factor of 2. This may be explained by the fact that we replaced a primitive operation, (+ test-divisor 1), by a user-defined operation, (next test-divisor). Each time that user-defined operation is called, an extra if must be evaluated (to check if the input is 2). Other than this small discrepancy, I think the improvement is quite good for such a small change to the code.


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.