Solution to SICP Exercise 1.23

Structure and Interpretation of Computer Programs

Solution to Exercise 1.23:

Here is the definition of a next procedure.

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

To use it, we need to modify find-divisor like so:

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

When I rerun the code from exercise 1.22, I get the following output:


1009 *** 0s 310000ns
1013 *** 0s 320000ns
1019 *** 0s 150000ns
(# # #)

10007 *** 0s 780000ns
10009 *** 0s 780000ns
10037 *** 0s 940000ns
(# # #)

100003 *** 0s 2500000ns
100019 *** 0s 7500000ns
100043 *** 0s 2500000ns
(# # #)

1000003 *** 0s 2190000ns
1000033 *** 0s 7810000ns
1000037 *** 0s 2190000ns
(# # #)

Compared to the results of exercise 1.22:

Number Ex 1.22 Time Ex 1.23 Time Ratio
1009 460000 310000 1.48
1013 470000 320000 1.47
1019 320000 150000 2.13
10007 1250000 780000 1.6
10009 1410000 780000 1.81
10037 1090000 940000 1.16
100003 5940000 2500000 2.38
100019 3910000 7500000 0.52
100043 4060000 2500000 1.62
1000003 7500000 2190000 3.42
1000033 1870000 7810000 0.24
1000037 2340000 2190000 1.07

If I throw away the top two and bottom two ratios, the average ratio is 1.54. This is close to but less than the expected speed up of 2. If the numbers are at all reliable — and I have my doubts — the extra 0.46 can be attributed to a combination of the procedure call to next (which could take longer than the call to + because it is user-defined versus built-in) and the additional if, with its test for equality to 2.

Advertisements