Re: Query: Decorations Challenge
John Pryce wrote:
You have been very quiet about my Decorations Challenge. Do you approve of
Arnold Neumaier's solution? If not, how would you amend it?
I am not familliar with the Matlab language, nor do I have any means to
compile and run Arnold's example in order to state for certain it does or
doesn't have any bugs. However, to the extent I am able to glean
understanding from his source code, it appears to me he has done everything
correct.
I also had the same observation you did that Arnold changed your example by
"resetting" the decoration at the beginning of each loop. Wether or not this
is the correct thing to do depends on the intent of the user, and the
purpose of the algorithm. Neither of these things were specified by you in
the original challenge, so I don't see anything wrong with what Arnold did.
For myself, I simply considered your example verbatim without questioning
whether or not the example, as given, had an intentional bug in it or not.
To the extent I am able to read your pseudo-code correctly, it appears the
algorithm begins by constructing the decorated interval:
xx = ([-1,4],safe)
and msg is set to "failure". Then iterations of a loop begin.
The very first time through the loop evaluates yy = g(xx):
yy = 1+sqrt(xx)
= 1+sqrt(([-1,4],safe))
= 1+([0,2],possiblyDefined)
= ([1,3],possiblyDefined)
Next, the relation "yy is contained in xx" is true, however, g was not
everwhere defined and continuous on xx (as indicated by the
"possiblyDefined" decoration). So msg is not set to "success" and the
algorithm does not break out of its loop. Instead, the decorated interval yy
is copied to the decorated interval xx. So now we have:
xx = ([1,3],possiblyDefined)
and the loop repeats itself.
Since your code (taken verbatim) does not reset the decoration of xx (as
Arnold did in his example), the remaining iterations through the loop will
never reach the msg = "success" break-point. Hence, the remaining two
iterations yield:
yy = 1+sqrt(([1,3],possiblyDefined))
= 1+([1,sqrt(3)],possiblyDefined)
= ([2,1+sqrt(3)],possiblyDefined)
yy = 1+sqrt(([2,1+sqrt(3)],possiblyDefined))
= 1+([sqrt(2),sqrt(1+sqrt(3))],possiblyDefined)
= ([1+sqrt(2),1+sqrt(1+sqrt(3))],possiblyDefined)
Therefore the final output will be:
count: 4
msg: failure
bare(xx): [2,1+sqrt(3)]
bare(yy): [1+sqrt(2),1+sqrt(1+sqrt(3))]
Which agrees exactly with your own expected outcome (see below), except I
only did 4 iterations but it appears you did 50.
Nate Hayes
On October 15, 2010 John Pryce wrote:
When the "domain" function is altered to do nothing, the output is again
as expected:
> AN_Solution1
info =
{
fail = 1
nf = 50
}
x =
{
inf = 2.6180
sup = 2.6180
}
----- Original Message -----
From: "John Pryce" <j.d.pryce@xxxxxxxxxxxx>
To: "Arnold Neumaier" <Arnold.Neumaier@xxxxxxxxxxxx>
Cc: "Nate Hayes" <nh@xxxxxxxxxxxxxxxxx>; "stds-1788"
<stds-1788@xxxxxxxxxxxxxxxxx>
Sent: Thursday, October 14, 2010 5:19 AM
Subject: 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
======================================================================