## ex 2.16

Expand Messages
• 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, 2005
• 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
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
• ... 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, 2005
• 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.
• ... 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, 2005
• 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
• ... 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, 2005
• 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.
• ... 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, 2005
• 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
• ... 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, 2005
• 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
• ... 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, 2005
• 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.