sicp 练习 1.23

10000000改进函数

(define (find-devisor n test-devisor)
  (cond ((> (square test-devisor) n) n)
	((divides? test-devisor n) test-devisor)
	(else (find-devisor n (next test-devisor)))))

(define (next n)
  (if (= n 2)
      3
      (+ n 2)))

10000000 times 1000
---------------------
10000019 0.341
10000079 0.343
10000103 0.342

100000000 times 1000
---------------------
100000007 1.079
100000037 1.048
100000039 1.035

1000000000 times 500
---------------------
1000000007 3.708
1000000009 3.692
1000000021 3.81

10000000000 times 250
---------------------
10000000019 12.088
10000000033 11.94
10000000061 11.956

100000000000 times 100
---------------------
100000000003 37.91
100000000019 38.44
100000000057 38.14

1000000000000 times 30
---------------------
1000000000039 118.967
1000000000061 121.333
1000000000063 118.9

10000000000000 times 10
----------------------
10000000000037 386.7
10000000000051 384.5
10000000000099 385.8

用上面的结果列表：

可以看到比值并不是2，一个直观的解释是我们定义的next是一个函数，对一个数的检测要调用next√n / 2 次，造成以一定的开销损耗。可以观察到，其实我们找出来的素数都是奇数，也就不需要为2单独判断，于是可以把next函数改为(+ test-divisor 2)，再进行一次实验。

10000000 times 1000
---------------------
10000019 0.276
10000079 0.275
10000103 0.282

100000000 times 1000
---------------------
100000007 0.866
100000037 0.868
100000039 0.868

1000000000 times 500
---------------------
1000000007 3.054
1000000009 3.084
1000000021 3.058

10000000000 times 250
---------------------
10000000019 9.956
10000000033 10.292
10000000061 10.18

100000000000 times 100
---------------------
100000000003 32.36
100000000019 33.35
100000000057 32.49

1000000000000 times 30
---------------------
1000000000039 101.333
1000000000061 103.4
1000000000063 102.433

10000000000000 times 10
----------------------
10000000000037 319.6
10000000000051 331.1
10000000000099 341.9

可以看到调整之后的比例基本都在2的附近，所以可以肯定损耗的原因是next函数带来的开销了。

• 全局相关文章