1.23
练习 1.23： 在本节开始时给出的那个 smallest-divisor 过程做了许多无用检查： 在它检查了一个数是否能被 2 整除之后，实际上已经完全没有必要再检查它是否能被任何偶数整除了。这说明 test-divisor 所用的值不应该是 2，3，4，5，6，……，而应该是 2，3，5，7，9，……。 请实现这种修改。其中应定义一个过程 next，用 2 调用它时返回 3，否则就返回其输入值加 2.修改 smallest-divisor 过程，使它去使用 (next test-divisor) 而不是 (+ test-divisor 1)。让 timed-prime-test 结合这个 smallest-divisor 版本，运行练习 1.22 里的 12 个找素数的测试。因为这一修改使检查的步数减少一半，你可能期望它的运行速度快一倍。实际情况符合这一预期吗？如果不符合，你所观察到的两个算法速度的比值是什么？你如何解释这一比值不是 2 的事实？
分别找出大于 1 000、 10 000、 100 000、 1 000 000 的三个最小素数
(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 (sqrt-iter lastGuess guess x)
(if (good-enough? lastGuess guess)
guess
(sqrt-iter guess (improve guess x) x)
)
)
(define (good-enough? lastGuess guess)
(< (abs (- lastGuess guess)) 0.001)
)
(define (improve guess x)
(average guess (/ x guess)))
(define (average x y)
(/ (+ x y) 2))
(define (report-prime n elapsed-time)
(newline)
(display n)
(display " _\*\* ")
(display elapsed-time)
(display ", 它的 $\\sqrt{n}$ 倍时间是 ")
(display (_ elapsed-time (sqrt-iter 1 10 elapsed-time)))
)
(define (prime? n)
(= n (smallest-divisor n)))
(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 (next test-divisor)))))
(define (next current)
(if (= current 2) 3 (+ current 2))
)
(define (divides? a b)
(= (remainder b a) 0))
(define (square x) (\* x x))
(define (timed-prime-test-between n1 n2 found)
(if (timed-prime-test n1)
(if (or (> found 1) (> n1 n2))
(display " 测试结束！ ")
(timed-prime-test-between (+ n1 1) n2 (+ found 1))
)
(if (> n1 n2)
(display " 测试结束！ ")
(timed-prime-test-between (+ n1 1) n2 found)
)
)
)
(newline)
(display "大于 1000 的三个最小素数：")
(timed-prime-test-between 1001 9999 0)
(newline)
(newline)
(display "大于 10 000 的三个最小素数：")
(timed-prime-test-between 10001 99999 0)
(newline)
(newline)
(display "大于 100 000 的三个最小素数：")
(timed-prime-test-between 100001 999999 0)
(newline)
(newline)
(display "大于 1 000 000 的三个最小素数：")
(timed-prime-test-between 1000001 9999999 0)
(newline)
以该测试机器为例：
| 大于 | 优化前 | 优化后 | 比值 |
|---|---|---|---|
| 1000 | 2 | 1 | 2 |
| 10 000 | 2 | 2 | 1 |
| 100 000 | 6 | 4 | 1.5 |
| 1 000 000 | 14 | 9 | 1.6 |
可以看到优化后的速度并没有快一倍，而是在 1.5 倍左右。
原因是虽然检查的步骤少了一半，但是整个寻找过程中，检查的步骤没有占到全部，还有一些例行的步骤在。并且相对于优化前的步骤，多出了 next 这个决定下一个检查数的步骤，不再是简单地累加 1 了，而是有个 if 判断。