SICP 习题参考答案 1.2

win_hate

1. 
   
2. (define (mul a b)
   
3.   (define (f a b c)
   
4.     (cond ((= b 0) c)
   
5.           ((even? b) (f (+ a a) (/ b 2) c))
   
6.           (else (f a (- b 1) (+ c a)))))
   
7. 
   
8.   (f a b 0))
   

复制代码

win_hate

Exercise 1.19.   There is a clever algorithm for computing the Fibonacci numbers in a logarithmic number of steps. Recall the transformation of the state variables a and b in the fib-iter process of section 1.2.2: a  a + b and b  a. Call this transformation T, and observe that applying T over and over again n times, starting with 1 and 0, produces the pair Fib(n + 1) and Fib(n). In other words, the Fibonacci numbers are produced by applying Tn, the nth power of the transformation T, starting with the pair (1,0). Now consider T to be the special case of p = 0 and q = 1 in a family of transformations Tpq, where Tpq transforms the pair (a,b) according to a  bq + aq + ap and b  bp + aq. Show that if we apply such a transformation Tpq twice, the effect is the same as using a single transformation Tp'q' of the same form, and compute p' and q' in terms of p and q. This gives us an explicit way to square these transformations, and thus we can compute Tn using successive squaring, as in the fast-expt procedure. Put this all together to complete the following procedure, which runs in a logarithmic number of steps:41

