SICP Exercise 1.22
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
(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
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
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.