; ======================================================================
;
; Structure and Interpretation of Computer Programs
; (trial answer to excercises)
;
; 计算机程序的构造和解释(习题试解)
;
; created: code17 02/28/05
; modified:
; (保持内容完整不变前提下，可以任意转载)
; ======================================================================
;; SICP No.1.24
;; 只需要修改 start-prime-test中所调用的判定质数的函数为fast-prime?即可
;; 另外，原fast-prime?函数中使用的true/false，在PLT Scheme中为#t/#f
(define (start-prime-test n start-time)
(if (fast-prime? n 3) ;;取测试次数为3
(report-prime (- (current-inexact-milliseconds) start-time))
#f))
;; 因为Fermat测试算法的时间复杂度是[theta](log(n))级的，因此n为1,000,000
;; 时的计算时间应当为n为1,000时的2倍左右。
;; 应该有如下关系t(1000):t(1000000):t(1000000000)=1:2:3左右
;; 测试数据（分析见后）
;; Test-it:
;;
;; Welcome to MzScheme version 209, Copyright (c) 2004 PLT Scheme, Inc.
;; > (search-for-primes 1000 3)
;;
;; 1001
;; 1003
;; 1005
;; 1007
;; 1009 *** 0.06298828125
;; 1011
;; 1013 *** 0.06396484375
;; 1015
;; 1017
;; 1019 *** 0.06591796875
;; finish
;;
;; > (search-for-primes 1000000 3)
;;
;; 1000001
;; 1000003 *** 0.162841796875
;; 1000005
;; 1000007
;; 1000009
;; 1000011
;; 1000013
;; 1000015
;; 1000017
;; 1000019
;; 1000021
;; 1000023
;; 1000025
;; 1000027
;; 1000029
;; 1000031
;; 1000033 *** 0.1630859375
;; 1000035
;; 1000037 *** 0.1708984375
;; finish
;; > (search-for-primes 1000000000 3)
;; 1000000001
;; 1000000003
;; 1000000005
;; 1000000007 *** 0.248046875
;; 1000000009 *** 0.2470703125
;; 1000000011
;; 1000000013
;; 1000000015
;; 1000000017
;; 1000000019
;; 1000000021 *** 0.24609375
;; finish
;; 分析：
;;
;; 由数据可见，t(1000)=0.6*, t(1000000)=0.16*, t(1000000000)=0.24*
;; 并非很严格地满足1:2:3，但基本满足与n之间的指数关系，其中后两者的关系
;; 比较符合2:3， 前两者的关系比例约为1:2.3左右
;; 根据我们的模型t(n) = c * log(n)
;; t(n^2) = c * log(n^2) = 2c * log(n)
;; 这表明，由于某些因素的作用，c在某些区间之间不保持一致，某些情况下
;; 产生了一定误差，但总体还是将指数增长的n降为一种近似线性关系的t。
;;
;; 考察我们分析时间复杂度的过程，我们可以发现，我们的时间复杂度计算基本根据
;; 递归的次数多少,我们认为即使在不同的n的情况下，每次递归的代价是一样的。
;; 而在每次递归中我们所进行的操作是random，squre和remainder，因此我们的
;; 分析基于一个基本假定：所有的这样操作，无论操作对象的大小位数，代价都是近
;; 似相同的。1 * 1的代价和10000 * 10000 是一样的。这个假设可以说是基本正
;; 确的，固定的机器代码操作是不论操作对象大小的。但，它也可能出问题，在那些
;; 操作对象的“字长”产生变化的时候。如果1和10000都是占用8位机器码，那么
;; 同样的操作作用在它们上的代价相同，但如果10000000000占用16位，那么操作
;; 的代价就是不同的了。
;;
;; 因此我们有这样的猜测，从1000到1000000的过程中，字长发生了变化(不一定是
;; 1000到1000000的字长不同，而是对它们的某些操作所使用的字长，比如square要
;; double操作数的位数)。 这很可能是为什么1000和1000000不严格符合比例，而
;; 1000000和1000000000基本符合比例的原因。
;;
;; 为了测试我们的想法，我们可以写一个测试函数
;; (define (test1 n c)
;; (* (remainder (* n (random n)) n)
;; (remainder (* n (random n)) n))
;; (if (> c 0) (test1 n (- c 1))))
;; 这个函数也使用类似fast-prime中的操作random，square和remainder，甚至对应
;; 的函数所产生的数字位数都基本近似，不同在于对于n和n^2，它们会执行“相同”多
;; 的次数c，在“不同”级别的操作数n上。这样它就把操作数的因素孤立了出来(操作次
;; 数现在是一样的了)。然后我们使用另一个(test n c)函数来调用它并测量使用时间
;; (define (test num times)
;; (display (current-inexact-milliseconds))
;; (newline)
;; (test1 num times)
;; (display (current-inexact-milliseconds))
;; (newline))
;; 结果和我们预测的一样
;; (test 1000 10000) 大约用了23毫秒时间
;; (test 1000000 10000) 大约用了69毫秒时间
;; (test 1000000000 10000) 同样用了大约69-71毫秒时间
;; 也就是说，执行同样的操作，1000000 1000000000 的代价是一样的，而1000则与它们
;; 不同(小于这两者)， 这很好地解释了我们在Fermat函数测试中的结果，这完全可能是
;; 字长变化产生的原因。 因此，我们知道，在正常情况下，我们可以认为同样的操作在
;; 不同的操作数上的代价基本相同，但某些涉及字长的特殊情况，则很可能是不同的。但
;; 无论如何，这样的误差同样是线性的，即常数因子的不同，不影响整体的复杂性量级。
;;
;; 另外，对于在题目1.22使用普通的prime?作测试函数时，为什么没发生这样的现象，我们
;; 可以发现一个很简单的解释。在1.22中，对于操作数n，具体计算函数操作数量级最高是
;; 是n，对于在此题中使用的最大的n=100000来说，[sqrt](100000)=10^5并不
;; 是很大；而在使用fermat-test的expmod时，具体计算函数的操作数的数量级是n^2，因此
;; 1000^2=10^6, 1000000^2=10^12。说明字长变化出现在10^6-10^12之间，这应该是
;; 为什么在使用普通prime?函数时没有明显误差的原因，它的字长没有达到变化的边界。
;; 注意，本实验的实际结果和字长分界点等情况与具体编译器和机器物理性质相关，请自行
;; 测试。另外，还有一个可能导致误差的原因，是n=1000比较小，一些基础的overhead(比
;; 如启动)比较明显，而在n为大数时则不明显，但这个原因的说服力不够。