(define (fib n)
  (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   <??>      ; compute p'
                   <??>      ; compute q'
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

[ 本帖最后由 win_hate 于 2008-9-9 13:30 编辑 ]

win_hate

1. 
   
2. (define (fib n)
   
3.   (fib-iter 1 0 0 1 n))
   
4. (define (fib-iter a b p q count)
   
5.   (cond ((= count 0) b)
   
6.         ((even? count)
   
7.          (fib-iter a
   
8.                    b
   
9.                    (+ (* p p) (* q q))      ; compute p'
   
10.                    (+ (* 2 p q) (* q q))    ; compute q'
    
11.                    (/ count 2)))
    
12.         (else (fib-iter (+ (* b q) (* a q) (* a p))
    
13.                         (+ (* b p) (* a q))
    
14.                         p
    
15.                         q
    
16.                         (- count 1)))))
    

复制代码

理论分析：

把矩阵 T:=

1 1
1 0

乘到 (fib(n-1) fib(n-2))^t 上就可以得到 (fib(n) fin(n-1)). 所以求 (fib(n+1) fib(n)) 相当于计算 T^n (1,0)^t。

若 a 是半群 A 的一个元素，则总可以用本节说讲的方法计算 a^n. 这种方法实际上是从右向左扫描 n 的比特，也可以采用从左向右扫描比特方法。

如果 a 在 A 中有逆且容易求出，则计算的开销可以进一步减少。

参考资料：

• 关于 fib 序列的计算，可以参考我 blog 上的一个帖子：[计算 Fibonacci 数的一些注记]
  
• 关于 fibonacci 数列的一般性介绍，可以参考维基百科的词条: [Fibonacci Number].
  
• 关于 Fibonacci 的生平，可以参考维基百科的词条: [Fibonacci].
  

======================================================================

Leonardo of Pisa (Fibonacci)

1170~1250

意大利数学家

[ 本帖最后由 win_hate 于 2008-9-14 11:53 编辑 ]

win_hate

1. 
   
2. (define (gcd a b)
   
3.   (if (= b 0)
   
4.       a
   
5.       (gcd b (remainder a b))))
   

复制代码

Exercise 1.20.  The process that a procedure generates is of course dependent on the rules used by the interpreter. As an example, consider the iterative gcd procedure given above. Suppose we were to interpret this procedure using normal-order evaluation, as discussed in section 1.1.5. (The normal-order-evaluation rule for if is described in exercise 1.5.) Using the substitution method (for normal order), illustrate the process generated in evaluating (gcd 206 40) and indicate the remainder operations that are actually performed. How many remainder operations are actually performed in the normal-order evaluation of (gcd 206 40)? In the applicative-order evaluation?

win_hate

应用序比较简单，把它放前面来。

(2) 应用序  

辗转序列为 206, 40, 6, 4, 2, 0

显然进行了 4 次 remainder.


(1) 正则序

把 reaminder 简单记为 r，分析一下逐步展开的过程

1. 
   
2. (if (= b 0) a
   
3.   (gcd b (r a b)))
   

复制代码

继续

1. 
   
2. (if (= b 0) a
   
3.   (if (= (r a b) 0) b
   
4.     (gcd (r a b) (r b (r a b)))))
   

复制代码

1. 
   
2. (if (= b 0) a
   
3.   (if (= (r a b) 0) b
   
4.     (if (= 0 (r b (r a b))) (r a b)
   
5.       (gcd (r b (r a b)) (r (r a b) (r b (r a b))))
   

复制代码

r 会在两个地方被执行，一是 if 判断 r 的结果是否为 0， 另一个是最终返回的最大公因子，它是用一串嵌套的 r 来求值的。

辗转序列为 205, 40, (r 205, 40), (r 40 (r 205, 40)) , (r (r 205, 40) (r 40 (r 205 40))), .....

设这串数中每个数包含 r 的个数为 a(n)，r 的增长模式为

x, y -> (r x y)

所以 a(n)=a(n-1)+a(n-2)+1，这是个什么序列？变个形

a(n)+1 = a(n-1)+1 + a(n-2)+1，a(0)+1=a(1)+1=1.

原来 a(n)=fib(n)-1

辗转序列的值为 205, 40, 6, 4, 2, 0，包含 r 的个数为  0, 0, 1, 2, 4, 7。用 if 进行判断时，r 执行了 1+2+4+7=14 (次).

但返回的最大公因子是辗转序列的倒数第二项，其中含有 4 个 r。所以 r 总共被执行了

(1+2+4+7)+4 = 18 (次).

[ 本帖最后由 win_hate 于 2008-9-11 22:20 编辑 ]

win_hate

Exercise 1.21.  Use the smallest-divisor procedure to find the smallest divisor of each of the following numbers: 199, 1999, 19999.

win_hate

1. 
   
2. > (map smallest-divisor '(199 1999 19999))
   
3. (199 1999 7)
   

复制代码

win_hate

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?

win_hate

在 guile, scm 中，runtime 的对应函数为 current-time，返回的单位是秒。在 mzscheme 中，runtime 的对应函数为 current-milliseconds，精确度要高一些。在这里，我们使用后者。

1. 
   
2. (define (search-for-primes a b)
   
3.   (define (timed-prime-test n)
   
4.     (newline)
   
5.     (display n)
   
6.     (start-prime-test n (current-milliseconds)))
   
7.   
   
8.   (define (start-prime-test n start-time)
   
9.     (if (prime? n)
   
10.          (report-prime (- (current-milliseconds) start-time))))
    
11.   
    
12.   (define (report-prime elapsed-time)
    
13.     (display " *** ")
    
14.     (display elapsed-time))
    
15. 
    
16.   (cond ((even? a) (search-for-primes (+ a 1) b))
    
17.         ((< a b) (if (timed-prime-test a) (search-for-primes (+ a 2) b)))))
    

复制代码

用上面的代码可以找出相应的素数为：

1009 , 10007, 100003, 1000003

接着讨论时间复杂度。现在的计算机速度很快，在我的机器上，测试前三个素数的时间为 0 毫秒，而测试 1000003 的时间是 1 毫秒。所以有必要把对一个数的测试反复执行多次。为此，我写了一个 prime-test-prof

1. 
   
2. (define (prime-test-prof p m)
   
3.     (define (f m)
   
4.       (cond ((> m 0) (prime? p)
   
5.              (f (- m 1)))))
   
6.             
   
7.   (let ((t (current-milliseconds)))
   
8.     (f m)
   
9.     (- (current-milliseconds) t)))
   

复制代码

执行 100 次的时间

1009: 5
10007: 12

(* 5 (sqrt 10)) =15.811388300841898

执行 1000 次的时间

1009: 45
10007:130

(* 45 (sqrt 10))=142.30249470757707

执行 10000 次的时间

1009: 224
10007:940

(* 224 (sqrt 10))=708.350195877717

执行 100000 次的时间

1009: 2153
10007: 7060

(* 2153 (sqrt 7060))=6808.383802342521

执行 500000 次的时间

1090: 9968
10007: 32669

(* 9968 (sqrt 10))=31521.583716558405

当执行次数比较多时，因子 sqrt(10) 还算比较精确的。

将被测试的数改为 100003 和 1000003 的结果与上面的类似，仍然是 3 倍左右的关系。 这里是一个执行 100000 次的结果

100000 次

100003：19649
1000003：62005

最后一个问题：

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?

题目中的 steps 比较含糊，不清楚是什么意思。如果是在一台理想的计算机上，这些 step 直接对应为机器的指令（或总复杂度为 O(1) 的指令序列），那么上述说法对运行时间的上界应该是正确的。

但如果一个 step 只是概念上的，则不然。比如在前面的运算中，我们用到加法，乘法，除法。注意到很多 scheme 实现支持任意长度的整数运算，所以这些运算的复杂度与参与运算的数的大小相关。

[ 本帖最后由 win_hate 于 2008-9-12 14:18 编辑 ]

win_hate

Exercise 1.23.  The smallest-divisor procedure shown at the start of this section does lots of needless testing: After it checks to see if the number is divisible by 2 there is no point in checking to see if it is divisible by any larger even numbers. This suggests that the values used for test-divisor should not be 2, 3, 4, 5, 6, ..., but rather 2, 3, 5, 7, 9, .... To implement this change, define a procedure next that returns 3 if its input is equal to 2 and otherwise returns its input plus 2. Modify the smallest-divisor procedure to use (next test-divisor) instead of (+ test-divisor 1). With timed-prime-test incorporating this modified version of smallest-divisor, run the test for each of the 12 primes found in exercise 1.22. Since this modification halves the number of test steps, you should expect it to run about twice as fast. Is this expectation confirmed? If not, what is the observed ratio of the speeds of the two algorithms, and how do you explain the fact that it is different from 2?