SICP Exercise 1.22

2021-09-02

Question

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(\sqrt{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 \(\Theta(\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?

Answer

Here is the full answer code. Note that I modified the code from the exercise text somewhat to achieve a cleaner output. I have also included the code for the prime calculation.

Since SICP was written in 1985, computers have become much more powerful. Therefore, in order to have representative data, I chose to start the calculation at 1,000,000 rather than 1,000.

; ----prime definition----
(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)))

; ----exercise text modified----

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

(define (report-prime number elapsed-time)
  (display number)
  (display " *** ")
  (display elapsed-time)
  (newline))

; ----solution----

(define (search-for-primes lower upper)
  (cond ((even? lower) (search-for-primes (+ lower 1) upper))
        ((> lower upper) (newline))
        (else (timed-prime-test lower)
              (search-for-primes (+ lower 2) upper))))

; ----run----
(search-for-primes 1000000 1000038)
(search-for-primes 1000000 1000038)
(search-for-primes 1000000 1000038)

(search-for-primes 10000000 10000105)
(search-for-primes 10000000 10000105)
(search-for-primes 10000000 10000105)

(search-for-primes 100000000 100000040)
(search-for-primes 100000000 100000040)
(search-for-primes 100000000 100000040)

(search-for-primes 1000000000 1000000030)
(search-for-primes 1000000000 1000000030)
(search-for-primes 1000000000 1000000030)

Each calculation is run three times, so we can take an average of the time and get a more accurate result.

1000003 *** 15
1000033 *** 15
1000037 *** 16

1000003 *** 15
1000033 *** 15
1000037 *** 14

1000003 *** 16
1000033 *** 15
1000037 *** 16

10000019 *** 48
10000079 *** 48
10000103 *** 48

10000019 *** 48
10000079 *** 48
10000103 *** 47

10000019 *** 48
10000079 *** 48
10000103 *** 48

100000007 *** 149
100000037 *** 151
100000039 *** 151

100000007 *** 150
100000037 *** 150
100000039 *** 150

100000007 *** 152
100000037 *** 151
100000039 *** 157

1000000007 *** 469
1000000009 *** 469
1000000021 *** 472

1000000007 *** 469
1000000009 *** 469
1000000021 *** 468

1000000007 *** 474
1000000009 *** 469
1000000021 *** 469

The base value will be the average calculation time of a prime number close to 1,000,000. In this case, the average value here is \(\approx 15.22\). We would expect this to increase by approximately \(\sqrt{10}\) for each subsequent iteration.

Let us compare the actual results to the expected results:

Lower Bound	Expected	Actual
10,000,000	48.14	47.89
100,000,000	152.22	151.22
1,000,000,000	481.36	469.78

As we can see, the values are all relatively close to one another. It seems reasonable to assume, then, that there is in fact a relationship of number of steps to time.