July « 2009 « Dan's Thoughts

11Jul/090

Exercise 1.41 of SICP

Exercise 1.41: Define a procedure double that takes a procedure of one argument as argument and returns a procedure that applies the original procedure twice. For example, if inc is a procedure that adds 1 to its argument, then (double inc) should be a procedure that adds 2. What value is returned by

(((double (double double)) inc) 5)

(define (double f)
  (lambda (x)
    (f (f x))))
 
(define (inc x)
  (+ x 1))

> (((double (double double)) inc) 5)
21
At first glance it's possible to assume the answer should be 8+5=13 instead of 21 (16+5).
13 is achieved through:
> ((double (double (double inc))) 5)
13

In order to understand what is happening here it is better to start simple and work up to the complex example:
Again, which ever function D receives it will apply it twice.
$f(x) = x+1$
$D(f) = (f \circ f)(x) = f(f(x)$
$D(D(f)) = (f \circ f) \circ (f \circ f)(x)$
$D(D(D(f))) = \left( \left( (f \circ f) \circ (f \circ f) \right) \circ \left( (f \circ f) \circ (f \circ f) \right) \right)(x) = f(f(f(f(x)))) \circ f(f(f(f(x)))) = f(f(f(f(f(f(f(f(x))))))))$
$f(f(f(f(f(f(f(f(5)))))))) = 13$

Clearly it's pain to trace through all those function compositions but if need be it can be done to verify that indeed f is applied 8 times to 5 in order to give the result of 13.
It's time now to go to (((double (double double)) inc) 5). The main difference from the previous statement is the bolded part.
$f(x) = x+1$
$D(f) = (f \circ f)(x) = f(f(x))$
$(D(D(f)) = D^2(f) = D(D(f)) = (f \circ f) \circ (f \circ f)(x)$
$D(D(D(f))) = D^2(f) \circ D^2(f) = D(D(f)) \circ D(D(f)) = D(D(D(D(f))))(x)$

So (double double) in fact returns a composition of (double (double f)) which in turn get's composed with itself to form (double (double (double (double f)))).

Filed under: lisp, SICP No Comments

10Jul/090

Exercise 1.40 of SICP

Exercise 1.40: Define a procedure cubic that can be used together with the newtons-method procedure in expressions of the form

 (newtons-method (cubic a b c) 1)

to approximate zeros of the cubic x³ + ax² + bx + c.

(define (cubic a b c)
  (lambda (x)
    (+
      (* x x x)
      (* a x x)
      (* b x)
      c)))
 
(define dx 0.00001)
(define (deriv g)
  (lambda (x)
    (/ (- (g (+ x dx)) (g x))
       dx)))
 
(define (newton-transform g)
  (lambda (x)
    (- x
       (/ (g x) ((deriv g) x)))))
 
(define (newtons-method g guess)
  (fixed-point (newton-transform g) guess))
 
(define (fixed-point f first-guess)
  (define tolerance 0.00001)
  (define (close-enough? v1 v2)
    (&lt; (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

> (newtons-method (cubic -2 -9 18) -2)
2.000000000000876
> (newtons-method (cubic 8 3 6) 1)
-7.711875650348891

Note that Newton's Method only finds a root not all roots or even all real roots.

Filed under: lisp, math, SICP No Comments

9Jul/090

Exercise 1.39 of SICP

Exercise 1.39: A continued fraction representation of the tangent function was published in 1770 by the German mathematician J.H. Lambert:

$\tan x = \cfrac{x}{1-\cfrac{x^2}{3-\cfrac{x^2}{5-{\ddots\,}}}}$

where x is in radians. Define a procedure (tan-cf x k) that computes an approximation to the tangent function based on Lambert's formula. K specifies the number of terms to compute, as in exercise 1.37.

(define (tan-cf x k)
  (define (n i)
    (if (= i 1)
      x
      (* x x)))
  (define (d i)
    (- (* 2 i) 1))
  (define (cf i)
    (if (= i (+ k 1))
      0
      (/ (n i) 
         (- (d i) (cf (+ i 1))))))
  (if (not (> k 0))
    0
    (cf 1)))

> (tan-cf (sqrt 2) 12)
6.334119167042199
$\tan \sqrt 2 = 6.3341191670421915540568332642277$

Filed under: lisp, math, SICP No Comments

8Jul/090

Exercise 1.38 of SICP

Exercise 1.38: 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 N_i are all 1, and the D_i are successively 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, .... Write a program that uses your cont-frac procedure from exercise 1.37 to approximate e, based on Euler's expansion.

Since all the continued fraction works is done from the previous exercise the trickiest part is defining a function for the D_i's. Procedure d should always return 1 except for the special indices. For me it was key to notice that every 3i-1 index, where is is i=1...n, was the even number I care about. And that even number was of the form 2i.

(define n (lambda (i) 1.0))
(define (d i)
  (if (= 0 (remainder (+ i 1) 3))
    (* 2 (/ (+ i 1) 3))
    1))
 
(define (cont-frac n d k)
  (define (cf i)
    (if (= i (+ k 1))
      0
      (/ (n i) 
         (+ (d i) (cf (+ i 1))))))
  (if (not (> k 0))
    0
    (cf 1)))
 
(define (cont-frac-iter n d k)
  (define (iter k result)
    (if (= k 0)
      result
      (iter (- k 1) (/ (n k) (+ (d k) result)))))
  (iter k 0))

> (cont-frac n d 11)
.7182818352059925
> (cont-frac-iter n d 11)
.7182818352059925
$e-2 = 0.7182818284590452353$
$\epsilon = |e-2-0.7182818352059925| = 0.0000000067469472647$

Filed under: lisp, math, SICP No Comments

7Jul/090

Exercise 1.37 of SICP

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

$f = \cfrac{N_1}{D_1 + \cfrac{N_2}{D_2 + \cfrac{N_3}{D_3 +\cdots}}}$

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 $\frac{1}{\phi}$ , where $\phi$ 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

$f = \cfrac{N_1}{D_1 + \cfrac{N_2}{{\ddots\,} + \cfrac{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 $\frac{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?

(define (cont-frac n d k)
  (define (cf i)
    (if (= i (+ k 1))
      0
      (/ (n i) 
         (+ (d i) (cf (+ i 1))))))
  (if (not (> k 0))
    0
    (cf 1)))

> (cont-frac (lambda (i) 1.0)
             (lambda (i) 1.0)
             11)

.6180555555555556
It takes 11 iterations to get to 4 decimal places within the reciprocal of golden ratio.
$\frac{1}{\phi} = 0.618033988$
It's amusing that the LaTeX looks almost identical to the above definition in scheme:

\cfrac{N_1}{D_1 + \cfrac{N_2}{D_2 + \cfrac{N_3}{D_3 +\cdots}}}

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.

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

> (cont-frac-iter (lambda (i) 1.0)
                  (lambda (i) 1.0)
                  11)

.6180555555555556

Filed under: lisp, math, SICP No Comments

6Jul/090

Exercise 1.36 of SICP

Exercise 1.36: Modify fixed-point so that it prints the sequence of approximations it generates, using the newline and display primitives shown in exercise 1.22. Then find a solution to $x^x = 1000$ by finding a fixed point of $x \mapsto \frac{\log 1000}{\log x}$ . (Use Scheme's primitive log procedure, which computes natural logarithms.) Compare the number of steps this takes with and without average damping. (Note that you cannot start fixed-point with a guess of 1, as this would cause division by log(1) = 0.)

(define (average a b) (/ (+ a b) 2))
(define tolerance 0.00001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (display guess)
    (newline)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

> (fixed-point (lambda (x) (/ (log 1000) (log x))) 2)

2
9.965784284662087
3.004472209841214
6.279195757507157
3.759850702401539
5.215843784925895
4.182207192401397
4.8277650983445906
4.387593384662677
4.671250085763899
4.481403616895052
4.6053657460929
4.5230849678718865
4.577114682047341
4.541382480151454
4.564903245230833
4.549372679303342
4.559606491913287
4.552853875788271
4.557305529748263
4.554369064436181
4.556305311532999
4.555028263573554
4.555870396702851
4.555315001192079
4.5556812635433275
4.555439715736846
4.555599009998291
4.555493957531389
4.555563237292884
4.555517548417651
4.555547679306398
4.555527808516254
4.555540912917957
4.555532270803653

$4.555532270803653^{4.555532270803653} = 999.9913579312362$
35 Steps.

Average damping: $x = \frac{\log 1000}{\log x} = \frac{1}{2}\left( \frac{\log 1000}{\log x} + x\right)$
> (fixed-point (lambda (x) (average (/ (log 1000) (log x)) x)) 2)

2
5.9828921423310435
4.922168721308343
4.628224318195455
4.568346513136242
4.5577305909237005
4.555909809045131
4.555599411610624
4.5555465521473675
4.555537551999825

$4.555537551999825^{4.555537551999825} = 1000.0046472054871$
Steps 10

Filed under: lisp, math, SICP No Comments

5Jul/090

Exercise 1.35 of SICP

Exercise 1.35: Show that the golden ratio $\phi$ (section 1.2.2) is a fixed point of the transformation $x\mapsto 1 + \frac{1}{x}$ , and use this fact to compute $\phi$ by means of the fixed-point procedure.

(define tolerance 0.00001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

> (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)
1.6180327868852458
Actual value of golden ratio: 1.61803399
Tolerance: 0.0001
$\epsilon = \left|1.61803399-1.6180327868852458\right| = .0000012031147542 < 0.0001$
Clearly $\epsilon$ is in the defined error tolerance.

Filed under: lisp, math, SICP No Comments

4Jul/090

Exercise 1.34 of SICP

Exercise 1.34: Suppose we define the procedure

(define (f g)
  (g 2))

Then we have

(f square)
4

(f (lambda (z) (* z (+ z 1))))
6

What happens if we (perversely) ask the interpreter to evaluate the combination (f f)? Explain.

(f f)
 *** ERROR -- Operator is not a PROCEDURE

The reasons this happens if clearer once we trace the evaluation steps:

(f f)
(f 2)
(2 2)

Since the leftmost side is not an operator but a number the interpreter doesn't know what to do and hence gives the error above.

Filed under: lisp, SICP No Comments

3Jul/090

Exercise 1.33 of SICP

Exercise 1.33: You can obtain an even more general version of accumulate (exercise 1.32) by introducing the notion of a filter on the terms to be combined. That is, combine only those terms derived from values in the range that satisfy a specified condition. The resulting filtered-accumulate abstraction takes the same arguments as accumulate, together with an additional predicate of one argument that specifies the filter. Write filtered-accumulate as a procedure. Show how to express the following using filtered-accumulate:

a. the sum of the squares of the prime numbers in the interval a to b (assuming that you have a prime? predicate already written)

(define (smallest-divisor n)
  (find-divisor n 2))
(define (find-divisor n test-divisor)
  (define (square x) (* x x))
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
  (= (remainder b a) 0))
 
(define (prime? n)
  (= n (smallest-divisor n)))
 
(define (filtered-accumulator pred? combiner null-value term a next b)
  (cond ((> a b) null-value)
        ((pred? a)
         (combiner (term a) 
                   (filtered-accumulator pred? combiner null-value term (next a) next b)))
        (else
          (filtered-accumulator pred? combiner null-value term (next a) next b))))
 
(define (sum-of-prime-squares a b)
  (define (square x) (* x x))
  (define (next x) (+ 1 x))
  (filtered-accumulator prime? + 0 square a next b))

> (sum-of-prime-squares 2 10)
87
$2^2+3^2+5^2+7^2 = 4+9+25+49=89$
> (sum-of-prime-squares 2 20)
1027

b. the product of all the positive integers less than n that are relatively prime to n (i.e., all positive integers i < n such that GCD(i,n) = 1).

(define (filtered-accumulator pred? combiner null-value term a next b)
  (cond ((> a b) null-value)
        ((pred? a)
         (combiner (term a) 
                   (filtered-accumulator pred? combiner null-value term (next a) next b)))
        (else
          (filtered-accumulator pred? combiner null-value term (next a) next b))))
 
(define (gcd a b)
  (if (= b 0)
    a
    (gcd b (remainder a b))))
 
(define (product-of-coprimes i n)
  (define (coprime? a)
    (= (gcd n a) 1))
  (define (identity x) x)
  (define (next x) (+ 1 x))
  (filtered-accumulator coprime? * 1 identity i next n))

> (product-of-coprimes 2 10)
189
$3\cdot7\cdot9=189$

Notice how coprime? binds n to itself.

Filed under: lisp, SICP No Comments

« Newer Entries

Dan's Thoughts Thinking somewhat carefully

Exercise 1.41 of SICP

Exercise 1.40 of SICP

Exercise 1.39 of SICP

Exercise 1.38 of SICP

Exercise 1.37 of SICP

Exercise 1.36 of SICP

Exercise 1.35 of SICP

Exercise 1.34 of SICP

Exercise 1.33 of SICP

Pages

Categories

Blogroll

Archive

Meta