Exercise 1.22: Most Lisp implementations include a primitive called runtime
(my implementation of scheme doesn’t.
I define a work around) 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 (runtime) (time->seconds (current-time)))
(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 \( \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?
> (timed-prime-test 68720001023)
68720001023 *** .4850001335144043
> (timed-prime-test 70368760954879)
70368760954879 *** 16.844000101089478
Since this exercise is a bit dated testing numbers on the order 106 for primality doesn’t give my system any noticeable workout. I test my ranges starting from 1010.
> (search-for-primes (expt 10 10) (- (expt 10 11) 1))
10000000019 *** .14100003242492676
10000000033 *** .1399998664855957
10000000061 *** .14000010490417483
According to the theoretical calculations the numbers on the order of 1011 should take \( 0.44 \approx 0.14 \cdot \sqrt{10} \) seconds.
Error: 17%
> (search-for-primes (expt 10 11) (- (expt 10 12) 1))
100000000003 *** .5310001373291016
100000000019 *** .5320000648498535
100000000057 *** .54699993133544923
\( 1.71 \approx 0.54 \cdot \sqrt{10} \) seconds.
> (search-for-primes (expt 10 12) (- (expt 10 13) 1))
1000000000039 *** 1.7660000324249268
1000000000061 *** 1.75
1000000000063 *** 1.76500010490417483
\( 5.57 \approx 1.76 \cdot \sqrt{10} \) seconds.
Error: 2%
> (search-for-primes (expt 10 13) (- (expt 10 14) 1))
10000000000037 *** 5.672000169754028
10000000000051 *** 5.672000169754028
10000000000099 *** 5.65599989891052253
It seems that \( \Theta(\sqrt n) \) is indeed a good predictor of the time it takes to check for primality of the algorithm.
(define (search-for-primes beg end)
(define (search beg end num-primes)
(cond ((= num-primes 3) num-primes)
((> beg end) num-primes)
((even? beg) (search (+ beg 1) end num-primes))
((prime? beg) (timed-prime-test beg)
(search (+ beg 2) end (+ 1 num-primes)))
(else
(search (+ beg 2) end num-primes))))
(search beg end 0))
(define (runtime) (time->seconds (current-time)))
(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)))
(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))