SICP 习题参考答案，3.5

win_hate

• a.
  
  
  1. 
     
  2. (define (integrate-series s)
     
  3.   (define (f s n)
     
  4.     (if (null? s) '()
     
  5.         (cons-stream (/ (stream-car s) (+ n 1))
     
  6.                      (f (stream-cdr s) (+ n 1)))))
     
  7.   (f s 0))
     
  8. 
     
  9. (define exp-series
     
  10.   (cons-stream 1 (integrate-series exp-series)))
      

  复制代码
  
  
  演示：计算  exp(x)
  
  
  1. 
     
  2. > (take exp-series 10)
     
  3. (1 1 1/2 1/6 1/24 1/120 1/720 1/5040 1/40320 1/362880)
     

  复制代码
  
  
  maxima 验证：
  
  
  1. 
     
  2. taylor(exp(x), x, 0, 10)
     
  3. 
     
  4. 1+x+x^2/2+x^3/6+x^4/24+x^5/120+x^6/720+x^7/5040+x^8/40320+x^9/362880+x^10/3628800+...
     

  复制代码
  
  
  
• b.
  
  1. 
     
  2. (define sin-series
     
  3.   (cons-stream 0 (integrate-series cos-series)))
     
  4. 
     
  5. (define cos-series
     
  6.   (cons-stream 1 (integrate-series
     
  7.                   (scale-series -1 sin-series))))
     

  复制代码
  
  
  演示
  
  
  1. 
     
  2. > (take sin-series 10)
     
  3. (0 1 0 -1/6 0 1/120 0 -1/5040 0 1/362880)
     
  4. > (take cos-series 11)
     
  5. (1 0 -1/2 0 1/24 0 -1/720 0 1/40320 0 -1/3628800)
     

  复制代码
  
  
  maxima 验证：
  
  
  1. 
     
  2. taylor (sin(x), x, 0, 11)
     
  3. 
     
  4. x-x^3/6+x^5/120-x^7/5040+x^9/362880-x^11/39916800+...
     
  5. 
     
  6. taylor (cos(x), x, 0, 10)
     
  7. 
     
  8. 1-x^2/2+x^4/24-x^6/720+x^8/40320-x^10/3628800+...
     

  复制代码
  
  [ 本帖最后由 win_hate 于 2009-1-23 10:04 编辑 ]

win_hate

Exercise 3.60.  With power series represented as streams of coefficients as in exercise 3.59, adding series is implemented by add-streams. Complete the definition of the following procedure for multiplying series:

(define (mul-series s1 s2)
  (cons-stream <??> (add-streams <??> <??>)))

You can test your procedure by verifying that sin^2 x + cos^2 x = 1, using the series from exercise 3.59.

win_hate

设 s1 = a(0)+A(x)x, s2=b(0)+B(x)x

有 s1 s2 = a(0) s2 + A(x) s2 x = a(0)b(0) + a(0) B(x) x + A(x) s2 x

1. 
   
2. (define add-series add-streams)
   
3. 
   
4. (define (mul-series s1 s2)
   
5.   (cons-stream (* (stream-car s1) (stream-car s2))
   
6.                (add-series (scale-series (stream-car s1) (stream-cdr s2))
   
7.                            (mul-series (stream-cdr s1) s2))))
   
8. 
   
9. (define one
   
10.   (let ((s1 (mul-series sin-series sin-series))
    
11.         (s2 (mul-series cos-series cos-series)))
    
12.     (add-series s1 s2)))
    

复制代码

演示

1. 
   
2. > (take one 20)
   
