Today's Meeting Log | 2.11-2.16

Skip to first unread message

Chris Conley

Mar 15, 2009, 8:45:23 PM3/15/09
to Hacker News Reads SICP
[8:04pm] aamar: start time?
[8:05pm] chrisconley: yeah, anybody else around?
[8:06pm] nicou: here I am
[8:06pm] nicou: we are off DST today so I almost missed it by one hour
[8:07pm] aamar: ok, let's start...
[8:07pm] nicou: I'ma get my notes
[8:07pm] aamar: First, should we do any review of 2.1 through 2.10 ?
[8:07pm] aamar: We had a smaller group last week.
[8:09pm] aamar: Okay, seems like no questions on 2.1 through 2.10
[8:09pm] nicou: yeah, let's move on
[8:09pm] aamar: 2.11
[8:09pm] chrisconley: yeah i'm ok to move on
[8:09pm] chrisconley: might even be smaller still this week
[8:10pm] aamar: -- my answer to 2.11
[8:10pm] nicou: yes
[8:10pm] nicou: so
[8:10pm] chrisconley: i still didn't finish 11; just started on 12 and
read your notes from last week
[8:11pm] nicou: in 2.11, we break into 16 cases, 7 of which are
invalid (lower bound higher than upper bound),
[8:11pm] aamar: okay, last week's log also had inimino's answer to
[8:12pm] chrisconley: yeah
[8:13pm] aamar: Seems like that might be one way to do it
[8:13pm] nicou: aamar, I think yours is fine
[8:13pm] aamar: 2.12 ?
[8:13pm] aamar: Exercise 2.12. Define a constructor make-center-
percent that takes a center and a percentage tolerance and produces
the desired interval. You must also define a selector percent that
produces the percentage tolerance for a given interval. The center
selector is the same as the one shown above.
[8:13pm] chrisconley:
[8:15pm] nicou: chrisconley, I think p must be passed to the procedure
as a percentage, not a ratio, so you'll have to divide p by 100,
everything else is fine, I think
[8:15pm] nicou: yes
[8:15pm] aamar: -- my 2.12
[8:15pm] chrisconley: ahh yeah, i was passing in .05, .10, etc
[8:16pm] aamar: okay, basically the same though
[8:16pm] chrisconley: yeah looks good aamar
[8:16pm] aamar: Exercise 2.13. Show that under the assumption of
small percentage tolerances there is a simple formula for the
approximate percentage tolerance of the product of two intervals in
terms of the tolerances of the factors. You may simplify the problem
by assuming that all numbers are positive.
[8:16pm] chrisconley:
[8:17pm] aamar: -- my 2.13
[8:17pm] X-Scale left the chat room.
[8:17pm] chrisconley: aamar: thanks for posting the questions; helpful
[8:17pm] chrisconley: my explanation is at the bottom of the file
[8:18pm] nicou: chrisconley, agree. I have the same solution as you
[8:19pm] aamar: Okay, my algebra is a little different but I think I'm
dropping the same term.
[8:20pm] aamar: And I get the same result
[8:20pm] chrisconley: cool
[8:20pm] aamar: Lem complains that Alyssa's program gives different
answers for the two ways of computing. This is a serious complaint.
Exercise 2.14. Demonstrate that Lem is right. Investigate the
behavior of the system on a variety of arithmetic expressions. Make
some intervals A and B, and use them in computing the expressions A/A
and A/B. You will get the most insight by using intervals whose width
is a small percentage of the center v
[8:21pm] chrisconley:
[8:21pm] aamar:
[8:22pm] ews_ joined the chat room.
[8:22pm] chrisconley: did you guys draw any conclusions from
[8:22pm] nicou: so it's because when there are more operations, the
uncertainty percentage grows
[8:22pm] nicou: error tolerance
[8:23pm] chrisconley: i just got as far as, yeah he's right
[8:23pm] nicou: we could derive some formulas for each operation, I
remember some from chemistry
[8:23pm] nicou: but that's the general idea
[8:23pm] chrisconley: ha, cool
[8:23pm] aamar: I did a little more math and got -- I think -- the
[8:24pm] Edico left the chat room. ("Leaving")
[8:24pm] aamar: they're at the end of my answer above
[8:24pm] aamar: but yes, basically when you do more operations you end
up with larger intervals
[8:24pm] chrisconley: right
[8:24pm] aamar: 2.15 ?
[8:24pm] chrisconley: yeah
[8:24pm] mariorz: hey guys im late
[8:24pm] nicou: I see, yeah 2.15
[8:24pm] aamar: Exercise 2.15. Eva Lu Ator, another user, has also
noticed the different intervals computed by different but
algebraically equivalent expressions. She says that a formula to
compute with intervals using Alyssa's system will produce tighter
error bounds if it can be written in such a form that no variable that
represents an uncertain number is repeated. Thus, she says, par2 is a
``better'' program for parallel resistances tha
[8:25pm] nicou: exactly, that's basically a corollary of the above
[8:25pm] chrisconley:
[8:25pm] chrisconley: yeah
[8:25pm] aamar:
[8:26pm] aamar: Okay, we say the same thing.
[8:26pm] nicou: yes
[8:26pm] mariorz:
[8:26pm] chrisconley: hey mariorz!
[8:26pm] nicou: and 2.16 (we are going quite fast here) asks for a
solution to this problem
[8:26pm] • mariorz waves
[8:26pm] aamar: I think the underlying idea is that each R really has
one true value
[8:26pm] aamar: so R - R really should = (0 0)
[8:26pm] chrisconley: did anybody get it?
[8:27pm] nicou: exactly
[8:27pm] aamar: I have an answer
[8:27pm] aamar:
[8:27pm] nicou: my solution for 2.16: the system should know when two
quantities are the same, so it can "cancel them out" algebraically,
and then operate on a simpler expression
[8:28pm] aamar: Yes, but the only way I could think of doing that is
to have the arithmetic you want to do passed in as a function
[8:28pm] nicou: like, when you have two intervals that actually
represent the same thing (not that are only equal), and you subtract
them, for example, you would get 0, not just center 0 and twice the
tolerance percentage
[8:29pm] aamar: And then each of the operands are passed in after
[8:29pm] chrisconley: yeah my idea was to change expressions so that
only one interval instance remained; but i had no idea how to
accomplish that
[8:29pm] nicou: yes, exactly
[8:29pm] nicou: because the system should know when two quantities
represent the same concept
[8:29pm] aamar: so instead of doing (add_interval a b), the new
interface does: (interval-algebra (lambda (x y) (+ x y)) a b)
[8:30pm] nicou: like I measure the height of a table twice, I get two
intervals, that are equal, but also represent the same concept, so
it's safe to assume they are *completely* equal, and cancel them out
in an algebraic expression
[8:30pm] aamar: yes, nicou -- how can the system determine when the
intervals are the same?
[8:30pm] aamar: There's probably a way, but it's not straightforward.
[8:31pm] aamar: There needs to be a way for the system to say this
interval and that interval represent the same underlying number.
[8:31pm] aamar: One more solution here (inimino?)
[8:31pm] nicou: aamar, it can't know by itself, chances are that maybe
using units like cm, kg, etc, allows for possible assumptions, but the
only way to know is to tell it, and you do that by binding the numbers
to variables, which is the easiest solution I think
[8:32pm] aamar: nicou: yes, ok
[8:32pm] aamar: By the way, doing that introduces one other weird
[8:32pm] nicou: so basically: bind the intervals to variables,
simplify the algebraic expression with a algebraic parser, recalculate
the new expression with the original values
[8:32pm] nicou: aamar, what do you mean?
[8:33pm] chrisconley: aamar: nice solution, pretty clever
[8:33pm] aamar: Oh, well, instead of using a true algebraic parser,
I'm just taking in a lambda which represents the interval-algebra you
want to accomplish.
[8:33pm] aamar: And then I'm running it against the lower and upper
bounds of each of the inputs.
[8:35pm] aamar: As inimino says, since addition, subtraction,
multiplication, and division are all monotonic (if nothing ever spans
zero), you can be confident that if you run the algebra against all
combinations of the bounds, you get the correct final bounds.
[8:35pm] aamar: However, I also tried to handle the case of (5 - x)^2
[8:35pm] nicou: exactly, that is, if nothing spans zero
[8:35pm] aamar: Let's say x is (4 6), then you'll get an intermediate
result which does span zero.
[8:36pm] aamar: Then you get the wrong answer -- you get (1, 1)
instead of the correct answer which I think should be (0 1)
[8:36pm] nicou: aamar, I see.
[8:36pm] aamar: I.e. if x's "true value" is 5, you'd want the result
of (5 - x)^2 to be zero.
[8:37pm] nicou: so the problem is the intervals that do span zero, and
computations that involve this type of intervals as intermediate
values will result in erroneous solutions
[8:37pm] aamar: I initially thought there might be some way to
calculate derivatives and find zeros, since there were derivatives
earlier in the chapter, but that was too difficult.
[8:37pm] aamar: So my approximate solution is just to iterate through
the intervals and compute the algebra for each point.
[8:38pm] aamar: Any way, that's the entire explanation.
[8:38pm] aamar: Okay, anything more to say?
[8:38pm] nicou: I think we do develop an arithmetic system somewhere
in the book, so we could use and extend and specify that for the
algebraic manipulation of intervals, bind before, simplify
expressions, and replace again, thus repeating each variable the least
possible number of times and reducing the error tolerance to the
minimum, but it's of course hard to develop the arithmetic package
[8:39pm] chrisconley: I'm good, thanks for the explanation; should we
set our sites on the next meeting?
[8:39pm] nicou: mmm
[8:39pm] aamar: nicou: okay, makes sense
[8:39pm] aamar: Yes
[8:40pm] chrisconley: aamar: you said 2.2 was pretty long?
[8:40pm] aamar: One thing I noticed is that 2.2 is very long
[8:40pm] aamar: Yes, I did a little of it.
[8:40pm] nicou: up to 2.32?
[8:40pm] aamar: yes
[8:40pm] nicou: it's kind of easy, just some examples of map,
reversing a tree, functions with optional arguments
[8:40pm] chrisconley: we could always shoot for something; then check
in in a week to see how's everybody's doing
[8:41pm] chrisconley: cool, 2.32 sounds good to me
[8:41pm] nicou: after 2.32, streams and folding come in
[8:41pm] aamar: should we do more than that?
[8:41pm] nicou: I think we'll be fine
[8:41pm] aamar: ok
[8:41pm] aamar: How about next meeting in 2 weeks?
[8:41pm] chrisconley: that's fine with me
[8:42pm] nicou: so next Sunday's a "calm" meeting
[8:42pm] mariorz: cool
[8:42pm] mariorz: il maki it next sunday but then ill miss the
following two, ill be keeping up though
[8:42pm] chrisconley: sounds good
[8:43pm] mariorz: s/maki/make/
Reply all
Reply to author
0 new messages