SICP exercise 1.22

From Drewiki

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.

" *** "

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 θ(n), you should expect that testing for primes around 10,000 should take about 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 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).

" (""ms)\n"

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.

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

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:

Output:

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

Output:

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

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:

Output:

3.163

Output:

3.163

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

Output:

3.162

which demonstrates that the procedure does, in fact, demonstrate a performance order of growth of .