SICP-2nd-Edition-Exercise-1.22

From Boozled

Jump to: navigation, search

Contents

Exercise 1.22 From SICP

Details from SICP are here

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. 

  1. (define (timed-prime-test n)
  2.   (newline)
  3.   (display n)
  4.   (start-prime-test n (runtime)))
  5. (define (start-prime-test n start-time)
  6.   (if (prime? n)
  7.       (report-prime (- (runtime) start-time))))
  8. (define (report-prime elapsed-time)
  9.   (display " *** ")
  10.   (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\left(n\right), 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?


Attempt

I am using DrScheme and I had to switch to that PLT-Scheme implementation to get a runtime primitive. I was also unable to find a microsecond version. Measuring in milliseconds meant that I had to make my numbers a bit bigger to get some measurable output.

\sqrt{10} \approx 3.16224

Times shown are measured in milliseconds.

p1,p2,p3 t = avg\left(t_1 + t_2 + t_3\right) t*\sqrt{10}
100000007, 100000037, 100000039 9.33... 29.5
1000000007, 1000000009, 1000000021 30.66... 97
10000000019, 10000000033, 10000000061 154.66... 489.1
100000000003, 100000000019, 100000000057 641.33... 2028
1000000000039, 1000000000061, 1000000000063 2097 6632.4
10000000000037, 10000000000051, 10000000000099 6523.33... 20628.6
100000000000031, 100000000000067, 100000000000097 20997.33... 66399.4
1000000000000037, 1000000000000091, 1000000000000159 66797.66... ...

I think going any lower than 100000000 would not be accurate. I actually do not think the numbers above are particularly accurate either. The machine I am using is a Quad Core pentium so it's a reasonably fast machine as of 16 Dec 2008.

I originally wrote

The first set look close to what we would expect ie the slow down was \sqrt{10} \approx 3.286. It's also 32bit which may explain why when we go above 2^\left(32\right) we see a marked slow down of 5.04 as opposed to the expected 3.16. So for large numbers the amount of calls is not the only deciding factor for performance on this machine.

But I decided to run more tests to see what would happen

There appears to be some anomalies for numbers below 100000000003 in the table above. I was tempted to see if I could find if there was a particular region where things get slower or faster but after running the tests and seeing large differences factorizing numbers that are close together I decided not to bother. It might be interesting to pursue this further though to see if there is anything in it, i.e. is the compiler optimizing something in some way or is it to do with how numbers are being represented on this machine etc.

Scheme

  1. (define (square x) (* x x))
  2. (define (smallest-divisor n)
  3.   (find-divisor n 2))
  4. (define (find-divisor n test-divisor)
  5.   (cond ((> (square test-divisor) n) n)
  6.         ((divides? test-divisor n) test-divisor)
  7.         (else (find-divisor n (+ test-divisor 1)))))
  8. (define (divides? a b)
  9.   (= (remainder b a) 0))
  10.  
  11. (define (prime? n)
  12.   (= n (smallest-divisor n)))
  13.  
  14. (define (timed-prime-test n)
  15.   (newline)
  16.   (display n)
  17.   (start-prime-test n (current-process-milliseconds)))
  18. (define (start-prime-test n start-time)
  19.   (if (prime? n)
  20.       (report-prime (- (current-process-milliseconds) start-time))))
  21. (define (report-prime elapsed-time)
  22.   (display " *** ")
  23.   (display elapsed-time))
  24.  
  25. (define (even? n)
  26.   (= (remainder n 2) 0))
  27.  
  28. (define (search-for-primes s l) 
  29.    (cond 
  30.       ((even? s) 
  31.         (set! s (+ s 1) ))) 
  32.    (cond
  33.      ((even? l) 
  34.       (set! l (+ l 1))))    
  35.   (timed-prime-test s)
  36.   (cond 
  37.     ((< s l) (search-for-primes (+ s 2) l)))
  38.   )
  39.  
  40. (search-for-primes 1000000000 1000000030)

Parent Course

6.001_Structure_and_Interpretation_of_Computer_Programs

Further Reading

PLT Scheme Documentation for millisecond timers

Retrieved from "http://www.boozled.org/wiki/index.php/SICP-2nd-Edition-Exercise-1.22"
Personal tools