SICP Exercise 1.23: Halving the Search Space

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?

The definition of next is nice and straightforward:

(define (next n)
  (if (= n 2)
      3
      (+ n 2)))

The exercise then says to "Modify the smallest-divisor procedure to use (next test-divisor) instead of (+ test-divisor 1)." The smallest-divisor procedure doesn't actually call (+ test-divisor 1); it simply calls through to find-divisor which does the call. So we modify the find-divisor procedure as follows:

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

I reused my implementation of search-for-primes from exercise 1.22 to test the 12 primes we found there:

> (search-for-primes 1000 3)
1001
1003
1005
1007
1009 *** 561.0
1011
1013 *** 562.0
1015
1017
1019 *** 546.0...done
> (search-for-primes 10000 3)
10001
10003
10005
10007 *** 1669.0
10009 *** 1654.0
10011
10013
10015
10017
10019
10021
10023
10025
10027
10029
10031
10033
10035
10037 *** 1669.0...done
> (search-for-primes 100000 3)
100001
100003 *** 5148.0
100005
100007
100009
100011
100013
100015
100017
100019 *** 5242.0
100021
100023
100025
100027
100029
100031
100033
100035
100037
100039
100041
100043 *** 5226.0...done
> (search-for-primes 1000000 3)
1000001
1000003 *** 16474.0
1000005
1000007
1000009
1000011
1000013
1000015
1000017
1000019
1000021
1000023
1000025
1000027
1000029
1000031
1000033 *** 16458.0
1000035
1000037 *** 16536.0...done

Right, let's calculate the averages, compare them with the results from exercise 1.22 and find the ratios:

Start	1st Prime Time (ms)	2nd Prime Time (ms)	3rd Prime Time (ms)	Average Time (ms)	Ex.1.22 Avg Time (ms)	Ratio
1,000	561.0	562.0	546.0	556.3	780.0	1.40
10,000	1669.0	1654.0	1669.0	1664.0	2532.3	1.52
100,000	5148.0	5242.0	5226.0	5205.3	7987.7	1.53
1,000,000	16474.0	16458.0	16536.0	16489.3	25558.0	1.55

Well, it's not quite the expected two-times improvement in speed... But it does appear to be fairly a constant improvements at around 1.5-times faster. So why's it not the two-times improvement? Let's have a closer look at the change we made: we replaced (+ test-divisor 1) with (next test-divisor). There are a couple of things of note here that could account for the difference:

1. We've replaced a built-in primitive operator (+) with a user-defined one (next). Built-in operators, particularly primitive ones such as basic numerical operations, can have various optimizations applied to them by the interpreter's authors and so may run faster than user-defined procedures. For example, the interpreter may be able to avoid the overhead of storing another stack frame on the call stack.
2. To evaluate the procedure next, the interpreter must evaluate the predicate of the if operator in order to determine whether to evaluate the consequent or the alternative as the result of the procedure. This adds additional overhead to determining the value of test-divisor to pass in the recursive call.