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 function current-inexact-milliseconds provides data in the microseconds scale, but our current hardware is pretty fast and this is not precise enough. I extended the code for computing the average time of 1000 runs.

DrRacket has high variability #

The initial test was done with DrRacket, using some variation of the code you can find here:

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

The ratio is pretty close to $\sqrt {10} = 3.162$, although this is only an 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 based on the code from here:

The table can be summarized as above:

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

Conclusion #

The timing data seems to confirm that, for the range of value tested, the speed increase by $\sqrt {10}$ when testing with a number that has one more digit.

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