Exercise 1.22 · 习题

Exercise 1.22: Most Lisp implementations include
a primitive called runtime that returns an integer that specifies the
amount of time the system has been running (measured, for example, in
microseconds). The following timed-prime-test procedure, when called
with an integer n, prints n and checks to see if n is prime. If
n is prime, the procedure prints three asterisks followed by the amount of
time used in performing the 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))))

(define (report-prime elapsed-time)
(display " *** ")
(display elapsed-time))

Using this procedure, write a procedure search-for-primes that checks
the primality of consecutive odd integers in a specified range. Use your
procedure to find the three smallest primes larger than 1000; larger than
10,000; larger than 100,000; larger than 1,000,000. Note the time needed to
test each prime. Since the testing algorithm has order of growth of
Θ
(

n

), you should expect that testing for primes
around 10,000 should take about 10 times as long as testing for
primes around 1000. Do your timing data bear this out? How well do the data
for 100,000 and 1,000,000 support the Θ
(

n

) prediction? Is your

result compatible with the notion that programs on your machine run in time

proportional to the number of steps required for the computation?

练习 1.22：大多数 Lisp 实现都提供一个名为 runtime 的基本过程，它返回一个整数，表示系统已运行的时间（例如以微秒为单位）。下面的 timed-prime-test 过程在以整数 n 调用时，打印 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 过程，它在指定范围内检验连续奇数的素性。用你的过程找出分别大于 1000、10,000、100,000 和 1,000,000 的三个最小素数，并记录检验每个素数所需的时间。由于检验算法的增长阶为 Θ(√n)，你应当预期检验 10,000 附近的素数所需时间约为检验 1000 附近素数的 √10 倍。你的计时数据是否支持这一结论？100,000 和 1,000,000 的数据与 Θ(√n) 的预测是否吻合？你的结果是否与"程序在你的机器上的运行时间与计算所需步骤数成正比"这一观点相符？