Exercise1-36 <---> Exercise1-38

Exercise 1.37

a. An infinite continued fraction is an expression of the form

As an example, one can show that the infinite continued fraction expansion with the N_i and the D_i all equal to 1 produces 1/, where is the golden ratio (described in section 1.2.2). One way to approximate an infinite continued fraction is to truncate the expansion after a given number of terms. Such a truncation -- a so-called k-term finite continued fraction -- has the form:

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 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?

b. If your cont-frac procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.

Ru: Русский текст упражнения

Scheme solution:

;; 'a' section
(define (cont-frac-rec n d k)
  (define (cont-rec-rev curr)
    (/ (n curr)
       (+ (d curr)
          (if (< curr k)
              (cont-rec-rev (+ curr 1))
              0))))
  (cont-rec-rev 1))

;; 'b' section
(define (cont-frac-iter n d k)
  (define (iter sum k)
    (if (= k 0)
        sum
        (iter (/ (n k)
                 (+ (d k) sum))
              (- k 1))))
  (iter 0 k))

Haskell solution:

cont'frac'rec _ _ 0 = 0
cont'frac'rec n d k = n 1 / (d 1 + cont'frac'rec (n.(+1)) (d.(+1)) (k-1))

cont'frac'iter n d k = rk where
  rk        = foldl rprev (n k / d k) $ enumFromThenTo (k-1) (k-2) 1
  rprev r j = n j * recip (r + d j)

limit :: Int -> Float -> (Int -> Float) -> (Int, Float)
limit zero prec f = (n, f n) where 
    n = l (f zero) zero
    l x i | abs (x - y) < prec = i
          | otherwise          = l y j
          where y = f j
                j = i + 1

-- The approximation gets the first 4 digits right at the 11th iteration:
-- *Main> limit 1 0.00005 (cont'frac'iter (const 1) (const 1))
-- (11,0.6180556)

Exercise1-36 <---> Exercise1-38

Comments

I think there is a slight bug in the recursive version. When curr = k, you are computing Dk. However, the general case computes Ni/(Di + something). In order to compute the right result, the "something" that the base case computes must be Nk/Dk. Changing the if statement like so should produce the correct result: (if (= curr k)     (/ (n curr) (d curr)) ; base case     (/ (n curr) (+ (d curr) (cont-rec-rev (+ curr 1)))))

Posted by sbdc at 2008-03-29 07:58:21 X

Yeah, I think so too! The series do converge to the gold ratio, but these are not the same series. I'll try to change the page.

Posted by AntonTayanovskyy at 2008-03-29 23:39:25

Add your comment Markup