1.22
练习 1.22： 大部分 Lisp 实现都包含一个 runtime 基本过程，调用它将返回一个整数，表示系统已经允许的时间（例如，以微秒计）。在对整数 n 调用下面的 timed-prime-test 过程时，将打印出 n 并检查 n 是否是素数。如果 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))
请利用这一过程写一个 search-for-primes 过程，它检查给定范围内连续的各个奇数的素性。请用你的过程找出大于 1 000、大于 10 000、大于 100 000 和大于 1 000 000 的三个最小素数。请注意其中检查每个素数所需要的时间。因为这一检查算法具有 的增长阶，你可以期望在 10 000 附近的素数检查的耗时大约是在 1 000 附近的素数检查的 倍。你得到的数据确实如此吗？对于 100 000 和 1 000 000 得到的数据，对这一 预测的支持情况如何？有人说程序在你的机器上运行的时间正比于计算所需的步数，你得到的结果符合这种说法吗？
先看下 timed-prime-test 执行的效果：
(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)) (display " 不是素数！")))
(define (report-prime elapsed-time)
(display " *** ")
(display 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 (+ test-divisor 1)))))
(define (divides? a b)
(= (remainder b a) 0))
(define (square x) (* x x))
(timed-prime-test 7)
(timed-prime-test 14)
分别找出大于 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 (+ test-divisor 1)))))
(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)
从这样的结果来看，还是非常符合 的预测的。运行的时间正比于执行所需步骤的判断也是正确的。
