SICP - Solution: Exercise 1.22

October 15, 2018

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:

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

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:

The table can be summarized as above:

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.