3. (1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
   

复制代码

[ 本帖最后由 win_hate 于 2009-1-23 09:45 编辑 ]

win_hate

Exercise 3.61.  Let S be a power series (exercise 3.59) whose constant term is 1. Suppose we want to find the power series 1/S, that is, the series X such that S · X = 1. Write S = 1 + SR where SR is the part of S after the constant term. Then we can solve for X as follows:



In other words, X is the power series whose constant term is 1 and whose higher-order terms are given by the negative of SR times X. Use this idea to write a procedure invert-unit-series that computes 1/S for a power series S with constant term 1. You will need to use mul-series from exercise 3.60.

win_hate

1. 
   
2. (define (inv-series s)
   
3.   (define inv (cons-stream 1 (scale-series -1
   
4.                               (mul-series (stream-cdr s) inv))))
   
5.   inv)
   

复制代码

演示

1. 
   
2. > (take (mul-series cos-series (inv-series cos-series)) 20)
   
3. (1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
   
4. >
   

复制代码

win_hate

Exercise 3.62.  Use the results of exercises 3.60 and 3.61 to define a procedure div-series that divides two power series. Div-series should work for any two series, provided that the denominator series begins with a nonzero constant term. (If the denominator has a zero constant term, then div-series should signal an error.) Show how to use div-series together with the result of exercise 3.59 to generate the power series for tangent.

win_hate

1. 
   
2. (define (div-series s1 s2)
   
3.   (if (eq? (stream-car s2) 0)
   
4.       (error "not a unit" s2)
   
5.       (let* ((c (stream-car s2))
   
6.              (t2 (scale-series (/ 1 c) s2))
   
7.              (t1 (scale-series c s1)))
   
8.         (mul-series t1 (inv-series t2)))))
   
9. 
   
10. (define tan-series
    
11.   (div-series sin-series cos-series))
    

复制代码

演示

1. 
   
2. > (take tan-series 10)
   
3. (0 1 0 1/3 0 2/15 0 17/315 0 62/2835)
   

复制代码

maxiam 验证

1. 
   
2. taylor(tan(x), x, 0, 10);
   
3. 
   
4. x+x^3/3+(2*x^5)/15+(17*x^7)/315+(62*x^9)/2835+...
   

复制代码

[ 本帖最后由 win_hate 于 2009-1-23 10:00 编辑 ]

win_hate

Exercise 3.63.  Louis Reasoner asks why the sqrt-stream procedure was not written in the following more straightforward way, without the local variable guesses:

(define (sqrt-stream x)
  (cons-stream 1.0
               (stream-map (lambda (guess)
                             (sqrt-improve guess x))
                           (sqrt-stream x))))

Alyssa P. Hacker replies that this version of the procedure is considerably less efficient because it performs redundant computation. Explain Alyssa's answer. Would the two versions still differ in efficiency if our implementation of delay used only (lambda () <exp>) without using the optimization provided by memo-proc (section 3.5.1)?

win_hate

• 先分析使用局部变量 guesses 的版本:
  
  
  1. 
     
  2. (define (sqrt-stream x)
     
  3.   (define guesses
     
  4.     (cons-stream 1.0
     
  5.                  (stream-map (lambda (guess)
     
  6.                                (sqrt-improve guess x))
     
  7.                              guess)))
     
  8.   guess)
     

  复制代码
  
  
  
  • 
    使用如下缩写：
    stream-cdr: scdr
    stream-map: smap
    sqrt-improve: f
    (lambda () ...) : ()->...
    
    
    设 sqrt-stream 产生的流序列为 r0, r1, r2, ...
    设 R0 = (sqrt-stream 2)。对 R0 不断 scdr，可以得到一系列的 pairs，这些 pairs 都只有
    两项。第一项是个实数 r_i，第二项是个无参函数。把这些 pairs 记为 R1, R2, R3, ...
    如果要访问 r_i，则需求出 R_i，然后 car 出其第一项。car 是平凡的，重点在于如何求出 R_i。
    
    R0 = (r0, ()-> (smap f R0))
    
    假如现在要求 R1, 则需要对 (cdr R0) 进行 force。即 (scdr R0)，也就是 (smap f R0)。
    
    smap 把 R0 的首项 r0 car 出来，f 作用后，cons-stream 到 (smap f (scdr R0)) 上。得到：
    
    R1 = (r1, ()-> (smap f (scdr R0)))。
    
    要注意 cons-stream 是个宏，它是特殊的，(scdr R0) 并没有被马上求值。
    
    好，现在我们求 R2, 即 (smap f (scdr R0))。
    
    smap 是个函数，所以先对 (scdr R0) 进行求值。先不管复杂度，(scdr R0) 是求值过的，我们知道
    结果是 R1，值为 (r1, ()-> (smap f (scdr R0)))。因此 (smap f (scdr R0)) 就是
    (smap f R1)。
    
    从 R1 中提出出 r1 并把 f 作用上去得到 r2。然后把 r2 cons-stream 到 (smap f (scdr R1)))
    上得到
    
    R2 = (r2, ()-> (smap f (scdr R1)))。
    
    接着求 R3= (smap f (scdr R1)) = (smap f R2) = (r3, ()-> (smap f (scdr R2)))
    
    ......
    
    不难看出，模式为: R[j] = (r[j], ()-> (smap f (scdr R[j-1])))
    
  • 现在来考虑计算量，以从 R[j-1] 求值 R[j] 为例。
    
    不带记忆的情形：
    
    R[j] = (smap f (scdr R[j-1])) = (smap f (smap f (scdr R[j-2])))
    = ... = (smap f (smap f (smap f ... (smap f R[0]))))
    
    或
    
    R[j] = (scdr R[j-1]) = (scdr (scdr R[j-2])) = ... = (scdr^j, R[0])
    
    每执行一次 scdr，都进行了一次 force，f 也被执行一次。如果认为耗时的主要在 f，则从 R[j-1]
    计算 R[j] 要执行  f j 次。这显然不合算，因为从 r[j-1] 计算 r[j] 只需要执行 f 一次。
    
    如果 (define S2 (sqrt-stream 2))，现在考虑 (stream-ref S2 n) 的计算量。为访问 r[0]，
    必须计算出 R[0], R[1], ..., R[n]，所以 f 被执行了 1+2+...+n 次。复杂度为 O(n^2).
    更糟糕的是，以后再次访问 S2 中的第 n 项，这些计算全会重新执行。
    
    如果是带记忆的版本，delay 被首次 force 时，会把计算结果存放在一个局部变量中。当 delay
    被再次 force 时，它简单地返回已保存的值。此时从 R[j-1] 求值 R[j] 将会是
    
    R[j] = (r[j], ()-> (smap f (scdr R[j-1])))
    R[j] = (scdr R[j-1]) = (smap f (scdr R[j-2]))
    
    由于 (scdr R[j-2]) 在计算 R[j-1] 时已经求值过，所以直接返回保存的值
    (r[j-1], ()-> (smap f (scdr R[j-2])))
    
    所以
    
    R[j] = (smap f (r[j-1], ()-> (smap f (scdr R[j-2]))))
    = (f(r[j-1]), ()-> (smap f (scdr (r[j-1], ()->(smap f (scdr R[j-2]))))))
    = (r[j], ()-> (smap f (scdr R[j-1])))
    
    这样只需要执行一次 f，两次 force。两次 force 中，一次是新的，一次是 force 过的。
    
    若 (define S2 (sqrt-stream 2))。则首次 (stream-ref S2 n) 时，需要执行 f n 次。
    若再次执行 (stream-ref S2 n)，则无需执行 f，但仍需要 O(n) 次 force.
    
  
  
• 最后看一下无局部变量 guesses 的版本：
  
  
  1. 
     
  2. (define (sqrt-stream x)
     
  3.   (cons-stream 1.0
     
  4.                (stream-map (lambda (guess)
     
  5.                              (sqrt-improve guess x))
     
  6.                            (sqrt-stream x))))
     

  复制代码
  
  
  这个版本有缺陷。stream-map 调用中使用 (sqrt-stream x) 会生成一个“新”的平方根序列，
  从而无法利用 delay 的记忆机制保存的值。在首次求值时，效率上等同于没有记忆。
  
  比如：(define x (sqrt-stream 2))，则首次 (stream-ref x n) 时，效率与带 guesses
  版本使用无记忆 delay 时相当，即 O(n^2)。 但再次访问 x 中已求值的项时，delay 的记忆机
  制将发挥作用，从而使访问量降为 O(n).
  

[ 本帖最后由 win_hate 于 2009-2-1 11:02 编辑 ]

win_hate

Exercise 3.64.  Write a procedure stream-limit that takes as arguments a stream and a number (the tolerance). It should examine the stream until it finds two successive elements that differ in absolute value by less than the tolerance, and return the second of the two elements. Using this, we could compute square roots up to a given tolerance by

(define (sqrt x tolerance)
  (stream-limit (sqrt-stream x) tolerance))