## **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

## 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.