3 views

Skip to first unread message

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: http://mibbit.com/pb/tPGuo8 -- 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

2.11

[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:

http://github.com/chrisconley/sicp-exercises/blob/e46bbaf96b12c4b86bd203d0c229c5a66498f178/chapter2/ex2-12.ss

[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: http://mibbit.com/pb/tCDkEf -- 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:

http://github.com/chrisconley/sicp-exercises/blob/e46bbaf96b12c4b86bd203d0c229c5a66498f178/chapter2/ex2-13.ss

[8:17pm] aamar: http://mibbit.com/pb/XzMyuJ -- 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:

http://github.com/chrisconley/sicp-exercises/blob/e46bbaf96b12c4b86bd203d0c229c5a66498f178/chapter2/ex2-14.ss

[8:21pm] aamar: http://mibbit.com/pb/ub4Ttt

[8:22pm] ews_ joined the chat room.

[8:22pm] chrisconley: did you guys draw any conclusions from

inestigating?

[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

formulas

[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:

http://github.com/chrisconley/sicp-exercises/blob/e46bbaf96b12c4b86bd203d0c229c5a66498f178/chapter2/ex2-15.ss

[8:25pm] chrisconley: yeah

[8:25pm] aamar: http://mibbit.com/pb/xyWS7Y

[8:26pm] aamar: Okay, we say the same thing.

[8:26pm] nicou: yes

[8:26pm] mariorz: http://github.com/mariorz/sicp/blob/e34a61d80effdbbbbecb50dfbfc2a11ec9bf4287/2.ss#L508

[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: http://mibbit.com/pb/QRoQN0

[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?)

http://inimino.org/SICP-wiki/doku.php?id=exercise_2.16

[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

case.

[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/

[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: http://mibbit.com/pb/tPGuo8 -- 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

2.11

[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:

http://github.com/chrisconley/sicp-exercises/blob/e46bbaf96b12c4b86bd203d0c229c5a66498f178/chapter2/ex2-12.ss

[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: http://mibbit.com/pb/tCDkEf -- 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:

http://github.com/chrisconley/sicp-exercises/blob/e46bbaf96b12c4b86bd203d0c229c5a66498f178/chapter2/ex2-13.ss

[8:17pm] aamar: http://mibbit.com/pb/XzMyuJ -- 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:

http://github.com/chrisconley/sicp-exercises/blob/e46bbaf96b12c4b86bd203d0c229c5a66498f178/chapter2/ex2-14.ss

[8:21pm] aamar: http://mibbit.com/pb/ub4Ttt

[8:22pm] ews_ joined the chat room.

[8:22pm] chrisconley: did you guys draw any conclusions from

inestigating?

[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

formulas

[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:

http://github.com/chrisconley/sicp-exercises/blob/e46bbaf96b12c4b86bd203d0c229c5a66498f178/chapter2/ex2-15.ss

[8:25pm] chrisconley: yeah

[8:25pm] aamar: http://mibbit.com/pb/xyWS7Y

[8:26pm] aamar: Okay, we say the same thing.

[8:26pm] nicou: yes

[8:26pm] mariorz: http://github.com/mariorz/sicp/blob/e34a61d80effdbbbbecb50dfbfc2a11ec9bf4287/2.ss#L508

[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: http://mibbit.com/pb/QRoQN0

[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?)

http://inimino.org/SICP-wiki/doku.php?id=exercise_2.16

[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

case.

[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

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu