SICP-2nd-Edition-Exercise-1.38

From Boozled

Jump to: navigation, search

Contents

Exercise 1.38 From SICP

Details from SICP are here

In 1737, the Swiss mathematician Leonhard Euler published a memoir De Fractionibus Continuis, which included a continued fraction expansion for e − 2, where e is the base of the natural logarithms. In this fraction, the Ni are all 1, and the Di are successively 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, \ldots. Write a program that uses your cont-frac procedure from exercise 1.37 to approximate e, based on Euler's expansion.

Attempt

I immediately jumped at the following attempt for d 

  1. (define (d k) 
  2.   (define (seq-gen k i t2 t3 t4)
  3.     ;(display "i=")  (display i)   (newline)
  4.     (if (< k 1)
  5.         i
  6.         (seq-gen (- k 1) t2 t3 t4 (if(= t2 1) 1 (+ t2 2)))))
  7.   (seq-gen k 1 2 1 1))

Or we could use 3 variables to achieve the same thing. 

  1. (define (d k) 
  2.   (define (seq-gen k i t1 t2)
  3.     ;(display "i=")  (display i)   (display " t1=")  (display t1)  (display " t2=")  (display t2)   (newline)
  4.     (if (< k 1)
  5.         i
  6.         (seq-gen (- k 1) t1 t2 (if(= i 1) 1 (+ i 2)))))
  7.   (seq-gen k 1 2 1))

This is a naive attempt because I spotted a simple pattern and ran with it. The above method is very inefficient though for large i. For small i it may be fast enough.

If we are unable to find an algorithm to calculate Di in closed form on every call to d we would need to use a method that stores state between calls or we would have problems with performance. If we calculated it each time from the start ie 1,2,1,1... (as the above methods do) we have n * (n + 1) / 2 operations to perform per call. We could use memoization to speed this up if each calculation is expensive.

So we need to find a closed form to calculate Di. Our sequence has a period of 3, (thats why we could use three variables in the second method above), so this gives us some ideas of things to try.

Di 1 2 1 1 4 1 1 6 1 1 8 1 1 10 1 1 12 1 1 14 1
i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
i\,\bmod\,3 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0

In the above table we can see a pattern. If i\,\bmod\,3 \in (1, 0) then i = 1. This rule takes care of \frac{2i}{3} numbers so for performance it should be our first check. This leaves us with the following numbers to work on.

Di 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40
i 2 5 8 11 14 17 20 23 26 29 32 35 38 41 44 47 50 53 56 59
i + 1 3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60
\frac{i+1}{3} 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
\frac{2\left(i+1\right)}{3} 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40

This gives us the complete sequence. Beware, \frac{2\left(i+1\right)}{3} does not work for i = 1 and this is another reason why we need to perform the i\,\bmod\,3 test first.

Scheme

  1. (define (cont-frac n d k)
  2.   (define (iter k res)
  3.     ;(display "k=")  (display k)   (newline)
  4.     ;(display "res=")(display res) (newline)
  5.     (let ((res (+  (/ (n k) (+ res (d k))))))
  6.       (if (= k 1)
  7.       res
  8.       (iter (- k 1) res)))) 
  9.   (iter k 1))
  10.  
  11. (define (d k) 
  12.   (define (seq-gen k i t1 t2)
  13.     ;(display "i=")  (display i)   (display " t1=")  (display t1)  (display " t2=")  (display t2)   (newline)
  14.     (if (< k 1)
  15.         i
  16.         (seq-gen (- k 1) t1 t2 (if(= i 1) 1 (+ i 2)))))
  17.   (seq-gen k 1 2 1))
  18.  
  19. (define (d2 k) 
  20.   (let ((r (remainder k 3)))
  21.     (if (or (= r 0) (= r 1))
  22.         1
  23.         (/ (* 2 (+ k 1)) 3))))
  24.  
  25. (define k 900)
  26. (display (+ 2 (cont-frac (lambda (x) 1.0) d2 k)))
  27. ;(display (cont-frac (lambda (x) 1.0) (lambda (x) 1.0) k))
  28.  
  29. ; The following shows some things I tried to see if I could spot patterns
  30. ;k   i t u
  31. ;1  (1 2 1)
  32. ;2  (2 1 1)
  33. ;3  (1 1 4)
  34. ;4  (1 4 1)
  35. ;5  (4 1 1)
  36. ;5  (1 1 6)
  37. ;6  (1 6 1)
  38. ;6  (6 1 1)
  39.  
  40. ;           1
  41. ;          2 1
  42. ;         1 4 1
  43. ;        1 6 1  1
  44. ;      8  1 1 10 1
  45. ;     1 12 1 1 14 1
  46. ;    1 16 1 1 18 1 1
  47. ;   20 1 1 22 1 1 24 1
  48. ;  1 26 1 1 28 1 1 30 1
  49. ; 1 32 1 1 34 1 1 36 1 1 
  50. ;38

Parent Course

6.001_Structure_and_Interpretation_of_Computer_Programs

Further Reading

Retrieved from "http://www.boozled.org/wiki/index.php/SICP-2nd-Edition-Exercise-1.38"
Personal tools