Chapter 1, Building Abstractions with Procedures
Section - Procedures and the Processes They Generate
Exercise 1.22
I have changed the code slightly for printing numbers in easier way. The complete code looks as follows:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#lang sicp
(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)))
(define (square x) (* x x))
(define (report-prime n elapsed-time)
(newline)
(display n)
(display " *** ")
(display elapsed-time)
1
)
(define (search-primes start count)
(define (search-primes-itr mm nn)
(if (> nn 0)
(if (> (elapsed-prime-time mm (runtime)) 0)
(search-primes-itr (+ mm 2) (dec nn))
(if (even? mm)
(search-primes-itr (+ mm 1) nn)
(search-primes-itr (+ mm 2) nn)
)
)
(newline)
)
)
(search-primes-itr start count)
)
(define (elapsed-prime-time n st)
(if (prime? n)
(report-prime n (- (runtime) st))
0
)
)
Output on multiple invocations is as follows:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
> (search-primes 100 5)
101 *** 2
103 *** 3
107 *** 2
; avg: 2.33
> (search-primes 1000 3)
1009 *** 4
1013 *** 4
1019 *** 4
; avg: 4
; prev_avg * sqrt 10 = 7.36
> (search-primes 10000 3)
10007 *** 12
10009 *** 26
10037 *** 13
; avg: 17
; prev_avg * sqrt 10 = 12.64
> (search-primes 100000 3)
100003 *** 41
100019 *** 40
100043 *** 40
; avg: 40.03
; prev_avg * sqrt 10 = 53.72
> (search-primes 1000000 3)
1000003 *** 157
1000033 *** 126
1000037 *** 127
; avg: 136.66
; prev_avg * sqrt 10 = 126.49
> (search-primes 10000000 3)
10000019 *** 349
10000079 *** 436
10000103 *** 398
; avg: 394.33
; prev_avg * sqrt 10 = 431.84
> (search-primes 100000000 3)
100000007 *** 1248
100000037 *** 1136
100000039 *** 1288
; avg: 1224
; prev_avg * sqrt 10 = 1246.08
> (search-primes 1000000000 3)
1000000007 *** 3937
1000000009 *** 3860
1000000021 *** 3866
; avg: 3887.66
; prev_avg * sqrt 10 = 3867.84
> (search-primes 10000000000 3)
10000000019 *** 12264
10000000033 *** 12119
10000000061 *** 12120
; avg: 12167.66
; prev_avg * sqrt 10 = 12285.00
> (search-primes 100000000000 3)
100000000003 *** 39317
100000000019 *** 40547
100000000057 *** 39256
; avg: 39706.66
; prev_avg * sqrt 10 = 38449.80
> (search-primes 1000000000000 3)
1000000000039 *** 122881
1000000000061 *** 123508
1000000000063 *** 123451
; avg: 123280
; prev_avg * sqrt 10 = 125473.04
> (search-primes 10000000000000 3)
10000000000037 *** 388727
10000000000051 *** 388108
10000000000099 *** 394797
; avg: 390544
; prev_avg * sqrt 10 = 389564.8
> (search-primes 100000000000000 3)
100000000000031 *** 1238697
100000000000067 *** 1240527
100000000000097 *** 1231886
; avg: 1237036.66
; prev_avg * sqrt 10 = 1234119.04
> (search-primes 1000000000000000 3)
1000000000000037 *** 4022782
1000000000000091 *** 4036198
1000000000000159 *** 4013268
; avg: 4024082.66
; prev_avg * sqrt 10 = 3909035.84
; lets try last example with five more zeroes than the previous example.
; clearly this time should come about prev_avg * sqrt 100000
> (search-primes 100000000000000000000 3)
100000000000000000039 *** 5964178266
; as it took too much time, i will not go for further primes. lets consider this only as avg: 5964178266
; prev_avg * sqrt 100000 = 1236145670.96 (note here we are using 100000 and not 10 like in last cases)
; clearly here actual time taken is much larger than the expected value.
; as it takes too much time
; this takes
As we can see above numbers are almost inline with our calculations. There can be multiple reasons for these small variations:
- Operations like multiplication/addition on very large numbers may take more time compared to small numbers.
- For small numbers time taken in loading and initialization of programs may take more time as compared to actual process.
- Garbage collector may also take some time and halt the program in between depending on the interpreter.
- For humongous numbers, eg i tried with 21 trailing zeros, and program is taking huge time and for this case the difference between expected and actual time taken is significant(almost 5 times in the eg). The reason can be that numbers that can need more than 64 bits for storage will take much more time on system of 64bits.