SICPの問題を解こう18

問題 1.35

     *Exercise 1.35:* Show that the golden ratio [phi] (section *Note           
     1-2-2::) is a fixed point of the transformation x |-> 1 + 1/x, and         
     use this fact to compute [phi] by means of the `fixed-point'               
     procedure.  

解

golden ratioの定義はを満たす正のであるので。
と置くと

となるのでfixed pointの定義であるを満たしている。
よってgolden ratioはとした時のfixed pointと等しい。

ではこの事実を使いfixed pointを計算するprocedureを書く

(define tolerance 0.0001)                                                       
(define (fixed-point f first-guess)                                             
  (define (close-enough? a b)                                                   
    (< (abs (- a b)) tolerance))                                                
  (define (try x)                                                               
    (let ((next (f x)))                                                         
      (if (close-enough? x next)                                                
          next                                                                  
          (try next))))                                                         
  (try first-guess))                                                            
                                                                                
(print (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)) 

lambda, letを使わせる問題は初出かな？
LISPはSICP以外では勉強していないので初めてlambdaとlet部分を読んだけど、問題1.29あたりで(set! ..)とやってた所を局所変数としてletが使えるのは楽そう。lambdaも無名関数として便利に使えそうだし。でもlambdaの真の意味（？）はもっと先を読まないとわからなそう。

問題 1.36

をにおけるfixed pointを使って求めよという問題

解

(define tolerance 0.0001)                                                       
(define (fixed-point f first-guess)                                             
  (define (close-enough? a b)                                                   
    (< (abs (- a b)) tolerance))                                                
  (define (try x count)                                                         
    (let ((next (f x)))                                                         
      (display next)                                                            
      (display "\t")                                                            
      (display count)                                                           
      (newline)                                                                 
      (if (close-enough? x next)                                                
          next                                                                  
          (try next (+ count 1)))))                                             
  (try first-guess 0))                                                          
                                                                                
(define (average x y)                                                           
  (/ (+ x y) 2))                                                                
                                                                                
(print "without average damping")                                               
(print (fixed-point (lambda (x) (/ (log 1000) (log x))) 5))                     
(print "with average damping")                                                  
(print (fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 5)) 

結果

without average damping
4.29202967422018        0
4.741863119908242       1
4.438204569837609       2
4.635299887107611       3
4.50397811613643        4
4.589989462723705       5
4.53301150767844        6
4.570475672855484       7
4.545720389670642       8
4.562024936588171       9
4.551263234080531       10
4.55835638768598        11
4.553676852183342       12
4.55676216434628        13
4.554727130670954       14
4.556069054770006       15
4.555184018843625       16
4.5557676565438205      17
4.555382746639082       18
4.55563658243586        19
4.555469180245326       20
4.555579577900997       21
4.5555067722873686      22
4.5555067722873686
with average damping
4.64601483711009        0
4.571611286076025       1
4.558294317536066       2
4.556006022881116       3
4.555615799731297       4
4.555549342575593       5
4.555549342575593

average dampingの方が速く収束していることがわかる。
※よりもが速く収束する事を言っているにすぎない。