# Exercise 1.22 of SICP

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