src/sicp/ex1_22.clj

   1 (ns sicp.ex1_22
   2   (:use [sicp utils]
   3         [clojure.contrib trace test-is]))
   4
   5 ;; exercise 1.22
   6 (defn timed-prime-test [n]
   7   (prn)
   8   (print n)
   9   (start-prime-test n (System/nanoTime)))
  10
  11 (defn start-prime-test [n start-time]
  12   (if (prime? n)
  13     (report-prime (- (System/nanoTime) start-time))))
  14
  15 (defn report-prime [elapsed-time]
  16   (print " *** ")
  17   (print elapsed-time))
  18
  19 (defn search-for-primes [a b]
  20   (cond (>= a b) nil
  21         (even? a) (search-for-primes (+ 1 a) b)
  22         (timed-prime-test a) (search-for-primes (+ 2 a) b)
  23         :else (search-for-primes (+ 2 a) b)))
  24
  25 ;;; three smallest primes greater than 1000
  26 ;;; 1009, 1013, 1019
  27 (take 3 (filter #(prime? %) (iterate inc 1000)))
  28 ;=> (1009 1013 1019)
  29
  30 ;=> 0.9642028750000001
  31
  32 ;;; > 10,000: 10007, 10009, 10037
  33 (take 3 (filter #(prime? %) (iterate inc 10000)))
  34 ;=> (10007 10009 10037)
  35
  36 ;=> 1.5897884999999998
  37
  38 ;;; > 100,000: 100003, 100019, 100043
  39 (take 3 (filter #(prime? %) (iterate inc 100000)))
  40 ;=> (100003 100019 100043)
  41
  42 ;=> 1.8525091250000003
  43
  44 ;;; > 1,000,000: 1000003, 1000033, 1000037
  45 (take 3 (filter #(prime? %) (iterate inc 1000000)))
  46 ;=> (1000003 1000033 1000037)
  47
  48 ;=> 1.908832125
  49
  50 ;; time taken seem to increase as the range increases.
  51 ;; but they are totally random on the jvm, so I can't find
  52 ;; the exact relation.
  53
  54 (comment
  55 user> (microbench 10 (take 3 (filter #(prime? %) (iterate inc 1000))))
  56 Warming up!
  57 Benchmarking...
  58 (1009 1013 1019)
  59 (1009 1013 1019)
  60 (1009 1013 1019)
  61 (1009 1013 1019)
  62 (1009 1013 1019)
  63 (1009 1013 1019)
  64 (1009 1013 1019)
  65 (1009 1013 1019)
  66 (1009 1013 1019)
  67 (1009 1013 1019)
  68 Total runtime:  0.28404500000000005
  69 Highest time :  0.083949
  70 Lowest time  :  0.019416
  71 Average      :  0.022585000000000008
  72 (0.083949 0.019416 0.023257 0.020394 0.024165 0.024514 0.024374 0.020813 0.021721 0.021442)
  73 user> (microbench 10 (take 3 (filter #(prime? %) (iterate inc 10000))))
  74 Warming up!
  75 Benchmarking...
  76 (10007 10009 10037)
  77 (10007 10009 10037)
  78 (10007 10009 10037)
  79 (10007 10009 10037)
  80 (10007 10009 10037)
  81 (10007 10009 10037)
  82 (10007 10009 10037)
  83 (10007 10009 10037)
  84 (10007 10009 10037)
  85 (10007 10009 10037)
  86 Total runtime:  0.26462800000000003
  87 Highest time :  0.067118
  88 Lowest time  :  0.020533
  89 Average      :  0.022122125000000006
  90 (0.067118 0.022698 0.024095 0.023537 0.020533 0.020882 0.020603 0.021372 0.020603 0.023187)
  91 user> (microbench 10 (take 3 (filter #(prime? %) (iterate inc 100000))))
  92 Warming up!
  93 Benchmarking...
  94 (100003 100019 100043)
  95 (100003 100019 100043)
  96 (100003 100019 100043)
  97 (100003 100019 100043)
  98 (100003 100019 100043)
  99 (100003 100019 100043)
 100 (100003 100019 100043)
 101 (100003 100019 100043)
 102 (100003 100019 100043)
 103 (100003 100019 100043)
 104 Total runtime:  0.265118
 105 Highest time :  0.073263
 106 Lowest time  :  0.020254
 107 Average      :  0.021450125000000004
 108 (0.073263 0.023048 0.023467 0.021022 0.020394 0.020254 0.021302 0.020812 0.020743 0.020813)
 109 )
 110
 111 ;;; can't make out any sqrt(10) relation between the numbers. may be because
 112 ;;; jvm compilation is doing some behind the scene tricks.