SICP Exercise 1.23

sicp

Question

The smallest-divisor procedure shown at the start of this section does lots of needless testing: After it checks to see if the number is divisible by 2, there is no point in checking to see if it is divisible by any larger even numbers. This suggests that the values used for test-divisor should not be 2, 3, 4, 5, 6, …, but rather 2, 3, 5, 7, 9, …. To implement this change, define a procedure next that returns 3 if its input is equal to 2 and otherwise returns its input plus 2. Modify the smallest-divisor procedure to use (next test-divisor) instead of (+ test-divisor 1). With timed-prime-test incorporating this modified version of smallest-divisor, run the test for each of the 12 primes found in exercise 1.22. Since this modification halves the number of test steps, you should expect it to run about twice as fast. Is this expectation confirmed? If not, what is the observed ratio of the speeds of the two algorithms, and how do you explain the fact that it is different from 2?

Answer

; ----next definition
(define (next n)
  (cond ((= n 2) 3)
        (else (+ n 2))))

; ----prime definition----
(define (square x) (* x x))

(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 test-divisor)))))

(define (divides? a b)
  (= (remainder b a) 0))

(define (prime? n)
  (= n (smallest-divisor n)))

; ----exercise text modified----

(define (timed-prime-test n)
  (start-prime-test n (runtime)))

(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime n (- (runtime)
                         start-time))))

(define (report-prime number elapsed-time)
  (display number)
  (display " *** ")
  (display elapsed-time)
  (newline))

; ----solution----

(define (search-for-primes lower upper)
  (cond ((even? lower) (search-for-primes (+ lower 1) upper))
        ((> lower upper) (newline))
        (else (timed-prime-test lower)
              (search-for-primes (+ lower 2) upper))))

; ----run----

(search-for-primes 1000000 1000038)
(search-for-primes 1000000 1000038)
(search-for-primes 1000000 1000038)

(search-for-primes 10000000 10000105)
(search-for-primes 10000000 10000105)
(search-for-primes 10000000 10000105)

(search-for-primes 100000000 100000040)
(search-for-primes 100000000 100000040)
(search-for-primes 100000000 100000040)

(search-for-primes 1000000000 1000000030)
(search-for-primes 1000000000 1000000030)
(search-for-primes 1000000000 1000000030)

Results:

1000003 *** 7
1000033 *** 7
1000037 *** 8

1000003 *** 8
1000033 *** 7
1000037 *** 8

1000003 *** 8
1000033 *** 8
1000037 *** 8

10000019 *** 24
10000079 *** 24
10000103 *** 24

10000019 *** 24
10000079 *** 24
10000103 *** 24

10000019 *** 24
10000079 *** 24
10000103 *** 24

100000007 *** 76
100000037 *** 76
100000039 *** 76

100000007 *** 76
100000037 *** 76
100000039 *** 75

100000007 *** 76
100000037 *** 76
100000039 *** 75

1000000007 *** 247
1000000009 *** 267
1000000021 *** 238

1000000007 *** 257
1000000009 *** 275
1000000021 *** 238

1000000007 *** 246
1000000009 *** 238
1000000021 *** 238

Let us compare these to the speeds we got in exercise 1.22:

Lower Bound 1.22 Time 1.23 Time % faster
1,000,000 15.22 7.67 198.4
10,000,000 47.89 24.0 199.5
100,000,000 151.22 75.78 199.6
1,000,000,000 469.78 249.33 188.4

Seems relatively close to 200%, but somewhat lower. This is likely because of the additional if-statement that must be evaluated every time now.