SICP – Section 2.1.4   Leave a comment

I’ve been silent for the past couple days, but not without good reason :)

I decided to finish all my solutions to the interval arithmetic exercise
before posting, because I can share as much insight as I have gained, in one
hit. ;)

In this extended exercise, we are helping Alyssa P. Hacker
(note the pun :)  to develop an interval arithmetic system for
her fellow electrical engineering compatriots.

The answers to exercises 2.7 to 2.10 are fairly clear, so here they are:

Exercise 2.7

(define (make-interval a b) (cons a b))

(define (lower-bound i) (car i))
(define (upper-bound i) (cdr i))

Exercise 2.8

(define (sub-interval x y)
(make-interval (- (lower-bound x) (lower-bound y))
(- (upper-bound x) (upper-bound y))))

Exercise 2.9

Let’s add some intervals and note the relation between the width of the
operands and the width of the result.

(define a (make-center-width 5 1))
(define b (make-center-width 10 2))
(define x (mul-interval a b))
(width x) = 3

From this it is fairly obvious that the width of the result of addition can
be described like so:
w(x*y) = w(x)+w(y)

The inverse holds true of division:
w(x/y) = w(x)-w(y)

Hmm… anyone else see the relation to logarithms?

Exercise 2.10
This one is also fairly simple.

(define (zero-span? i)
(if (and (<= (lower-bound i) 0) (>= (upper-bound i) 0))

(define (div-interval x y)
(if (zero-span? y)
(error "Attempt to divide by an interval that spans 0")
(mul-interval x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y))))))

Exercise 2.11

To be honest, I didn’t get Ben’s cryptic comment. After reading
Eli Bendersky’s post on the topic I understood, but previously I had
gone off on a wrong tangent.

Regarding this, let me state my policy regarding my completion of these exercises. I firmly believe that cheating cheats the cheater, and while it is not necessarily cheating to check an answer to get hints, this is usually not necessary. There have been a few exercises where I have encountered a mindblock, but my advice to others is to go do something else, completely unrelated to computing or using your brain. Hop on your bike, go for a run or eat a pie, whatever works for you :) Usually when you get a mindblock it shows that you’ve been working your brain too long, too hard, and you just need to let it relax. This also happens a bit in programming, at least when you’re starting out, and in “How To Think Like A Computer Scientist” the author also suggests taking a break when you get frustrated, as this can be a source of unpleasant code and bugs.

I tend to read Eli’s posts after completing a section, because they are quite enlightening and informative. There is nothing quite like a veteran hackers view of the topic :)

This leads me to a shout out to Eli. Thanks for writing such detailed, interesting, and informative posts! I believe that, along with watching the lectures, doing the exercises and reading the book, your posts are a very complementary aid in understanding the material.

Exercise 2.12

(define (make-center-percent c p)
(make-interval (- c (* c p))
(+ c (* c p))))

(define (percent i)
(/ (- (upper-bound i)
(center i))
(center i)))

Again, this is fairly simple. The percent selector may have caused
some trouble, but it’s not too hard to figure out.

Exercise 2.13

;;Let's try:
(define a (make-center-percent 1 .1))
(define b (make-center-percent 1 .2))
(define x (* a b))
(percent x)

So we can indeed see that (percent x) ~= (percent a) + (percent b)
This follows from exercise 2.9, except here we see that the percentage
is only approximate.

Exercise 2.14

To show why, we will use:

(define A (make-center-percent 8 .01))
(define B (make-center-percent 9 .05))

We will process A/A by hand, in order to see what’s going on.

(mul-interval A (make-interval (/ 1 8.08) (/ 1 7.92)))
;;p1 = .980
;;p2 = 1
;;p3 = 1
;;p4 = 1.02

The result is: (make-interval .980 1.02)
Instead of (make-interval 1 1) which you might have expected.

Let’s also do (/ A B) as suggested

;;(mul-interval A (make-interval (/ 1 9.45) (/ 1 (8.55))))
;;p1 = .838
;;p2 = .926
;;p3 = .855
;;p4 = .945

So the result is: (make-interval .838 .945) instead of the more accurate
(make-interval .855 .926)

Here’s my explanation.

Interval A/A is not an interval spanning 1 <-> 1 as we would expect in normal arithmetic, but an interval spanning .980 <-> 1.02. The width of this interval is a factor of the initial uncertainty .01, where the new uncertainty is .04. Interval A/B is also not the .855 <-> .926 that we might expect, but instead .838 <-> .945. We can see from these examples that arithmetic operations increase the innacuracy/uncertainty of the answer. The error in the answer is therefore directly related to the uncertainty in the intervals given.

Exercise 2.15

She is correct. As stated above, the amount of error in the answer is directly related to the uncertainty in the intervals given. Because there are more intervals in par1, there is a higher error in the answer. That is why par2 is a better method.

Reading Eli’s solutions to this extended exercise also gives a different view on the matter, he talks about it in terms of the fact that interval arithmetic is not a one-to-one mapping of simple numerical arithmetic.


Posted 27/03/2010 by Emmanuel Jacyna in Code, Scheme, SICP

Tagged with , , ,

Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: