Exercise 1.23 asks us to add a modification to the
smallest-divisorprocedure, then test the improvement using the timing statistics we gathered in exercise 1.22.
We start with the observation that
smallest-divisorinefficiently 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
nextthat 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-divisorprocedure 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-testwith 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|
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
ifmust 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.
For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.