Chapter 1, Building Abstractions with Procedures
Section - Procedures and the Processes They Generate
Exercise 1.23
Here I have written code in two ways:
- one is as asked in problem, by writing a function
next-divisor
. - Without writing any extra function, just adding 2 in every iteration.
First approach:
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
#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 (next-divisor test-divisor)))
)
)
(define (divides? a b)
(= (remainder b a) 0)
)
(define (next-divisor d)
(if (= d 2)
3
(+ d 2)
)
)
(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
)
)
Second approach:
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
#lang sicp
(define (smallest-divisor n)
(if (even? n)
2
(find-divisor n 3)
)
)
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (+ test-divisor 2)))
)
)
(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
)
)
Now I will put all the timings from all three approaches in one place:
Numbers | Orignal approach with no skipping | Skipping even numbers by calling next-divisor | Skipping even numbers directly |
---|---|---|---|
1009 | 4 | 3 | 2 |
1013 | 4 | 3 | 2 |
1019 | 4 | 3 | 2 |
10007 | 12 | 9 | 7 |
10009 | 26 | 8 | 7 |
10037 | 13 | 7 | 5 |
100003 | 41 | 26 | 20 |
100019 | 40 | 27 | 19 |
100043 | 40 | 26 | 19 |
1000003 | 157 | 83 | 62 |
1000033 | 126 | 82 | 63 |
1000037 | 127 | 83 | 63 |
10000000000037 | 388727 | 279466 | 194440 |
10000000000051 | 388108 | 279058 | 192753 |
10000000000099 | 394797 | 304850 | 207065 |
100000000000031 | 1238697 | 8375991 | 6426951 |
100000000000067 | 1240527 | 8306311 | 6561041 |
As we can see clearly that ‘next-divisor’ function calls make significant extra cost and it increases as number increases. Without using this function and skipping the even numbers generates prime numbers in almost half of the orignial time as expected.