SICP - Solution: Exercise 1.22

# SICP - Solution: Exercise 1.22

## Exercise 1.22 #

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 $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 (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 ${\mathrm\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 ${\mathrm\Theta(\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?

## Solution #

Since runtime is not part of DrRacket, you can use current-inexact-milliseconds. The code, including the search-for-primes function is:

#lang racket/base
(define (runtime) (current-inexact-milliseconds)) ; adapting to DrRacket

; --- Prime computation ---

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

; --- Timing ---

(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))
"nothing"))

(define (report-prime elapsed-time)
(display " *** ")
(display elapsed-time))

(define (search-for-primes start-range end-range)
(if (even? start-range)
(search-for-primes (+ 1 start-range) end-range)
(cond ((> start-range end-range)
(newline) (display "done"))
(else (timed-prime-test start-range)
(search-for-primes (+ 2 start-range) end-range)))))

(search-for-primes 10000000000 10000000090)


The funcion current-inexact-milliseconds provide data in the microseconds scale, but our current hardware are pretty fast and this is not precise enough. I extended the code for computing the averate time of 1000 runs.

### DrRacket has high variability #

The initial test where done with DrRacket:

log(prime) prime time (µs)
3 1,009 2.8010
3 1,013 2.4858
3 1,019 2.3898
4 10,007 7.9331
4 10,009 7.9948
4 10,037 7.8310
5 100,003 44.663
5 100,019 26.879
5 100,043 24.563
6 1,000,003 81.736
6 1,000,033 78.949
6 1,000,037 79.261
7 10,000,019 284.77
7 10,000,079 254.29
7 10,000,103 302.63
8 100,000,007 847.27
8 100,000,037 854.13
8 100,000,039 887.25
9 1,000,000,007 2612.4
9 1,000,000,009 2616.5
9 1,000,000,021 2625.0
10 10,000,000,019 8438.9
10 10,000,000,033 8096.1
10 10,000,000,061 8052.0

By averaging the run of the 3 first prime numbers and taking successive ratio, you get:

log(prime) average (µs) ratio
3 2,5589
4 7,9196 3,09493067
5 28,702 3,624145833
6 79,982 2,786651772
7 280,56 3,507844209
8 862,88 3,075520274
9 2618,0 3,03400981
10 8195,7 3,130518518

The ratio is pretty close to $\sqrt {10} = 3.162$, although this is only average of 3 run.

### Chicken Scheme, with compiled code, is less variable #

I wanted to compare to another implementation and managed to get the program compiled with Chicken Scheme. The results are somewhat more consistent:

log(prime) prime time (µs)
3 1,009 4.0
3 1,013 3.0
3 1,019 4.0
4 10,007 11.0
4 10,009 12.0
4 10,037 11.0
5 100,003 35.0
5 100,019 34.0
5 100,043 36.0
6 1,000,003 111.0
6 1,000,033 108.0
6 1,000,037 114.0
7 10,000,019 341.0
7 10,000,079 353.0
7 10,000,103 342.0
8 100,000,007 1105.0
8 100,000,037 1073.0
8 100,000,039 1080.0
9 1,000,000,007 3439.0
9 1,000,000,009 3471.0
9 1,000,000,021 3494.0
10 10,000,000,019 11129.0
10 10,000,000,033 11193.0
10 10,000,000,061 11224.0

The table can be summarized as above:

log(prime) average (µs) ratio
3 3,6
4 11 3,090
5 35 3,088
6 111 3,171
7 345 3,111
8 1086 3,144
9 3468 3,193
10 11182 3,224

The ratio here is also close to $\sqrt {10} = 3.162$, although this is only average of 3 run.

The variation in speed might be due to interaction with garbage collection. This article about micro-benchmarks could be a clue.