]> git.rkrishnan.org Git - sicp.git/blob - src/sicp/ex1_22.clj
rewrite `quote->cons' using `match'.
[sicp.git] / 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.