Re: [WWdevel] Subtractive cancellation

[P. G. L. <gl...@um...>]

Hi Davide,

Thanks for confirming what I had suspected was the case in the different 
results returned by the Parser and non-parser evaluators.

This is a "for your information" follow-up; you may be aware of these 
ideas already, but they're sufficiently novel to me that I'm forwarding 
them to the group.  I had an exchange with John Orr at some point about 
how answer checking is/was done in eGrade(/EDU), as a result of which he 
referred me to an article he wrote with Fisher and Scott ("Randomized 
Interval Analysis Checks for the Equivalence of Mathematical Expressions", 
by TW Fisher, JL Orr and SD Scott; I can find it listed as a preprint on 
his webpage, <http://www.math.unl.edu/~jorr1/research/abstracts.html>, but 
it doesn't say there if it was published).

The upshot of the article as I understand it is that they replace the 
standard numerical check of equivalence with an interval equivalence: 
given the standard operations and functions on machine precision numbers, 
they define the rounded interval versions of these functions and 
operations to operate on intervals, returning an interval that is 
guaranteed to include all values of the function when correctly evaluated 
on the interval.  That is, given an interval A = [a1,a2], then f(A) =
{ f(a) | a in A }, and the rounded interval version of f returns an 
interval that is guaranteed to include f(A) (plus, of course, possible 
additional values).

Thus, for each operation or elementary function they have an interval
definition that returns an interval in which the exact interval evaluation
of the function or operation must lie.  Equivalence of functions is then
determined by picking test points and determining the rounded intervals in
which the functions evaluated at these points must lie.  If at least one
of the resulting pairs of intervals is non-overlapping, the functions are
judged unequal.

This method still has trouble with numerical instability (the intervals
generated are large in this case), of course.

Cheers,
Gavin

-- 
P. Gavin LaRose / Instructional Tech.,  The tough problem is not in iden-
Math Dept., University of Michigan      tifying winners;  it is in making
gl...@um...                       winners of ordinary people. That,
734.764.6454                            after  all,  is  the overwhelming
http://www.math.lsa.umich.edu/~glarose/ purpose of education.  -K.P.Cross

On Wed, 12 Apr 2006, Davide P.Cervone wrote:

>> I'm afraid I'm going to sully your elegant explanation with a stupid 
>> question.  I (believe I) understand the issue of cancellation, however poor 
>> I may be at predicting it.  In the example problem that we discussed before 
>> you sent this e-mail, I found that the issue with subtractive cancellation 
>> occurred when I used the Parser version of fun_cmp, but not the older 
>> version.  Is there any reason besides blind luck that the older version 
>> didn't also mis-grade the problem?
>
> Yes, there is a reason:  the two versions of the checker pick the random 
> points differently (it is a simple matter of the order in which things are 
> done, so the random numbers you get are different in the two orders), so when 
> you switch to the older checker, the chances are you don't get the point near 
> the origin that is the one that has the instability.
>
> Davide
>
>
>
>