## Ex 2.10: question for John

Expand Messages
• ... Any more thoughts about a geometric way of thinking? I d like it, probably, if I could think about it that way.
Message 1 of 12 , May 12, 2005
• 0 Attachment
--- In sicp-vsg@yahoogroups.com, John Berthels <john.berthels@g...> wrote:

> clearer, but maybe the above helps too?
>

Any more thoughts about a geometric way of thinking? I'd like it,
probably, if I could think about it that way.
• ... Why did you turn the square brackets outward, as in ]a,b[ as opposed to [a,b]? Also, what is the force of your term random. Are you using it in a
Message 2 of 12 , May 12, 2005
• 0 Attachment
--- In sicp-vsg@yahoogroups.com, Pascal J.Bourguignon <pjb@i...> wrote:

> numbers. Therefore dividing an interval by this interval doesn't give
> one interval, but two: ]a,b[ / ]-x,+x[ |---> ]-oo,-b/x[ U ]a/x,+oo[
>
> Since you want your operations on interval return new intervals and
> not random sets, you cannot accept that anymore than you can accept to
> divide by zero.
>

Why did you turn the square brackets outward, as in ]a,b[ as opposed
to [a,b]?

Also, what is the force of your term "random." Are you using it in
a formal way?
• ... Oops, that must be: ]a,b[ / ]-x,+x[ |--- ]-oo,-a/x[ U ]a/x,+oo[ ... This is not important. I was just thinking of open intervals instead of closed
Message 3 of 12 , May 12, 2005
• 0 Attachment
Philip Ansteth writes:
> --- In sicp-vsg@yahoogroups.com, Pascal J.Bourguignon <pjb@i...> wrote:
>
> > numbers. Therefore dividing an interval by this interval doesn't give
> > one interval, but two: ]a,b[ / ]-x,+x[ |---> ]-oo,-b/x[ U ]a/x,+oo[

Oops, that must be: ]a,b[ / ]-x,+x[ |---> ]-oo,-a/x[ U ]a/x,+oo[

> > Since you want your operations on interval return new intervals and
> > not random sets, you cannot accept that anymore than you can accept to
> > divide by zero.
> >
>
> Why did you turn the square brackets outward, as in ]a,b[ as opposed
> to [a,b]?

This is not important. I was just thinking of open intervals instead
of closed intervals.

> Also, what is the force of your term "random." Are you using it in
> a formal way?

No, in an informal way. Change it with a universal quantifier.

Actually, one could _define_ arithmetic operations on sets, but the
point is that these operations would not have any definite properties
if you don't restrict the set of sets you're considering.

Let P(R) be the set of all subsets of R.

Let's define these operations:

+ : P(R) x P(R) ------> P(R)
(U , V) |-----> W={w|there is a u in U and a v in V such as w=u+v}

- : P(R) x P(R) ------> P(R)
(U , V) |-----> W={w|there is a u in U and a v in V such as w=u-v}

* : P(R) x P(R) ------> P(R)
(U , V) |-----> W={w|there is a u in U and a v in V such as w=u*v}

/ : P(R) x P(R) ------> P(R)
(U , V) |-----> W={w|there is a u in U and a v in V such as w=u/v}

And let's define an interval as:

An element U of P(R) is an interval
<=def=> there are a,b in R, such as a<=b and U={x|0<=(x-a)<=(b-a)}

Notation: U=[a,b]

Theorem: for all interval U and V, U+V, U-V and U*V are intervals.

Theorem: for all interval U=[a,b] and V=[c,d],
for all op in {+,-,*,/},
for all e in U and f in V,
U op V = [a,e] op V union [e,b] op V
U op V = U op [c,f] union U op [f,d].

But, if U and V are closed intervals and V contains 0
then U/V is not an interval.

For example, [1,1]/[-1,1] = [1,1]/[-1,0] union [1,1]/[0,1]

[1,1]/[-1,0] = ]-oo,-1] [a]
and: [1,1]/[0,1] = [1,+oo[ [b]

So: [1,1]/[-1,1] = ]-oo,-1] union [1,+oo[ [c]

Unfortunately, ]-oo,-1] and [1,+oo[ are not intervals per the above
definition, and neither is ]-oo,-1] union [1,+oo[.

So, if you want your operations on intervals to be endomorphic, you
need to prevent division by an interval containing 0.

Note that / is endomorphic on P(R), but everytime you divide by a set
containing 0, you obtain more and more complex sets, for which you
need more and more bits to describe.

--
__Pascal Bourguignon__ http://www.informatimago.com/

There is no worse tyranny than to force a man to pay for what he does not
want merely because you think it would be good for him. -- Robert Heinlein
• ... Hmm. I don t have anything to hand. Maybe this helps. Multiplication by a single factor scales an interval (shifts it along towards or away from the
Message 4 of 12 , May 13, 2005
• 0 Attachment
> > clearer, but maybe the above helps too?
> >
>
> Any more thoughts about a geometric way of thinking? I'd like it,
> probably, if I could think about it that way.

Hmm. I don't have anything to hand. Maybe this helps.

Multiplication by a single factor scales an interval (shifts it along
towards or away from the origin). Think of a cartesian (x-y) plane.
Draw your interval on the X axis (shade in a segment) and then scaling
by a single factor (say K) can be visualised by mapping the segment up
to the line y=kx and then horizontally to the y-axis.

Dividing by an interval was taken to mean taking the reciprocal of an
interval and then multiplying. The reciprocal is the dodgy bit. You
can visualise taking the reciprocal of the an interval as doing the
same process as above, but instead of a y=kx, you use the graph of
y=1/x. Note that this is discontinuous as x=0, +ve and -ve tails
"going off to infinity".

If you do this with an interval which doesn't span 0, you'll get a
fairly well behaved mapping. If your interval does span 0, you get (as
Pascal pointed out) two "image" intervals, one containing +inf and one
containing -inf.

Another way of thinking of it is to do something not easy to justify
mathematically, which is to map the real line plus a "point at
infinity" to a circle [there is a cool construction of this (*)]. Then
scaling your intervals (and taking reciprocals of intervals)
correspond to moving your segment around the circle and changing its
width. But taking a reciprocal of an interval which spans 0 leaves you
with an image interval which includes your "point at infinity", hence
the problem.

regards,

jb

(*) Take a circle. Draw the real line tangent to it, calling the point
of contact the origin. Call the opposite point on the circle X (your
"point at infinity"). Then each pt on the real line maps to the unique
pt of the circle which lies on the line joining the real to X. No real
pt maps to X...
• ... I interpret multplication by a single factor as multiplication by an interval with equal upper and lower bounds. Using your mapping visualization with a
Message 5 of 12 , May 13, 2005
• 0 Attachment
I think I understand your first paragraph:

--- In sicp-vsg@yahoogroups.com, John Berthels <john.berthels@g...> wrote:

> Multiplication by a single factor scales an interval (shifts it along
> towards or away from the origin). Think of a cartesian (x-y) plane.
> Draw your interval on the X axis (shade in a segment) and then scaling
> by a single factor (say K) can be visualised by mapping the segment up
> to the line y=kx and then horizontally to the y-axis.
>

I interpret multplication by a single factor as multiplication by
an interval with equal upper and lower bounds. Using your mapping
visualization with a line y=.5x is the same as:
(mul-interval (make-interval 1 2) (make-interval .5 .5)) --> (0.5 .
1.0) which is equivalent to the segment from .5 through 1 on the y-axis

With a line y=2x, your mapping visualization is the same as:
(mul-interval (make-interval 1 2) (make-interval 2 2)) --> (2 . 4)
which is equivalent to the segment from 2 through 4 on the y-axis.

So it takes two geometric mappings to make
(mul-interval (make-interval 1 2) (make-interval .5 2)) --> (0.5 . 4.0).

I worked a little on your next point, the y=1/x mapping. It looked
like it would be okay, and impatiently I jumped ahead to the
circle/line construction, which looks interesting.

But, I don't know how to end up with a segment from .5 through 4.0
on the line. Do you know how to figure the radius of the circle,
the angles to make the arc corresponding to, say, (.5 . 2) ?
• ... Have a look at the tangent function (tan x) and its inverse (atan x). -- __Pascal Bourguignon__ http://www.informatimago.com/ Until
Message 6 of 12 , May 13, 2005
• 0 Attachment
Philip Ansteth writes:
> But, I don't know how to end up with a segment from .5 through 4.0
> on the line. Do you know how to figure the radius of the circle,
> the angles to make the arc corresponding to, say, (.5 . 2) ?

Have a look at the tangent function (tan x) and its inverse (atan x).

--
__Pascal Bourguignon__ http://www.informatimago.com/
Until real software engineering is developed, the next best practice
is to develop with a dynamic system that has extreme late binding in
all aspects. The first system to really do this in an important way
is Lisp. -- Alan Kay
• ... Fair enough, but I was trying to go the other way (I didn t go into detail, sorry I was in a rush). i.e. You can think of multiplying by an interval as the
Message 7 of 12 , May 14, 2005
• 0 Attachment
Philip Ansteth writes:
> I interpret multplication by a single factor as multiplication by
> an interval with equal upper and lower bounds.

Fair enough, but I was trying to go the other way (I didn't go into
detail, sorry I was in a rush). i.e. You can think of multiplying by
an interval as the same thing as multiplying by a single factor, for
every single factor in that interval.

i.e.:

if [a, b] * [c, d] -> [A, B]

then [A, B] = Union of all the [ka, kb] for k in [c, d]

Each value of k gives a different image of the [a, b] interval and and
visually, you can think of "sliding" the k through the [c, d] interval
and collecting all the resulting images to get your image of [a, b]
under multiplication by [c, d].

[but I think I'm going off-topic, see below for more on that]

> visualization with a line y=.5x is the same as:
> (mul-interval (make-interval 1 2) (make-interval .5 .5)) --> (0.5 .
> 1.0) which is equivalent to the segment from .5 through 1 on the y-axis
>
> With a line y=2x, your mapping visualization is the same as:
> (mul-interval (make-interval 1 2) (make-interval 2 2)) --> (2 . 4)
> which is equivalent to the segment from 2 through 4 on the y-axis.
>
> So it takes two geometric mappings to make
> (mul-interval (make-interval 1 2) (make-interval .5 2)) --> (0.5 . 4.0).

Yes, if you just take the end points, but as mentioned above I'd
visualise it by effectively considering every real in the interval.
Not something thats really possible in a programming language...

I don't want to distract you on this. I think from the point of view
of SICP, it is possible to just take at face value "division of
intervals fails for intervals containing 0". I'm worried about
from the main points of the material. Ex 2.10 doesn't require you to
explain why such intervals fail. Maybe thats a good lesson, accept the
domain knowledge of experts such as Ben Bitdiddle and get on with the
code :-)

> I worked a little on your next point, the y=1/x mapping. It looked
> like it would be okay, and impatiently I jumped ahead to the
> circle/line construction, which looks interesting.
>
> But, I don't know how to end up with a segment from .5 through 4.0
> on the line. Do you know how to figure the radius of the circle,
> the angles to make the arc corresponding to, say, (.5 . 2) ?

The radius is whatever you want.

As Pascal says, the mapping is related to atan (but a straight 'atan'
function will give you only a semircle, not a circle).

I think I've been a bit unfair, because I'm not thinking of this in
terms of hard numbers, more as a visualisation tool. For example,
taking the reciprocal of an number (and hence also all the numbers
which make up an interval) "kind of" involves mapping it to the other
side of the circle. This is sort-of true in the important aspect that
as you approach the origin, you head around to the infinity point on
the circle, but it is probably false in that I think it doesn't work
out numerically.

So...I wouldn't personally try numerical experiments with this. If it
works for you as a visualisation tool, then cool. If not, then don't
burn any brain cells on it - I'm probably distracting you from the
SICP...

regards,

jb
• ... John (and Pascal), I don t really think there s anything too terribly wrong with digressions. It wouldn t hurt me to know more about the math and set
Message 8 of 12 , May 14, 2005
• 0 Attachment
--- In sicp-vsg@yahoogroups.com, John Berthels <john.berthels@g...>
wrote:

>
> [but I think I'm going off-topic, see below for more on that]
>

John (and Pascal),

I don't really think there's anything too terribly wrong with
digressions. It wouldn't hurt me to know more about the math
and set theory you guys are talking about (in response, partly
at least, to my questions).

But I have recognized the need to go on.

Still, I don't think the recent posts have been THAT far off topic. If
I'm understanding the theme of the SICP authors in Section 2.1.4
correctly--there is some problem in the postulates that Alyssa starts
with.

Wasn't there, historically, a relationship between the attempt to
formalize Euclid's postulates and the study of axiomatic systems?
That's what I remember, but I could be wrong.

Anyway, time IS our greatest enemy, and it is important to get on
with SICP. I haven't figured out Ex. 2.11 yet, much less
2.14 through 2.16.
Your message has been successfully submitted and would be delivered to recipients shortly.