## Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

# SICP exercise 1.22

## Problem

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). The following timed-prime-test procedure, when called with an integer n, prints n and checks to see if n is prime. If n is prime, the procedure prints three asterisks followed by the amount of time used in performing the test.

(define (timed-prime-test n)
(newline)
(display n)
(start-prime-test n (runtime)))
(define (start-prime-test n start-time)
(if (prime? n)
(report-prime (- (runtime) start-time))))
(define (report-prime elapsed-time)
(display " *** ")
(display elapsed-time))

Using this procedure, write a procedure search-for-primes that checks the primality of consecutive odd integers in a specified range. Use your procedure to find the three smallest primes larger than 1000; larger than 10,000; larger than 100,000; larger than 1,000,000. Note the time needed to test each prime. Since the testing algorithm has order of growth of $\theta(n)$, you should expect that testing for primes around 10,000 should take about $\sqrt{10}$ times as long as testing for primes around 1000. Do your timing data bear this out? How well do the data for 100,000 and 1,000,000 support the $\sqrt{n}$ prediction? Is your result compatible with the notion that programs on your machine run in time proportional to the number of steps required for the computation?

## Solution

None of the Scheme implementations I checked have a runtime primitive, but many have similar functionality. Mzscheme and Chicken provide current-milliseconds, which returns the number of milliseconds that have passed since a particular event (e.g., since starting the Scheme process). The code provided here uses current-milliseconds, but if your particular Scheme implementation doesn't provide it, consult your implementation's documentation for similar functionality (cpu-time, time, etc.) and adapt the code accordingly.

There are a few other differences between the code provided and the code in the text. The provided code only displays a number when it is prime, and displays the time required to find the prime (in milliseconds) in parentheses, to the right of the discovered prime. Also, start-prime-test returns #f if its argument is not prime, otherwise it returns #t (via report-prime).

(define runtime current-milliseconds)

(define (square x)
(* x x))

(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 (prime? n)
(= n (smallest-divisor n)))

(define (timed-prime-test n)
(start-prime-test n (runtime)))

(define (start-prime-test n start-time)
(if (prime? n)
(report-prime n (- (runtime) start-time))
#f))

(define (report-prime n elapsed-time)
(display n)
(display " (")
(display elapsed-time)
(display "ms)\n")
#t)

The procedure search-for-primes given below is different than the specification in the text. Rather than searching for primes in a given range, it finds the first n primes beginning with a number a, since that's what the exercise ultimately wants us to answer. search-for-primes uses a helper function, search-for-primes-helper, to accomplish its task. search-for-primes-helper returns 0. It assumes that the first argument is odd and checks only odd numbers for primality.

(define (search-for-primes a n)
(search-for-primes-helper (next-odd a) 0 n))

(define (search-for-primes-helper a found n)
(if (= found n)
0
(search-for-primes-helper (+ a 2)
(if (timed-prime-test a)
(+ found 1)
found)
n)))

(define (next-odd n)
(if (even? n)
(+ n 1)
n))

(define (even? n)
(= 0 (remainder n 2)))

Let's use this procedure to find the 3 smallest primes larger than 1000:

(search-for-primes 1000 3)

On a circa-2008 computer, chances are that the time required to compute each of these primes is smaller than the uncertainty in Scheme's timing routine, so this isn't a very useful test. We should find primes that take at least a few seconds to compute in order to get a reliable result. Start with 1000 and add an order of magnitude to each attempt until you get a satisfactory result, then repeat this process a few more times to verify that the procedure runs in time proportional to the number of steps required for the computation.

On a 2.4GHz Apple MacBook Pro running Chicken Scheme 3.1 on the Mac OS X operating system, I get the following results:

(search-for-primes 100000000000 3)

Output:

100000000003.0 (485ms)
100000000019.0 (486ms)
100000000057.0 (485ms)

(search-for-primes 1000000000000 3)

Output:

1000000000039.0 (1534ms)
1000000000061.0 (1537ms)
1000000000063.0 (1545ms)

(search-for-primes 10000000000000 3)

Output:

10000000000037.0 (4852ms)
10000000000051.0 (4870ms)
10000000000099.0 (4858ms)


Choosing one sample time measurement from each group of 3, the ratios between successive orders of magnitude (i.e., 10x) are approximately:

(/ 1534.0 485.0)

Output:

3.163

(/ 4852.0 1534.0)

Output:

3.163


And this value is approximately equal to the square root of 10:

(sqrt 10)

Output:

3.162


which demonstrates that the procedure does, in fact, demonstrate a performance order of growth of $\theta(\sqrt{n})$.