## **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 <math> \theta(n)</math>, you should expect that testing for primes
around 10,000 should take about <math>\sqrt{10}</math> 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 <math>\sqrt{n}</math> 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 <math>\theta(\sqrt{n})</math>.