Loading ...
Sorry, an error occurred while loading the content.

Ex 2.10: question for John

Expand Messages
  • Philip Ansteth
    ... 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:

      > There's probably a geometric way of thinking about this which makes is
      > 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.
    • Philip Ansteth
      ... 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?
      • Pascal J.Bourguignon
        ... 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
        • John Berthels
          ... 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
            > > There's probably a geometric way of thinking about this which makes is
            > > 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...
          • Philip Ansteth
            ... 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) ?
            • Pascal J.Bourguignon
              ... 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
              • John Berthels
                ... 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]

                  > 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).

                  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
                  drifting off-topic here and also about diverting your energies away
                  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
                • Philip Ansteth
                  ... 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.