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