A Decorations Challenge
Arnold, Nate, P1788
Arnold, I remain sceptical of your new scheme as I am of Nate's domain tetrit, namely it confuses properties of an interval with properties of the computation history that produced it. Here is my challenge, basically the example in 5.3 of my "Decoration Properties, Structural Induction, and Stickiness" position paper.
If you, or anyone, can meet it, I will stop complaining (or complain less loudly, anyway). More importantly, the solution will provide checkable evidence that the P1788 decoration scheme supports the writing of provably correct algorithms.
Problem
=======
Let g(x) = 1 + sqrt(x).
In the algorithm, g also denotes the interval version of this.
Input:
real values xlo, xhi.
Algorithm:
construct xx = (decorated) interval [xlo,xhi]
set msg = "failure"
for count = 1 to 3 do
set yy = g(xx)
if (yy is contained in xx) and
(g is everywhere defined and continuous on xx)
then set msg = "success" and break (i.e. exit the loop)
else set xx = yy
end for
Output:
count, msg, bare(xx), bare(yy)
Test data:
xlo = -1, xhi = 4
Note: count is assumed to equal 4 on normal (non-break) exit from the loop.
Challenge
=============================================================
Refine this into code, say in C/C++ or Matlab, giving sufficient specification of the library functions used that you can perform a complete execution trace (dry run). Exact arithmetic may be used in the dry run, or finite precision if you wish. If the latter, I suggest 4 digit decimal floating point.
Two dry runs are required: first using Hayes "domain" tetrit and my "continuous" bit (or its reverse) in the decoration; second using Arnold's new scheme.
Present the dry runs suitably tabulated, with their final output.
=============================================================
The library functions that need specifying include
decorated interval versions of +, sqrt
constructor
getter and/or setter functions for decorations
That's my first try at the challenge specification. It will probably need revising.
John
On 10 Oct 2010, at 12:15, Arnold Neumaier wrote:
> ========================================================================
> It is proposed that precisely the following five decorations shall be available:
>
> dec = 0: safe = everywhere defined, continuous, and bounded)
> dec = 1: everywhere defined
> dec = 2: possibly everywhere defined
> dec = 3: nowhere defined
> dec = 4: not valid
>
> In all interval exchange formats, a decoration is encoded by an
> unsigned integer dec taking one of the values 0, 1, 2, 3, or 4.
> The encoding in a datatype is left to the implementor.
>
>
> The following unary predicates shall be provided for bare decorations
> and for decorated intervals of any supported idatatype:
>
> isValid dec<4
> possiblyNonempty dec<3
> everywhereDefined dec<2
> isSafe dec<1
>
> notValid dec>3
> isEmpty dec>2
> possiblyUndefined dec>1
> notSafe dec>0
> ======================================================================