Exercise 1.22 introduces a new primitive called
Most Lisp implementations include a primitive called runtime that returns an integer that specifies the amount of time the system has been running (measured, for example, in microseconds).
Unfortunately, this turns out not to be the case for Scheme. After a bit of research, I found what I think to be a suitable replacement: current-inexact-milliseconds. It's not as precise as I'd like, but there are a couple of workarounds to this problem that I'll explain shortly.
The exercise goes on to to introduce the
timed-prime-testprocedure, which prints its input
nand tests to see if
nis prime. If
nis prime, the procedure prints three asterisks followed by the amount of time used in performing the test. Here is the modified version that I'll be using, including all of the required support procedures from the book:
(define (timed-prime-test n)
(start-prime-test n (current-inexact-milliseconds)))
(define (start-prime-test n start-time)
(cond ((prime? n)
(report-prime (- (current-inexact-milliseconds) start-time)))))
(define (report-prime elapsed-time)
(display " *** ")
(define (smallest-divisor n)
(find-divisor n 2))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
(= (remainder b a) 0))
(define (square x)
(* x x))
(define (prime? n)
(= n (smallest-divisor n)))
Our task (finally) is to use
timed-prime-testto write a procedure named
search-for-primesthat checks the primality of consecutive odd integers in a specified range. We're instructed to use this procedure to find the three smallest primes larger than 1000, 10000, 100000, and 1000000. Since the
prime?procedure has an order of growth of O(√n), we should expect a run time increase of a factor of √10 at each step. We'll use the output from
timed-prime-testto check this assumption.
The following procedure checks the primality of consecutive odd integers in the range from start to end.
(define (search-for-primes start end)
(if (even? start)
(search-for-primes (+ start 1) end)
(cond ((< start end) (timed-prime-test start)
(search-for-primes (+ start 2) end)))))
(define (even? n)
(= (remainder n 2) 0))
The procedure initially checks to see if the
startinput argument is even. If it is, the procedure simply starts over with the next (odd) integer. Next the procedure checks to see if
startis less than
end. If so, it performs a
start, then recursively calls itself with the next odd integer as a starting value. This process will continue until
With a little bit of trial and error we can find
endvalues that surround the first three primes larger than our target values. Here's a sample run starting at 1000.
> (search-for-primes 1000 1020)
1009 *** 1.0
1013 *** 1.0
1019 *** 0.0
We can tell from this output that our timer's resolution isn't fine enough to give us meaningful results on modern desktop hardware (even if it is cheap). I see two things we can do to work around this problem. First, we could ignore the suggested inputs from the exercise and just keep increasing the input values until we get meaningful measurements. Second, we could run
prime?in a loop and measure how long it takes to test a value 1000 (or maybe more) times. The code is ready as-is for the first option, so that's what I'm going to try. (If anyone implements the second option, please leave a comment so we can compare results.)
The first consistent results I got were by using a
startvalue of 1010. It took an average of 154 milliseconds to test each of the first three primes after that value. The following table shows details of the time required to test the primality of numbers spread over several orders of magnitude.
The last column shows the ratio of the average time for each row to the average time for the preceding row. These ratios stay very close to √10, which is approximately 3.162. These results do seem to verify that programs on my machine run in time proportional to the number of steps required for the computation.
For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.