Dan's Thoughts Thinking somewhat carefully

Exercise 1.23 of SICP

Exercise 1.23: 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?

12 Primes from 1.22:

1. 10000000019 *** .14100003242492676
2. 10000000033 *** .1399998664855957
3. 10000000061 *** .14000010490417483
4. 100000000003 *** .5310001373291016
5. 100000000019 *** .5320000648498535
6. 100000000057 *** .54699993133544923
7. 1000000000039 *** 1.7660000324249268
8. 1000000000061 *** 1.75
9. 1000000000063 *** 1.76500010490417483
10. 10000000000037 *** 5.672000169754028
11. 10000000000051 *** 5.672000169754028
12. 10000000000099 *** 5.65599989891052253

Using time-prime-test with the new next function

1. 10000000019 *** .07799983024597168
2. 10000000033 *** .07800006866455078
3. 10000000061 *** .07800006866455078
4. 100000000003 *** .2969999313354492
5. 100000000019 *** .29600000381469727
6. 100000000057 *** .2969999313354492
7. 1000000000039 *** .9849998950958252
8. 1000000000061 *** .9840002059936523
9. 1000000000063 *** .9839999675750732
10. 10000000000037 *** 3.171999931335449
11. 10000000000051 *** 3.1570000648498535
12. 10000000000099 *** 3.171999931335449

Judging by the speedup it does look like there is about a 2 fold increase in speed of determining if a number is prime.

(define (runtime) (time->seconds (current-time)))
(define (square x) (* x x))
(define (smallest-divisor n)
  (find-divisor n 2))
(define (next n)
  (if (= n 2)
    3
    (+ 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)))
 
(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))
(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (runtime) start-time))))
(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))