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

ex 2.16

Expand Messages
  • Ioura Batugowski
    Hello people, I found a copy of the SICP book in a used book store a few month ago, and after realising how good it was I started working on the exercises. I m
    Message 1 of 7 , Jul 2 5:02 AM
    • 0 Attachment
      Hello people,

      I found a copy of the SICP book in a used book store a few month ago,
      and after realising how good it was I started working on the
      exercises. I'm now at ex 2.43. I discovered this group yesterday and
      this is a nice surprise. Please excuse me in advance if I'm not always
      using the correct technical terms as I never had any math course in
      english.

      For this first post I would like to discuss ex 2.16. I hope it doesn't
      bother you that I come back to an already discussed exercise. John
      Berthels has made good points about this exercise. From a software
      engineering point of view, I think "interval arithmetic" is an
      inprecise description of the problem we are trying to solve. "Error
      calculation" might be a better term.

      To build a better system, my first idea was to use symbolic
      manipulation to transform the expression to an algebraically
      equivalent form which minimize the interval. But what is this form ?
      It should probably minimize the repetition of a single variable, but
      is it enough ? And how to select the right transformation rules ?
      These problems are a bit over my head...

      My second idea was more mathematical, and seems more practical too.
      I'll explain through an example: When asked to find the bounds of an
      expression such as (R1*R2)/(R1+R2), where R1 and R2 are intervals,
      find the extremas of the (mathematical) function f(x,y) = (x*y)/(x+y),
      where x and y are real values, over the domain formed by the
      intervals: R1xR2. The extremas (global minimum and maximum over the of
      the resuldomain) are the bounds ting interval. Well, finding the
      extremas of arbitrary functions is not that easy (maybe numerical
      methods would help?) but at least the solution is well defined. It
      wouldn't depend on the algebraic form of the expression, and give the
      smaller acceptable interval in all cases.Thinking about it, it may be
      the only correct way to do it in the general case.

      I would be interested to know if you agree or disagree. Is this the
      "right" way to perform error calculation ? If not, where is the fault
      in my reasonning ?

      regards,

      Ioura
    • Pascal Bourguignon
      ... Indeed. But for simple functions such as +, -, * and /, the probblem can be analyzed and we can provide an exact solution to this search of extrema.
      Message 2 of 7 , Jul 2 8:37 AM
      • 0 Attachment
        Ioura Batugowski writes:
        > My second idea was more mathematical, and seems more practical too.
        > I'll explain through an example: When asked to find the bounds of an
        > expression such as (R1*R2)/(R1+R2), where R1 and R2 are intervals,
        > find the extremas of the (mathematical) function f(x,y) = (x*y)/(x+y),
        > where x and y are real values, over the domain formed by the
        > intervals: R1xR2. The extremas (global minimum and maximum over the of
        > the resuldomain) are the bounds ting interval. Well, finding the
        > extremas of arbitrary functions is not that easy (maybe numerical
        > methods would help?) but at least the solution is well defined. It
        > wouldn't depend on the algebraic form of the expression, and give the
        > smaller acceptable interval in all cases.Thinking about it, it may be
        > the only correct way to do it in the general case.

        Indeed. But for simple functions such as +, -, * and /, the probblem
        can be analyzed and we can provide an exact solution to this search of
        extrema. That's what we're doing in these exercices.


        > I would be interested to know if you agree or disagree. Is this the
        > "right" way to perform error calculation ? If not, where is the fault
        > in my reasonning ?


        --
        __Pascal Bourguignon__ http://www.informatimago.com/
        In deep sleep hear sound,
        Cat vomit hairball somewhere.
        Will find in morning.
      • Ioura Batugowski
        ... But even for these basic operations, the extremas aren t always on the frontier of the domain and the exact solution can t be found by working only on the
        Message 3 of 7 , Jul 3 7:09 AM
        • 0 Attachment
          On 7/2/05, Pascal Bourguignon <pjb@...> wrote:
          > Indeed. But for simple functions such as +, -, * and /, the probblem
          > can be analyzed and we can provide an exact solution to this search of
          > extrema. That's what we're doing in these exercices.

          But even for these basic operations, the extremas aren't always on the
          frontier of the domain and the exact solution can't be found by
          working only on the bounds of the intervals. Take for instance X*X,
          where X is the interval [-1,1]. The exact solution is obvious: [0,1].
          With the system built in the previous exercises, the answer would be
          [-1,1] which may be admissible since it contains [0,1] but is not
          exact. If we modify the system to recognize that its the same
          variable, but still only derive the solution from the bounds of the
          interval, it would give [1,1] which is completely false.

          My maths are rusty, but I think that finding the exact solution (even
          if we only consider the four basic operations) would involve solving a
          few systems of non necessarily linear equations (to check for extremas
          in the domain and on the boundaries of the domain)...

          Ioura
        • Pascal Bourguignon
          ... Yes it is exact. If the actual values are -1 (in [-1,+1]) and +1 (in [-1,+1]), then the product -1*+1=-1 must be in the result. [-1,+1]*[-1,+1]=[-1,+1]
          Message 4 of 7 , Jul 3 2:02 PM
          • 0 Attachment
            Ioura Batugowski writes:
            > On 7/2/05, Pascal Bourguignon <pjb@...> wrote:
            > > Indeed. But for simple functions such as +, -, * and /, the probblem
            > > can be analyzed and we can provide an exact solution to this search of
            > > extrema. That's what we're doing in these exercices.
            >
            > But even for these basic operations, the extremas aren't always on the
            > frontier of the domain and the exact solution can't be found by
            > working only on the bounds of the intervals. Take for instance X*X,
            > where X is the interval [-1,1]. The exact solution is obvious: [0,1].
            > With the system built in the previous exercises, the answer would be
            > [-1,1] which may be admissible since it contains [0,1] but is not
            > exact.

            Yes it is exact. If the actual values are -1 (in [-1,+1]) and +1 (in
            [-1,+1]), then the product -1*+1=-1 must be in the result.

            [-1,+1]*[-1,+1]=[-1,+1]

            You must not have had good math teachers, if they've not told you that
            when you see an "obvious" solution in maths, then you're wrong. ;-)


            > If we modify the system to recognize that its the same
            > variable, but still only derive the solution from the bounds of the
            > interval, it would give [1,1] which is completely false.
            >
            > My maths are rusty, but I think that finding the exact solution (even
            > if we only consider the four basic operations) would involve solving a
            > few systems of non necessarily linear equations (to check for extremas
            > in the domain and on the boundaries of the domain)...

            There's no system to be solved. Only a decomposition of the problem
            into manageable cases.


            When you consider [a,b]*[c,d], you have the following cases:

            0 <= a <= b & 0 <= c <= d ==> [a,b]*[c,d] = [a*c,b*d]
            0 <= a <= b & c <= 0 <= d ==> [a,b]*[c,d] = [b*c,b*d]
            0 <= a <= b & c <= d <= 0 ==> [a,b]*[c,d] = [b*c,a*d]

            a <= 0 <= b & 0 <= c <= d ==> [a,b]*[c,d] = [a*d,b*d]
            a <= 0 <= b & c <= 0 <= d ==> [a,b]*[c,d] = [min(a*d,b*c),max(a*c,b*d)]
            a <= 0 <= b & c <= d <= 0 ==> [a,b]*[c,d] = [b*c,a*c]

            a <= b <= 0 & 0 <= c <= d ==> [a,b]*[c,d] = [a*d,b*c]
            a <= b <= 0 & c <= 0 <= d ==> [a,b]*[c,d] = [a*d,a*c]
            a <= b <= 0 & c <= d <= 0 ==> [a,b]*[c,d] = [b*d,a*c]


            Just draw the intervals yourself in the different cases.
            (Actually, the functions min and max hide further subcases, you can
            explicit them).


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

            The world will now reboot. don't bother saving your artefacts.
          • Ioura Batugowski
            ... Maybe they told me, but I wasn t listening at the time. My failures are my own ;-) But at the risk of seeming stubborn, I don t give up; I think there is
            Message 5 of 7 , Jul 4 2:00 AM
            • 0 Attachment
              On 7/3/05, Pascal Bourguignon <pjb@...> wrote:
              > Ioura Batugowski writes:
              > > On 7/2/05, Pascal Bourguignon <pjb@...> wrote:
              > > > Indeed. But for simple functions such as +, -, * and /, the probblem
              > > > can be analyzed and we can provide an exact solution to this search of
              > > > extrema. That's what we're doing in these exercices.
              > >
              > > But even for these basic operations, the extremas aren't always on the
              > > frontier of the domain and the exact solution can't be found by
              > > working only on the bounds of the intervals. Take for instance X*X,
              > > where X is the interval [-1,1]. The exact solution is obvious: [0,1].
              > > With the system built in the previous exercises, the answer would be
              > > [-1,1] which may be admissible since it contains [0,1] but is not
              > > exact.
              >
              > Yes it is exact. If the actual values are -1 (in [-1,+1]) and +1 (in
              > [-1,+1]), then the product -1*+1=-1 must be in the result.
              >
              > [-1,+1]*[-1,+1]=[-1,+1]
              >
              > You must not have had good math teachers, if they've not told you that
              > when you see an "obvious" solution in maths, then you're wrong. ;-)
              >

              Maybe they told me, but I wasn't listening at the time. My failures
              are my own ;-)

              But at the risk of seeming stubborn, I don't give up; I think there is
              some misunderstanding here. I think the goal of the last exercises on
              the subject (2.14-2.16) are there to make us think about the uses of
              the system we have built. Users are likely engineers; in engineering,
              intervals usually represents uncertainty on measures/quantities. In
              this light X=[-1,1] represents the fact that quantity X as a precise
              value, which is known to be between -1 and 1. X*X is the square of
              measure X, not the product of two unrelated quantities. For any (real)
              value of X, the square of X can't be negative.

              You might say (rightfully) it's outside the scope of interval
              arithmetic, but in this case I'd say: interval arithmetic is not
              really what users are interested in; error calculation is (or maybe
              there is a more consecrated term for it in english).

              >
              > > If we modify the system to recognize that its the same
              > > variable, but still only derive the solution from the bounds of the
              > > interval, it would give [1,1] which is completely false.
              > >
              > > My maths are rusty, but I think that finding the exact solution (even
              > > if we only consider the four basic operations) would involve solving a
              > > few systems of non necessarily linear equations (to check for extremas
              > > in the domain and on the boundaries of the domain)...
              >
              > There's no system to be solved. Only a decomposition of the problem
              > into manageable cases.
              >
              >
              > When you consider [a,b]*[c,d], you have the following cases:
              >
              > 0 <= a <= b & 0 <= c <= d ==> [a,b]*[c,d] = [a*c,b*d]
              > 0 <= a <= b & c <= 0 <= d ==> [a,b]*[c,d] = [b*c,b*d]
              > 0 <= a <= b & c <= d <= 0 ==> [a,b]*[c,d] = [b*c,a*d]
              >
              > a <= 0 <= b & 0 <= c <= d ==> [a,b]*[c,d] = [a*d,b*d]
              > a <= 0 <= b & c <= 0 <= d ==> [a,b]*[c,d] = [min(a*d,b*c),max(a*c,b*d)]
              > a <= 0 <= b & c <= d <= 0 ==> [a,b]*[c,d] = [b*c,a*c]
              >
              > a <= b <= 0 & 0 <= c <= d ==> [a,b]*[c,d] = [a*d,b*c]
              > a <= b <= 0 & c <= 0 <= d ==> [a,b]*[c,d] = [a*d,a*c]
              > a <= b <= 0 & c <= d <= 0 ==> [a,b]*[c,d] = [b*d,a*c]
              >
              >
              > Just draw the intervals yourself in the different cases.
              > (Actually, the functions min and max hide further subcases, you can
              > explicit them).
              >

              That's indeed what is asked for ex. 2.11; I have no problem
              understanding that. I was more specifically addressing ex. 2.14-2.16.
              And X*X was just an example, my point was more generally about
              functions for which extremas aren't on the boundaries of the domain,
              and it was the first one I could think of.

              Ioura
            • Pascal Bourguignon
              ... Well, the exercices asked for *, not for square. (* [-1,1] [-1,1]) -- [-1,1] (square [-1,1]) -- [0,1] In the case of square, we know the x is
              Message 6 of 7 , Jul 4 3:51 AM
              • 0 Attachment
                Ioura Batugowski writes:
                > But at the risk of seeming stubborn, I don't give up; I think there is
                > some misunderstanding here. I think the goal of the last exercises on
                > the subject (2.14-2.16) are there to make us think about the uses of
                > the system we have built. Users are likely engineers; in engineering,
                > intervals usually represents uncertainty on measures/quantities. In
                > this light X=[-1,1] represents the fact that quantity X as a precise
                > value, which is known to be between -1 and 1. X*X is the square of
                > measure X, not the product of two unrelated quantities. For any (real)
                > value of X, the square of X can't be negative.

                Well, the exercices asked for *, not for square.

                (* [-1,1] [-1,1]) --> [-1,1]
                (square [-1,1]) --> [0,1]

                In the case of square, we know the x is the same, so indeed, we could
                define square to return the intersection of the product with [0,+infity[.

                But in the case of the product, we don't know that x and y are the
                same measurement even when they're equal.


                So, now what is better, define square as above, or keep the identity
                (square x) === (* x x) ?


                > You might say (rightfully) it's outside the scope of interval
                > arithmetic, but in this case I'd say: interval arithmetic is not
                > really what users are interested in; error calculation is (or maybe
                > there is a more consecrated term for it in english).

                You've got a point, but also abstraction and mathematisation always do
                that: forget about the specifics of the user's problem, build a
                theoric machine, input the data, and output the abstract result. Then
                translate back the result to the user's problem domain. That's what
                allows us to use the same addition operation to add apples, dollars,
                inches and "real" numbers. It would be rather inconvenient if we had
                to define different addition operations for different kind of stuff.
                And beware of adding red apples with the green apple addition operator!
                (After all, if you add red apples with green apples, you may get brown
                compote ;-)

                --
                __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
                ... Yes, this was my thought too. I also thought it was over my head :-) Although, pleasingly, SICP seems to come closer to this sort of symbolic manipulation
                Message 7 of 7 , Jul 4 7:14 AM
                • 0 Attachment
                  On 7/2/05, Ioura Batugowski <ibatugow@...> wrote:

                  > To build a better system, my first idea was to use symbolic
                  > manipulation to transform the expression to an algebraically
                  > equivalent form which minimize the interval. But what is this form ?
                  > It should probably minimize the repetition of a single variable, but
                  > is it enough ? And how to select the right transformation rules ?
                  > These problems are a bit over my head...

                  Yes, this was my thought too. I also thought it was over my head :-)

                  Although, pleasingly, SICP seems to come closer to this sort of
                  symbolic manipulation a bit further on, so it looks more reasonable. I
                  don't have sufficient motivation to try and work on a real solution to
                  this, however.

                  For example, the constraint modelling, as refined in exercise 3.37 is
                  a system which maintains the algrebraic structure of a calculation, in
                  order to be able to calculate the value of whichever term lacks one.
                  It doesn't seem beyond the bounds of possibility that rules for
                  algrebraic simplification could be built into this. Also, the symbolic
                  differentiation from chapter 2.3 is also fairly close to this problem
                  area.

                  > My second idea was more mathematical, and seems more practical too.
                  > I'll explain through an example: When asked to find the bounds of an
                  > expression such as (R1*R2)/(R1+R2), where R1 and R2 are intervals,
                  > find the extremas of the (mathematical) function f(x,y) = (x*y)/(x+y),
                  > where x and y are real values, over the domain formed by the
                  > intervals: R1xR2. The extremas (global minimum and maximum over the of
                  > the resuldomain) are the bounds ting interval. Well, finding the
                  > extremas of arbitrary functions is not that easy (maybe numerical
                  > methods would help?) but at least the solution is well defined. It
                  > wouldn't depend on the algebraic form of the expression, and give the
                  > smaller acceptable interval in all cases.Thinking about it, it may be
                  > the only correct way to do it in the general case.

                  This is interesting. As your discussion with Pascal highlights, such
                  an analysis should also need to track the identity of various
                  quantites, to differentiate (mul-interval x y) from (mul-interval x x)
                  Note, however, that you can't re-establish identity from noting within
                  the mul-interval function that the two arguments have the same value
                  and error, since they may still be independent variables/measurements
                  which happen to have the exact same value and error.

                  So I guess you need a rule/restriction which states that when
                  analysing (f x y ... z), all the arguments must be independent
                  measurements/variables. Which is fine, since if they aren't you can in
                  theory define a function of fewer variables and analyse that instead.

                  As you suggest, a numerical approach (where you put a mesh or grid
                  over the function domain, and evaluate at all points in the grid)
                  sounds feasible, but has the drawback that it will always tend to
                  underestimate the error, perhaps badly, depending on the resolution of
                  the mesh and the shape of the function.

                  > I would be interested to know if you agree or disagree. Is this the
                  > "right" way to perform error calculation ? If not, where is the fault
                  > in my reasonning ?

                  It is an interesting approach. I guess the 'right' way depends on the
                  intended usage, as always. The numeric approach may be quite
                  practical, if you have some domain knowledge which allows you to
                  choose appropriate shaped/sized meshes and sufficient horsepower to
                  evaluate functions on a sufficiently dense mesh. (since even a
                  10-interval mesh has just raised the cost of evaluating a function of
                  two numbers by a factor of 100...).

                  I guess the 'right' answer is whatever people selling software in this
                  area have researched and implemented :-)

                  jb
                Your message has been successfully submitted and would be delivered to recipients shortly.