# 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 (timed-prime-test n) (newline) (display n) (start-prime-test n (current-time time-process))) (define (start-prime-test n start-time) (if (prime? n) (report-prime (time-difference (current-time time-process) start-time)))) ```

```(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 (# # #)```

``` 10007 *** 0s 0ns 10009 *** 0s 0ns 10037 *** 0s 0ns (# # #) 100003 *** 0s 0ns 100019 *** 0s 0ns 100043 *** 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 (# # #)```

``` 10007 *** 0s 1250000ns 10009 *** 0s 1410000ns 10037 *** 0s 1090000ns (# # #) 100003 *** 0s 5940000ns 100019 *** 0s 3910000ns 100043 *** 0s 4060000ns (# # #) ```

```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.

Group Average Time Expected time (based on lower group) Difference
~1000 416667
~10000 1250000 1317616 -5%
~100000 4636667 3952847 17%
~1000000 3903333 14662427 -73%

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.