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

1 2 3 4 5 6 7 8 9 10 11 |
(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 , you should expect that testing for primes around 10,000 should take about 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 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 10^{6} for primality doesn’t give my system any noticeable workout. I test my ranges starting from 10^{10}.

> (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 10^{11} should take seconds.

Error: 17%

> (search-for-primes (expt 10 11) (- (expt 10 12) 1))

100000000003 *** .5310001373291016

100000000019 *** .5320000648498535

100000000057 *** .54699993133544923

seconds.

> (search-for-primes (expt 10 12) (- (expt 10 13) 1))

1000000000039 *** 1.7660000324249268

1000000000061 *** 1.75

1000000000063 *** 1.76500010490417483

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 is indeed a good predictor of the time it takes to check for primality of the algorithm.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
(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)) |