SICPの問題を解こう19 - ウォンツテック

問題 1.37.a

         k-term finite continued fraction
                      N_1                                                       
               -----------------                                                
                         N_2                                                    
               D_1 + -----------                                                
                     ...    N_K                                                 
                         + -----                                                
                            D_K                                                 
                                                                                
          Suppose that `n' and `d' are procedures of one argument (the          
          term index i) that return the n_i and D_i of the terms of the         
          continued fraction.  Define a procedure `cont-frac' such that         
          evaluating `(cont-frac n d k)' computes the value of the              
          k-term finite continued fraction.  Check your procedure by            
          approximating 1/[phi] using                                           
                                                                                
               (cont-frac (lambda (i) 1.0)                                      
                          (lambda (i) 1.0)                                      
                          k)                                                    
                                                                                
          for successive values of `k'.  How large must you make `k' in         
          order to get an approximation that is accurate to 4 decimal           
          places?

まずは(cont-frac n d k)を求めるために数学的に考えると

2元のパラメータを持つ数列 を以下のように定義する


これよりk-term continued finite fractionはのように表現出来、この数列の特性から

となる

以上の特性から再帰的に $C_{1,k}$ を求めるprocedureを書き、 $C_{1,k}$ と $C_{1,k+1}$ の差が4桁の精度となるよう0.0001以下になる時のkの値を求めるprocedureを書く

(define (cont-frac n d k)                                                       
  (define (cont-frac-itr n d k m)                                               
    (if (= m k)                                                                 
        (/ (n k) (d k))                                                         
        (/ (n m) (+ (d m) (cont-frac-itr n d k (+ m 1))))))                     
  (cont-frac-itr n d k 1))                                                      
                                                                                
(define tolerance 0.0001)                                                       
(define (close-enough? a b)                                                     
  (< (abs (- a b)) tolerance))                                                  
                                                                                
(define (k-check)                                                               
  (define (k-check-itr begin count)                                             
    (let ((next (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) count)))           
      (print next)                                                              
      (if (close-enough? begin next)                                            
          count                                                                 
          (k-check-itr next (+ count 1)))))                                     
  (k-check-itr 1 2))                                                            
                                                                                
(display "The k which I want to calcurate is ")                                 
(print (k-check))

結果

0.5
0.6666666666666666
0.6000000000000001
0.625
0.6153846153846154
0.6190476190476191
0.6176470588235294
0.6181818181818182
0.6179775280898876
0.6180555555555556
11

問題 1.37.b

問題aは再帰的に解いたので反復的にする

(define (cont-frac n d k)                                                       
  (define (cont-frac-itr n d k m x)                                             
    (if (= m 1)                                                                 
        x                                                                       
        (cont-frac-itr n d k (- m 1) (/ (n m) (+ (d m) x)))))                   
  (cont-frac-itr n d k k 1))

問題 1.38

finite continued fractionでN_k = 1, D_k = 1 2 1 1 4 1 1 6 1 1 8 ... の時に自然対数の底e-2が求まるよという問題

(define (cont-frac n d k)                                                       
  (define (cont-frac-itr n d k m)                                               
    (if (= m k)                                                                 
        (/ (n k) (d k))                                                         
        (/ (n m) (+ (d m) (cont-frac-itr n d k (+ m 1))))))                     
  (cont-frac-itr n d k 1))                                                      
                                                                                
(define tolerance 0.0001)                                                       
(define (close-enough? a b)                                                     
  (< (abs (- a b)) tolerance))                                                  
(define (eulernum-check n)                                                      
  (= (remainder (+ n 1) 3) 0))                                                  
                                                                                
(define (k-check)                                                               
  (define (k-check-itr begin count)                                             
    (let ((next (cont-frac (lambda (i) 1.0)                                     
                           (lambda (i) (if (eulernum-check i)                   
                                            (* 2 (/ (+ i 1) 3))                 
                                            1))                                 
                           count)))                                             
      (display (+ next 2))                                                      
      (display "\t")                                                            
      (display count)                                                           
      (newline)                                                                 
      (if (close-enough? begin next)                                            
          (+ next 2)                                                            
          (k-check-itr next (+ count 1)))))                                     
  (k-check-itr 1 2))                                                            
                                                                                
(print (k-check))

ほぼ問題1.37からD_k部分のlambdaを変更しただけ。
※結果はe-2なので表示する時に2を足している

結果

2.6666666666666665      2
2.75    3
2.7142857142857144      4
2.71875 5
2.717948717948718       6
2.7183098591549295      7
2.718279569892473       8
2.718279569892473

問題 1.39

tan(x)をk-term continued fractionで近似する問題

(define (cont-frac n d k)                                                       
  (define (cont-frac-itr n d k m)                                               
    (if (= m k)                                                                 
        (/ (n k) (d k))                                                         
        (/ (n m) (- (d m) (cont-frac-itr n d k (+ m 1))))))                     
  (cont-frac-itr n d k 1))                                                      
(define (tan-cf x k)                                                            
  (cont-frac (lambda (i) (if (= i 1)                                            
                             x                                                  
                             (* x x)))                                          
             (lambda (i) (- (* 2 i) 1))                                         
             k))                                                                
                                                                                
(print (tan-cf (/ 3.14159265 4) 100))

結果

0.9999999982051034

tan(pi/4) = 1だからOK。