Solution to SICP Exercise 1.22

Solution to Exercise 1.22:

DrScheme does not have a built-in runtime procedure that I could find, so I modified the code for timed-prime-test to use SRFI 19, like so

(require (lib "19.ss" "srfi"))

(define (report-prime elapsed-time)
(display " *** ")
(display (time-second elapsed-time))
(display "s ")
(display (time-nanosecond elapsed-time))
(display "ns"))

I implemented seach-for-primes as follows:

(define (search-for-next-prime starting-at)
(if (prime? starting-at)
starting-at
(search-for-next-prime (+ starting-at 2))))

(define (search-for-primes find-n starting-at)
(if (= find-n 0)
null
(let ((next-prime (search-for-next-prime starting-at)))
(cons next-prime
(search-for-primes (- find-n 1) (+ next-prime 2))))))

I could then run some tests:

(define (time-prime-tests primes)
(map timed-prime-test primes))

(time-prime-tests (search-for-primes 3 1001))
(time-prime-tests (search-for-primes 3 10001))
(time-prime-tests (search-for-primes 3 100001))
(time-prime-tests (search-for-primes 3 1000001))


This gave the following output:


1009 *** 0s 0ns
1013 *** 0s 0ns
1019 *** 0s 0ns
(# # #)

1000003 *** 0s 0ns
1000033 *** 0s 0ns
1000037 *** 0s 0ns
(# # #)

As you can see, all of the tests for prime took no time at all. This is obviously wrong.

I have a feeling that all these processes complete in less time than a single tick of the process clock (which, on Windows, appears to have a resolution in milliseconds).

Let’s magnify the results by calling prime? in timed-prime-test 1000 times instead of just once. Here’s the modified definition:

(define (timed-prime-test n)
(newline)
(display n)
(start-prime-test 1000 n (current-time time-process)))
(define (start-prime-test i n start-time)
(if (prime? n)
(if (= i 0)
(report-prime
(time-difference
(current-time time-process)
start-time))
(start-prime-test (- i 1) n start-time))))

Now I get the following output:


1009 *** 0s 460000ns
1013 *** 0s 470000ns
1019 *** 0s 320000ns
(# # #)

1000003 *** 0s 7500000ns
1000033 *** 0s 1870000ns
1000037 *** 0s 2340000ns
(# # #)

Alright! We have some numbers. Unfortunately, when I run the tests again, I get totally different numbers. Grr! I’m going to consider these numbers representative of many runs, but they probably aren’t. Let’s start with some analysis.

Let’s start by averaging the times for each group. We can multiply this by √10 to obtain an expected time for the following group, which we can compare against the measured time.

With a difference of over 70% on the final group, this data clearly does not support the √n hypothesis, but it doesn’t disprove it, either. For a definitive answer, we need a larger sample group. We need data for more values of n and for several runs. I’m not going to do that here because this post is already too long, and I’m sure you have better things to do.