Re: Tetrits and "stickiness"
I've been unable to keep up with this thread in real time, but I have just read through all the messages for the past few days. I cannot guarantee I got all the details. WOW!
Ian, I appreciate the length & detail of your examples.
I still wonder whether propagating ONLY the sticky decorations might be enough. If I write an interval algorithm using a Fixed Point Theorem applied to a function f, all I care about is that f is continuous on the interval \x. If it fails to be continuous, I really don't care where. I THINK sticky decorations are all I need for that.
Forgive me if it has been raised (and settled?) earlier, but we seem to consider isDefined as a surrogate for isContinuous, especially given the dangers of isContinuous. What about
floor([0.5, 1.5])?
c = [-1, 1]; d = c ? a : b;
George
On Apr 15, 2010, at 6:03 PM, Ian McIntosh wrote:
> Sorry about the length, but concrete examples sometimes help.
>
>
> What I had in mind would be something like
>
> DoubleInterval calculate (DoubleInterval a, DoubleInterval b, DoubleInterval c)
> {
> DoubleInterval x, y, z, xyz;
> try
> {
> // full speed calculations
> x = a + b * c;
> y = b + c * a;
> z = c + a * b;
> xyz = x * y * z;
> if (IntervalErrorOccurred (xyz) ) throw IntervalErrorValue (xyz);
> }
> catch (IntervalErrorValue errorValue)
> {
> // step by step calculations
> if (IntervalErrorOccurred (a)) ReportIntervalErrorIn (a, "parameter a");
> if (IntervalErrorOccurred (b)) ReportIntervalErrorIn (b, "parameter b");
> if (IntervalErrorOccurred (c)) ReportIntervalErrorIn (c, "parameter c");
> x = a + b * c; if (IntervalErrorOccurred (x)) ReportIntervalErrorIn (x, "x = a + b * c");
> y = b + c * a; if (IntervalErrorOccurred (y)) ReportIntervalErrorIn (y, "y = b + c * a");
> z = c + a * b; if (IntervalErrorOccurred (z)) ReportIntervalErrorIn (z, "z = c + a * b");
> xyz = x * y * z; if (IntervalErrorOccurred (xyz)) ReportIntervalErrorIn (xyz, "xyz = x * y * z");
> }
> return (xyz);
> }
>
> IntervalErrorOccurred (intervalValue) would check if the decorations in intervalValue say an error occurred.
>
> ReportIntervalErrorIn (intervalValue, string) would print a message. Since it's given both the value and a string describing it, it can examine the value, report what's wrong with it, and report its formula. It should of course also report the file name, function name and line number, and it's a pity to write the formula once to be executed and a second time to possibly be printed. In real life I'd write a macro packaging all that up, so the catch block would look something like
>
> ReportIfIntervalError (x = a + b * c);
> ReportIfIntervalError (y = b + c * a);
> ReportIfIntervalError (z = c + a * b);
> ReportIfIntervalError (xyz = x * y * z);
>
> ReportIfIntervalError (expression) would turn its parameter into both code to be executed and a string to describe it, and do the same as the example above.
>
>
>
> The important thing is that since you can check the decorations of a final value or an intermediate result or a subexpression or an input parameter, you can write code to investigate and report on the details if you want them. You could even add checks on intermediate expressions like b * c. If you define types DoubleInterval for speed and CheckedDoubleInterval which does the checking inside each operation, the example could be
>
> DoubleInterval calculate (DoubleInterval a, DoubleInterval b, DoubleInterval c)
> {
> DoubleInterval x, y, z, xyz;
> try
> {
> // full speed calculations
> x = a + b * c;
> y = b + c * a;
> z = c + a * b;
> xyz = x * y * z;
> if (IntervalErrorOccurred (xyz) ) throw IntervalErrorValue (xyz);
> }
> catch (IntervalErrorValue errorValue)
> {
> // automatically checked calculations
> CheckedDoubleInterval xx, yy, zz, xyz;
> xx = a + b * c;
> yy = b + c * a;
> zz = c + a * b;
> xxyyzz = xx * yy * zz;
> xyz = xxyyzz;
> }
> return (xyz);
> }
>
> which would do the same detailed checking under the covers in the second part, but the first part would run full speed. The next step might be to use undecorated intervals in the fast path, as long as there is a way to check whether an error occurred, but that would probably involve a per-thread status register like typical floating point implementations have.
>
> With a little more smarts using templates, all the source code duplication can be eliminated too, but the example is much less obvious:
>
> DoubleInterval calculate (DoubleInterval a, DoubleInterval b, DoubleInterval c)
> {
> template <type DInterval>
> {
> inline DInterval calculateTemplate (DInterval a, DInterval b, DInterval c)
> {
> DInterval x, y, z;
> x = a + b * c;
> y = b + c * a;
> z = c + a * b;
> return (x * y * z);
> }
> };
> if (IntervalErrorOccurred (calculateTemplate <DoubleInterval> (a, b, c)) // fast using DoubleInterval
> return (calculateTemplate <CheckedDoubleInterval> (a, b, c)); // checked using CheckedDoubleInterval
> }
>
> Now the calculations only need to be written once. The "// fast" line generates a copy of them using type DoubleInterval for speed, checks the final result to see if an error occurred anywhere in it, and if yes then executes the "// slow" line which generates a copy of them using type CheckedDoubleInterval for detailed step by step checking and reporting. You have speed and detailed checking in a reasonably simple form, and it can be simplified more. The actual internal compiled code would be very similar to the previous example. For simplicity, this relies on automatic conversions of function parameters and assignments to the required type.
>
> The only decorations needed are to describe the result, not what went into it. The final decorations are determined by the history (the operations and their input values), but they don't need to (and in finite space can't) describe its complete history.
>
> What if you wanted to calculate even faster, using undecorated intervals? Then you'd use a different type name in the fast calculations, and you'd need a modified UndecoratedIntervalErrorOccurred function that cleared the current thread's hardware error status register, called calculateTemplate <UndecoratedDOubleInterval>, and checked for errors by looking in the status register. So that all works too, with only trivial changes. Assuming the parameters and result are decorated, only one line is changed:
>
> DoubleInterval calculate (DoubleInterval a, DoubleInterval b, DoubleInterval c)
> {
> template <type DInterval>
> {
> inline DInterval calculateTemplate (DInterval a, DInterval b, DInterval c)
> {
> DInterval x, y, z;
> x = a + b * c;
> y = b + c * a;
> z = c + a * b;
> return (x * y * z);
> }
> };
> if (UndecoratedIntervalErrorOccurred (calculateTemplate <UndecoratedDoubleInterval> (a, b, c)) // faster using UndecoratedDoubleInterval
> return (calculateTemplate <CheckedDoubleInterval> (a, b, c)); // checked using CheckedDoubleInterval
> }
>
> - Ian McIntosh IBM Canada Lab Compiler Back End Support and Development
>
> ----- Forwarded by Ian McIntosh/Toronto/IBM on 04/15/2010 05:33 PM -----
>
> <ecblank.gif>
> From: <ecblank.gif>
> Michel Hack <hack@xxxxxxxxxxxxxx>
> <ecblank.gif>
> To: <ecblank.gif>
> Ian McIntosh/Toronto/IBM@IBMCA
> <ecblank.gif>
> Date: <ecblank.gif>
> 04/15/2010 04:42 PM
> <ecblank.gif>
> Subject: <ecblank.gif>
> Re: Tetrits and "stickiness"
>
>
>
> > In that case, when the routine is repeated, can't the debugger just
> > manually reset the decoration of each input interval during the slow
> > but thoroughly-checked sequence?
>
> What debugger? I'm talking running program here, with alternate paths
> depending on whether funny things do or don't happen, as detected by
> the sticky decorations.
>
> If the sticky bits represent the same information as the detailed bits
> for a single operation, then yes, it would be sufficient to implement
> the sticky bits, and have the program clear the sticky bits before
> every operation. I was under the impression however that the detailed
> bits proposed by Dan Zuras carried more information than can be handled
> as a sticky bit.
>
> There is also the issue of the cost of the explicit clearing, but that
> depends greatly on implementation choices, and might be negligible.
>
> Michel.
> ---Sent: 2010-04-15 20:40:14 UTC
>
Dr. George F. Corliss
Electrical and Computer Engineering
Marquette University
P.O. Box 1881
1515 W. Wisconsin Ave
Milwaukee WI 53201-1881 USA
414-288-6599; GasDay: 288-4400; Fax 288-5579
George.Corliss@xxxxxxxxxxxxx
www.eng.mu.edu/corlissg