Skip to main content

IEEE Interval Standard Working Group - P1788 (in English)

  4 posts   Feedicon  
Replies: 3 - Last Post: January 14, 2012 19:04
by: Dmitry Nadezhin
« Older Topic » Newer Topic
showing 1 - 4 of 4
Posted: January 13, 2012 16:18 by Dmitry Nadezhin
This topic should be discussed in English so that foreign interval people could participate in discussion.

The P1788 IEEE Interval Standard Working Group started its work in 2008 and it is expected to release the Interval Standard in the end of 2012. Their activity can be followed in the public mailing list and in a private content. The chairman of this group Prof. Baker Kearfott sent a message on 1 January 2012 with call for volunteers that will create and support a reference implementation of the standard and a test suite. An idea to make JInterval the reference implementation of P1788 came to us. This topic will discuss how to do it.
Posted: January 13, 2012 16:19 by Dmitry Nadezhin
These are my first thoughts about reference implemntation/test suite.
I sent them to the P1788 mailing list also.

Standard can specify results of some operations in a unique way,
though results of other operations may be a little sloppy.
Let us take for example the midpoint operation "double mid(DoubleInterval x)".
If for some "x" the exact midpoint is not a double number,
the standard should allow (I hope) this operation to return any
of two double numbers that surround the exact midpoint.

The specification of the "mid" operation by mapping from input to output may be restrictive.
IMHO, the specification of "mid" operation should look like a predicate on input and output:
"boolean midShall(DoubleInterval x, double result)"
"boolean midShould(DoubleInterval x, double result)".

Ideally, such predicate should be defined in some proof checker language (like Coq).
However, I guess that this will happen only after adoption of the standard.
More quicker way is to define these predicates in a programming language.
The program component with such predicates can be called "checker".
The checker is a normative program component,
it expresses wordings of the standard in a computer-executable way.

A test suite for some operation is a program component that generates a stream of inputs for this operation.
It may be a plain reader of file with test inputs.
It may be a generator of random inputs.
It may be an algorithm that enumerates corner cases.

The test loop of a any implementation of P1788 that defines the "mid"
operation as well as others will look like
for (DoubleInterval x: midTestSuite.inputs()) {
double result = implementation.mid(x);
if (!checker.midShall(x, result)) println("failure");

The reference implementation must pass the above test loop, of course.
But I don't consider reference implementation as a normative program component.
Rather it is a proof of concept. It shows that the operation of the standard
can be implemented with a reasonable performance.

Perhaps a few reference implementation may exist.
One returns the tightest results, but it is slow.
The other is faster, but its results are not always the tightest.
These reference implementations can be written in different
programming languages.

So the framework in my opinion consists of:
* normative checker;
* testSuits;
* variants of reference implementations (perhaps in different programming languages);
* launcher.

The launcher is a component that
1) dynamically links ".jar"/".dll"/".so" file with particular
reference implementation,
2) loads testSuits
3) runs the testing loop.
Posted: January 13, 2012 16:19 by Dmitry Nadezhin
The draft of P1788 is structured into four levels. These levels are similar to those from IEEE754 standard.
Here is a small snippet form the current version of the draft:
  • Level 1 (Mathematical Model level) defines the mathematical theory underlying the standard. The entities at this level are mathematical intervals and operations on them. Conforming implementations shall implement this theory.
  • Level 2 (Interval datum level) is the central part of the standard. Here the mathematical theory is approximated by an implementation-defined finite set of entities and operations. A level 2 entity is called a datum (plural “datums” in this standard, since “data” is often misleading). In addition to an ordinary (bare) interval, this level defines a decorated interval, comprising a bare interval and a decoration. Decorations implement the P1788 exception handling mechanism.
  • Level 3 (Representation of interval data) defines the representation of interval datums in terms of underlying floating- point datums. A level 3 entity is an interval object.
  • Level 4 (Bit strings) is concerned with the encoding of interval objects. A level 4 entity is a bit string, though it may be broken into non-contiguous parts in memory.

I think that it is quite natural to structure our "checker" in the same way.
  • Level 1 checks input and outputs that are mathematical intervals with real bounds.
  • Level 2 checks inputs and outputs that are intervals with binary or decimal floating-point bounds. Intervals at this level are decorated with attribute bits. Checker predicates of level 2 are defined using checker predicates of level 1
  • Level 3 checks pairs of floating-point numbers together with decoration. Predicates of level 3 use checker predicates of level
  • Level 4 checks bit string. Predicates of level 4 use predicates of level3

At this message I consider how to express level 1 checks as Scala prdicates. Instead of intervals with real bounds we shall consider intervals with Rational bounds. First let us define what is Interval at Mathematical model level
class MathInterval {}
   case object Empty extends MathInterval {}
   case class Nonnempty(inf: Rational, sup: Rational) extends MathInterval {}

The predicate isValid
def isValid(x: MathInterval): Boolean = x match {
  case Empty => true
  case Nonemptu(inf, sup) => inf < sup ||
      inf == sup && inf != Rational.NEGATIVE_INFINITY && sup != Rational.POSITIVE_INFINITY

We define isSubset predicate
def isSubset(x: MathInterval, y: MathInterval): Boolean = isValid(x) && isValid(y) && x match {
  case Empty => true
  case Nonempty(xi,xs) => y match {
    case Empty => false
    case Nonempty(yi,ys) => yi <= xi && xs <= ys

The predicate addShall
def addShall(x: MathInterval; y: MathInterval; r: MathInterval): Boolean = isValid(x) and isValid(y) && isValid(r) && x match {
  case Empty => true
  case Nonempty(xi, xs) => y match {
    case Empty => true
    case Nonempty(yi, ys) => isSubset(Nonempty(xi + yi, xs + ys), r)

The predicate sqrtShall
def sqrtShall(x: MathInterval, r: MathInterval): Boolean = isValid(x) && isValid(r) && r match {
  case Empty => true
  case Nonempty(xi, xs) && xs < 0 => true
  case Nonempty(xi,xs) && xs >= 0 => r match {
    case Empty => false
    case Nonempty(ri,rs) => (ri <= 0 || xi >= ri*ri) && xs <= rs*rs 

Posted: January 14, 2012 19:04 by Dmitry Nadezhin
In the previous post I wrote a draft of a few checker methods. It was realy a draft, I didn't compile them.

I started to prototype the draft in this directory.
  • Class Rational.scala is a class that implements extended rational numbers (finite rational number, negative and positive infinites). It uses java class com.kenai.jinterval.number.Rational .
  • Class Interval.scala is a Level 1 interval. It is either Empty interval or Nonempty(inf: Rational, sup: Rational).
  • Class DirectedFractionals.scala contains a few objects that defines operations on Doubles, Rationals and Intervals. They are: operations with directed rounding on Doubles; exact operations and operations with directed rounding on Rationals; operations on Intervals.
  • Class Checker.scala is a start of P1788 checker.
  • Class TestFractionals.scala is a tempory test class.
Replies: 3 - Last Post: January 14, 2012 19:04
by: Dmitry Nadezhin
« Older Topic » Newer Topic
Please Confirm