SICP 习题 (1.22) 解题总结

SICP 习题 1.22 要求改进题中列举出来检查素数的过程，用来求1000， 10000， 100 000，还有1000 000附近的素数，然后比较求这些素数的时间，看是否符合θ(√n)的复杂度。

要完成这道题首先要将题目中列出的过程照抄到你的Scheme环境中。因为书中的代码使用了（runtime）过程，我就先在我的环境中测试了(runtime)的结果，很悲剧地发现(runtime)的返回值好几秒才变一个数字，根本没办法用来纪录计算过程所需要的时间。于是去查Mit-Scheme的参考文档，找到过程(real-time-clock) ，发现(real-time-clock)还靠谱一点，返回的是一个很长的整数，每次手工执行(real-time-clock)都返回一个不同的数值。

于是使用(real-time-clock)代替(runtime)写了以下过程：

(define (timed-prime-test n)
  (start-prime-test n (real-time-clock)))

(define (start-prime-test n start-time)
  (if (prime? n)
      (begin 
	(report-prime n (- (real-time-clock) start-time))
	#t)
      #f))

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

除了使用（real-time-clock)代替(runtime)以外，这里的过程代码和书中的也不太一样，主要是一些输出的过程有调整，这样在后面的使用中不会那么啰嗦。另外添加了返回值，表示检查的目标数是否为素数。

有了以上过程就可以去检查任意一个数是否为素数，如果是的话会打印检查所花费的时间，同时返回＃t。

接着按题目要求，定义过程去查找比1000大的三个素数，还有比10000, 100 000,1000 000大的三个素数，看花费多长时间。

我定义的过程如下：

(define (find-prime start end number)
  (if (even? start) 
      (find-prime (+ start 1) end number)
      (find-prime-iter start end 0 number)))

(define (find-prime-iter start end cur-number max-number)
  (if (and (< start end) (< cur-number max-number))
      (if (timed-prime-test start)
	  (find-prime-iter (+ start 2) end (+ 1 cur-number) max-number)
	  (find-prime-iter (+ start 2) end cur-number max-number))
      cur-number))

过程(find-prime)接受三个参数：查找的起点，终点，还有需要查找的素数个数，如果找到的素数超过指定的数量，或者知道终点都没有找足指定数量的素数，过程都会返回，返回值是找到的素数个数。

后来测试了一下，发现找比1000大的三个素数没有多大意义，因为计算机太快，总认为在0单位时间内就找到三个素数。

后来就增加了测试数的大小。 增加到10 000 000的时候开始出现有意义的结果，执行结果如下：

1 ]=> (find-prime 10000000 10002000 3)
10000019 *** 5
10000079 *** 5
10000103 *** 5
;Value: 3

1 ]=> (find-prime 100000000 100002000 3)
100000007 *** 16
100000037 *** 14
100000039 *** 15
;Value: 3

1 ]=> (find-prime 1000000000 1000002000 3)
1000000007 *** 48
1000000009 *** 50
1000000021 *** 46
;Value: 3

可以发现查找100000000附近的素数花费的时间大概是查找10000000附近的素数时间的3倍。

总结来讲，就是目标数大10倍，检验它是否为素数的时间就大3倍。

这一点和书中要求我们检查的“根号10”的结果接近，因为“根号10”的计算结果大概就是3左右。