SICP 2.1 exercises cont. 2

2.9

width(x) = \frac{upper(x) - lower(x)}{2}
width(x + y) = \frac{upper(x + y) - lower(x + y)}{2}
width(x + y) = \frac{upper(x) + upper(y) - lower(x) - lower(y)}{2}
width(x + y) = \frac{upper(x) - lower(x)}{2} + \frac{upper(x) - lower(x)}{2}
width(x + y) = width(x) + width(y)

2.10

(define (div-interval x y)
  (if (>= 0 (* (upper-bound y) (lower-bound y)))
      (error "undefined behavior: interval spans 0")
      (mul-interval x
                    (make-interval (/ 1.0 (upper-bound y))
                                   (/ 1.0 (lower-bound y))))))

I didn’t figure this answer out by myself, but this is by far the most elegant way I’ve seen.

2.11

(define (mul-interval-2 x y)
  (let ((ux (upper-bound x))
        (uy (upper-bound y))
        (lx (lower-bound x))
        (ly (lower-bound y)))
    (cond ((> lx 0)
           (cond ((> ly 0)
                  (make-interval (* lx ly) (* ux uy)))
                 ((< uy 0)
                  (make-interval (* ux ly) (* lx uy)))
                 (else
                  (make-interval (* ux ly) (* ux uy)))))
          (( ly 0)
                  (make-interval (* lx uy) (* ux ly)))
                 (( ly 0)
                  (make-interval (* lx uy) (* ux uy)))
                 ((< uy 0)
                  (make-interval (* ux ly) (* lx uy)))
                 (else
                  (make-interval (min (* lx uy) (* ux ly)) (max (* lx uy) (* ux ly)))))))))

This was so tedious. Maybe there’s a smarter way?

2.12

(define (make-center-percent c p)
  (make-center-width c (* c p)))

(define (percent x)
  (/ (width x) (center x)))

This one was pretty easy.

2.13

This question was unclear, so I looked around for an answer for this.

Given two intervals with the percentage tolerance representation, multiply them together to get the minimum interval of XY:

(X - p_x X) (Y - p_y Y) = XY - p_x XY - p_y XY + p_x p_y X Y \approx XY - (p_x + p_y)XY

similarly maximum

(X + p_x X) (Y + p_y Y) = XY + p_x XY + p_y XY + p_x p_y X Y \approx XY + (p_x + p_y)XY

because p_x p_y is negligible.

Therefore when multiplying two intervals with low percentage tolerances, simply add the percentage tolerances together.

2.14

Running it and showing it’s different is easy enough. We’re told that using a small tolerance is useful, so we do.

(par1 (make-center-percent 5 0.0001) (make-center-percent 6 0.0001))
(2.72645465453455 . 2.72809101819273)

(par2 (make-center-percent 5 0.0001) (make-center-percent 6 0.0001))
(2.727 . 2.72754545454545)

The values are close but different. Seems like it’s the tolerance that is causing the difference. We also see that the second case is more precise. The reason is that the first procedure does operations on four values – r1 and r2 are each used twice in the procedure, but each time it is used, the associated tolerance is introduced into the system. Therefore the values are different since in the second procedure, r1 and r2 are only introduced once.

2.15

The wording of this question made me doubt my answer to 2.14. But I turned out to be right.

2.16

As before, certain expressions may repeat values. Each time it is introduced, it brings a distorting tolerance value along with it.

I’m glad I looked this one up before even attempting it. Apparently it’s undergoing active research, so the question is essentially impossible.

Comments: 2.1 finished! Took me only 3 days, although I looked at other solutions more than usual. It’s really just practice using cons, car, and cdr as well as making abstraction barriers. That lambda stuff was amazing though.

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