sicp 练习 1.22

本来我都是在目录下完成练习，不过这道题实在比较特殊，光用文本解答可能效果不好。

我在这道题上卡了蛮久，一是因为最近放假，荒废起光阴来有了些冠冕堂皇的借口；二是这道题及后面几道相关的题并不像前面的练习一样把代码写出来就完事了，需要的是一种探索式的方法，这种方法可能是科学研究中最基本的，而这也恰恰是我所没有的。

题目里告诉我们大多数lisp实现都包括一个runtime过程，能以微秒的单位返回系统已运行的时间。坏消息是我用来做练习的guile并没有这个函数，好消息是我在这里^[1]找到了一个替代方案

(define (runtime) (tms:clock (times)))

题目的要求是给定一个起始数字，检测连续一段范围内奇数的素性。并且题目里给出了一段代码，要求你调用这段代码来完成练习。

(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))
  elapsed-time)

这是我给出的实现：

(define (search-for-primes start range)
  (if (> range 0)
      (timed-prime-test start))
  (if (> range 0)
      (search-for-primes (+ start 2) (- range 2)))

问题是在我看来这段代码并不好用，首先题目中这几个函数都没有返回值，也就是他们都是带有某种副作用的过程。没有返回值也就意味这没法根据不同的返回值进行不同的处理。并且题目中要求找出分别大于1e3, 1e4, 1e5, 1e6的三个最小的素数，那么只能给range指定一个足够大的数让它能至少包括三个素数，虽然带有一定的人工成分，但是完成这个任务依然是比较容易的。然而有一个棘手的问题是现在的电脑运行的太快，以至于题目中给出的几个数都被cpu轻松运算完，结果基本上都是0。解决的方法是把数加大，我简单乘了1w。

10000000
---------------------
10000019
10000079
10000103

100000000
---------------------
100000007
100000037
100000039

1000000000
---------------------
1000000007
1000000009
1000000021

10000000000
---------------------
10000000019
10000000033
10000000061

100000000000
---------------------
100000000003
100000000019
100000000057

1000000000000
---------------------
1000000000039
1000000000061
1000000000063

10000000000000
----------------------
10000000000037
10000000000051
10000000000099

我没有列出每个数runtime运行的结果，因为我发现对于小的数来说结果太有浮动性，任意取一次恐怕获得的结果不太好，于是又了运行多次求平均的简单想法。

(define (get-avg-runtime n times)
  (define (sum-runtime times sum)
    (if (= times 0)
	sum
	(sum-runtime (- times 1) (+ sum (timed-prime-test n)))))
  (/ (sum-runtime times 0) (+ times 0.0)))

然后把上面几个函数稍微改一下让他们返回值，对于已知的每个素数都运行一次，对越小的数取越大的times，得到结果。虽然结果依然会有一定的浮动，但浮动范围已经很小了。

10000000 times 1000
---------------------
10000019 0.55
10000079 0.549
10000103 0.558

100000000 times 1000
---------------------
100000007  1.743
100000037  1.746
100000039  1.734

1000000000 times 500
---------------------
1000000007 6.146
1000000009 6.14
1000000021 6.134

10000000000 times 250
---------------------
10000000019 20.416
10000000033 20.488
10000000061 20.456

100000000000 times 100
---------------------
100000000003 65.04
100000000019 65.59
100000000057 65.57

1000000000000 times 30
---------------------
1000000000039 211.47
1000000000061 206.6
1000000000063 206.83

10000000000000 times 10
----------------------
10000000000037 653.0
10000000000051 656.0
10000000000099 656.5

得到结果后，进行一个简单的统计^#1：

√10大概是3.162, 基本上可以对题目做肯定回答，运行的步骤和时间成正比。

[1] http://community.schemewiki.org/?SICP

#1 这里得到的时间的单位据说是毫秒，但我感觉不对，不过单位对这个练习没有任何影响。

• 全局相关文章