SICP 1.3 exercises cont. 3

The rest of the exercises in this chapter turned out to be pretty simple, so I decided to finish them all in one go.

1.38

(define (euler-expansion k)
  (define (n i)
    1.0)
  (define (d i)
    (if (= 0 (remainder (+ i 1) 3))
        (* 2 (/ (+ i 1) 3))
        1))
  (cont-frac n d k))


1.39

(define (tan-cf x k)
  (define (n i)
    (if (= i 1)
        x
      (- (square x))))
  (define (d i)
    (- (* 2 i) 1))
  (cont-frac n d k))

Comments: Both of these exercises were straightforward implementations of N and D. I had a bit of trouble because my answer to 1.37 turned out to have an off by one error.

1.40

(define (cubic a b c)
  (lambda (x)
    (+ (cube x) (* a (square x)) (* b x) c)))

1.41

(define (double f)
  (lambda (x)
    (f (f x))))

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

1.42

(define (compose f g)
  (lambda (x)
    (f (g x))))

((compose square inc) 6)
49

Comments: These simple exercises are probably for easing people into the idea of procedures returning procedures.

1.43

(define (repeated f n)
  (if (= n 1)
      f
      (compose f (repeated f (- n 1)))))

1.44

(define (smooth f)
  (lambda (x)
    (/ (+ (f (- x dx)) (f x) (f (+ x dx))) 3)))

(define (n-smooth f n)
  ((repeated smooth n) f))

1.45

To make things easier I implemented an experiment procedure which takes an argument r for the number of times average-damp is repeated.

(define (nr-root x n r)
  (fixed-point ((repeated average-damp r) (lambda (y) (/ x (expt y (- n 1)))))
               1.0))

Running it showed that every time average-damp is applied, n can be twice as big for an answer to be found. Then simply replace r in the above procedure to be log2 of n.

(define (n-root x n)
  (fixed-point ((repeated average-damp (floor (/ (log n) (log 2)))) (lambda (y) (/ x (expt y (- n 1)))))
               1.0))

Perhaps it might have been better to define log2 as a separate procedure. In any case, this works.

(n-root 8 100)
1.0210089104768

1.46

(define (iterative-improve good-enough? improve)
  (define (improve-function guess)
    (let ((next (improve guess)))
     (if (good-enough? guess next)
         next
       (improve-function next))))
  improve-function)

(define (sqrt x)
  (define (good-enough? guess next)
    (< (abs (- x (square guess))) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  ((iterative-improve good-enough? improve) x))

(define (fixed-point-2 f first-guess)
  (define (good-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  ((iterative-improve good-enough? f) first-guess))

Comments: Much of the work is already done for this exercise, the trick is to find the right example to model after. Since the good-enough? procedure inside fixed-point requires two arguments, the solution is to copy the logic from the fixed-point example in the chapter, namely put the try procedure into iterative-improve. This exercise took more thinking than the previous ones by far, although still relatively straight forward.

Finished section 1.3 and therefore the entirety of chapter 1! These exercises really helped me get familiar with writing recursive and iterative procedures as well as become comfortable with lisp in general. It took me almost exactly 3 weeks, with most of my time spent on section 1.2. A nice side benefit was the LaTeX I learned in order to type out mathematical proofs on this blog.

Next step is Chapter 2. Let’s see how it goes.

Advertisements


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s