Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

SICP exercise 1.23

From Drewiki
Jump to: navigation, search

Problem

The smallest-divisor procedure shown at the start of section 1.2.6 of the text 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?

Solution

Here is the original, inefficient version of smallest-divisor:

(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 (+ test-divisor 1)))))
 
(define (divides? a b)
  (= (remainder b a) 0))

Here is the modified version (square, smallest-divisor and divides? remain the same):

(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 (next n)
  (if (= n 2)
      3
      (+ n 2)))

And here is the procedure timed-prime-test as we designed it in our answer to exercise 1.22 (see that answer for details on the differences between this timed-prime-test and the one described in the text):

(define runtime current-milliseconds)
 
(define (prime? n)
  (= n (smallest-divisor n)))
 
(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))
      #f))
 
(define (report-prime n elapsed-time)
  (display n)
  (display " (")
  (display elapsed-time)
  (display "ms)\n")
  #t)
 
(define (search-for-primes a n)
  (search-for-primes-helper (next-odd a) 0 n))
 
(define (search-for-primes-helper a found n)
  (if (= found n)
      0
      (search-for-primes-helper (+ a 2)
                                (if (timed-prime-test a)
                                    (+ found 1)
                                    found)
                                n)))
 
(define (next-odd n)
  (if (even? n)
      (+ n 1)
      n))
 
(define (even? n)
  (= 0 (remainder n 2)))

Finally, here are the 3 prime searches we performed in our answer to exercise 1.22, this time using the improved version of smallest-divisor, along with their results on a 2.4GHz Apple MacBook Pro running Chicken Scheme 3.1 on OS X:

(search-for-primes 100000000000 3)

Output:

100000000003.0 (296ms)
100000000019.0 (296ms)
100000000057.0 (295ms)
(search-for-primes 1000000000000 3)

Output:

1000000000039.0 (941ms)
1000000000061.0 (942ms)
1000000000063.0 (939ms)
(search-for-primes 10000000000000 3)

Output:

10000000000037.0 (2980ms)
10000000000051.0 (2962ms)
10000000000099.0 (2958ms)


Compared to the timings given in the answer to exercise 1.22 on the same hardware, these results are about 1.6 times faster. One possible reason that the actual speedup is less than 2 is that while we're doing only half as many operations in the modified smallest-divisor procedure, each operation is slightly more expensive than the operation performed in the original smallest-divisor procedure. Procedure next compares its input to 2 before determining which expression to evaluate (usually incrementing the input value by 2), whereas the original smallest-divisor implementation simply increments the test divisor by 1.

Because the test divisor is only equal to 2 at the very beginning of the process, it isn't efficient to test it for each successive test divisor. If we can eliminate this test, we can change the calculation of the next test divisor to the combination (+test-divisor 2), a combination whose evaluation is as fast as the original (+ test-divisor 1) combination. Then this modified procedure will still perform only half as many operations as the original smallest-divisor procedure, and the cost of each operation is the same. In this case, it's reasonable to expect that the new procedure is twice as fast as the original.

Here's one way to implement it, along with timings on the MacBook Pro:

(define (smallest-divisor n)
  (if (divides? n 2)
      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)))))
(search-for-primes 100000000000 3)

Output:

100000000003.0 (242ms)
100000000019.0 (242ms)
100000000057.0 (242ms)
(search-for-primes 1000000000000 3)

Output:

1000000000039.0 (768ms)
1000000000061.0 (765ms)
1000000000063.0 (767ms)
(search-for-primes 10000000000000 3)

Output:

10000000000037.0 (2430ms)
10000000000051.0 (2415ms)
10000000000099.0 (2434ms)
(/ 4852.0 2430.0)

Output:

1.99670781893004


So these timings are indeed approximately twice as fast as the original procedure's.

Personal tools