1.22 Exercise 1.22

A lot of the exercises in this book are more interesting than they appear. I’m going to pick on this one for a little bit.

We are asked to write a procedure search-for-primes to find primes greater than certain numbers, and to investigate whether the running times needed to determine if these numbers are prime increases as the asymptotic complexity of the primality-testing algorithm we’re using suggests. This procedure is meant to check for primality "of consecutive odd integers in a specified range". With this range specified by a minimum and maximum value, the procedure could be written like this:

(define (search-for-primes start end)   (define (loop current end)     (if (> current end) (newline)         (begin           (timed-prime-test current)           (loop (+ current 2) end))))   (cond ((not (< start end)) (search-for-primes end start))         ((divides? 2 start) (loop (+ start 1) end))         (else (loop start end))))

Here, I chose to use an inclusive range, and chose to switch the range bounds if start was greater than end, rather than throwing an error.

This procedure is fully capable of completing the exercise, as we shall see later, but I’m not satisfied with it. Its use of timed-prime-test means that the results from the function are printed, rather than returned in a useful way. And trying to use this procedure in the way we are intended, to find the first three primes greater than 1000, 10000, etc is awkward, needing trial and error. This function also contains a subtle bug. I think we can do better.

First, a function for computing the first n primes greater than a certain number:

(define (next-primes start num)   (define (loop current-number current-list)     (cond ((= (length current-list) num) current-list)           ((prime? current-number)            (loop (+ current-number 2) (append current-list (list current-number))))           (else (loop (+ current-number 2) current-list))))   (cond ((< start 2) (error "can't start with a number less than 2"))         ((= start 2) (loop 3 '(2)))         ((divides? 2 start) (loop (+ start 1) '()))         (else (loop (+ start 2) '()))))

Like much of the code I write, this uses an inner recursive loop procedure that assumes a simpler set of inputs to reduce the inner conditions, with the outer procedure managing the interface to this procedure. Besides being expressed with tail recursion, I find the simplifying assumptions make the main algorithm easier to reason about – in this case, getting rid of the awkwardness where all even numbers are not prime except 2. This handles a case not properly handled by search-for-primes.

Now, we could pass these primes off to timed-prime-test. But this procedure deserves examination. It manages the calling of runtime itself, which works well enough if you want to test the run time of primality testing. But what if you didn’t? You would have to write a new procedure to test the run time yourself.

Instead, we can write a procedure to test the run time of any arbitrary procedure passed to it:

(define (time-proc proc . args)

(let ((start-time (runtime)))

(apply proc args)

(- (runtime) start-time)))

This procedure takes a procedure as the first argument and executes it with the rest of its given arguments passed as arguments to the given procedure, calling runtime before and after and returning the difference, much like how timed-prime-test works. This is similar to procedures that exist in many dialects of Lisp, including Racket.

We can use this to get the runtimes we’ve been asked for like this:

(map

(lambda (x)

(time-proc prime? x))

(next-primes 1000 3))

We can generalize this to work for 10000 and the rest, or we could not.

The exercise asks us to test execution times on testing for primality on the the first three primes greater than 1000, 10000, 100000, and 1000000. But this is not being careful enough. In my current environment (DrRacket), both of these means of testing show much higher execution times the first time any number is tested. And those first execution times seem to be quite variable. We have to decide whether the average first execution time is what we want, or if we want the average after the runtime reaches stability.

There is also a cost to time-proc – these runtimes are consistently higher than those from timed-prime-test. However, this cost is somewhere in the tens of microseconds. This is not even remotely large enough to outweigh the benefits of generalization.

TODO: Actually answer the question.