Solution to Exercise 1.23:
Here is the defintion 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 <strong>(next test-divisor)</strong>))))When I rerun the code from exercise 1.22, I get the following output:
1009 *** 0s 310000ns
1013 *** 0s 320000ns
1019 *** 0s 150000ns
(#<void> #<void> #<void>)
10007 *** 0s 780000ns
10009 *** 0s 780000ns
10037 *** 0s 940000ns
(#<void> #<void> #<void>)
100003 *** 0s 2500000ns
100019 *** 0s 7500000ns
100043 *** 0s 2500000ns
(#<void> #<void> #<void>)
1000003 *** 0s 2190000ns
1000033 *** 0s 7810000ns
1000037 *** 0s 2190000ns
(#<void> #<void> #<void>)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.
Posted by Ken Dyck in Programming