algorithmmathschemesicpcontinued-fractions

Why the bleep isn't my continued fraction approximating properly?


Reading through more SICP and I'm stuck on exercise 1.3.8. My code works properly for approximating 1/phi, but doesn't work for approximating e - 2.

(define (cont-frac n d k)
  (define (frac n d k)
        (if (= k 0)
            1.0
            (+ (d k) (/ (n (+ k 1)) (frac n d (- k 1))))))
    (/ (n 1) (frac n d k)))

(define (eulers-e-2)
  (cont-frac (lambda (i) 1.0) 
             (lambda (i)
               (if (= (remainder (+ i 1) 3) 0)
                   (* 2.0 (/ (+ i 1) 3))
                   1.0))
             100))

(define (1-over-phi)
  (cont-frac (lambda (i) 1.0)
             (lambda (i) 1.0)
             100))

Instead of getting .7 blah blah blah for e-2, I'm getting .5 blah blah something. I can't figure out why. I'm pretty sure I have "d" defined properly in the "eulers-e-2" function.

Edit: Thanks guys, I was calculating it backwards. Here's the fixed code.

(define (cont-frac n d k)
  (define (frac n d i)
        (if (= k i)
            (d i)
            (+ (d i) (/ (n (+ i 1)) (frac n d (+ i 1))))))
    (/ (n 1) (frac n d 1)))

Solution

  • You seem to be calculating the following:

    N1/(D100 + (N101/ D99 + N100/(D98 + N99/(..))))
    

    Instead of

    N1/(D1 + N2/(D2 + ...))
    

    Since N and D are the same (all 1s) for 1/phi, you get the right answer there.