Interval arithmetics

• Template parameters
• How to create an interval?
• How to access interval end points?
• Writing and reading intervals
• Exact input and output
• Arithmetic operators
• Elementary functions
• Logical operators and inclusions
• Inclusions
• Interval specific functions
• Constants

Choosing between CAPD and FILIB intervals

When configuring CAPD library you can choose which of interval arithmetic packages, native CAPD intervals or wrapper for FILIB, will be used as default one for double precision. To do that pass the flag –without-filib or –with-filib to the configure script.

Note

For the moment we recommend FILIB intervals because GCC optimization of the native CAPD intervals with build-in floating point types can produce not correct results.

Both interval arithmetics have the same interface. If you include file capd/intervals/lib.h then the name capd::DInterval points always to the current intervals. This allows to write code that will work with both interval arithmetics.

The native CAPD interval arithmetics is more general and has end point type as template parameter.
The following example uses explicitly CAPD intervals but almost everything applies to the FILIB intervals as well.

Template parameters

Template class Interval has two parameters

template class Interval <typename BoundType, typename Rounding>

• BoundType - type of interval ends (e.g. int, double, MpFloat)
• Rounding - class that switches rounding.
  If Rounding is not given then default values are taken:
  • DoubleRounding for double, long double
  • IntRounding for all integer types: int, long ...
  • BoundType for user other types

The following lines define new names for intervals with the endpoint's type: double, int, MpFloat correspondigly

typedef capd::intervals::Interval< double > DInterval;
typedef capd::intervals::Interval< int > ZInterval;
typedef capd::intervals::Interval< capd::MpFloat > MpInterval;

In the following we will use type DInterval but in most of the cases any of the above can be used.

Note

If you include file "capd/intervals/lib.h" then capd::DInterval is already defined as interval with double endpoints.

How to create an interval?

We can construct intervals by :

  DInterval a;                   // a = [0.0, 0.0] (*)
  DInterval b(1.0);              // b = [1.0, 1.0]
  DInterval c(2.0, 3.0);         // c = [2.0, 3.0]
  DInterval d(c);                // d = [2.0, 3.0]
  DInterval e("2.5","3.0");      // e = [2.4999999999999996, 3.0000000000000004]

A constructor from string (the last one) is the safest one but it brings overestimations. Interval bounds are read from string and then last bit of their mantissa is rounded to ensure enclosure. It always produce intervals of non zero width e.g. diameter of (DInterval("1.0", "1.0")) is 3.33067e-16.

Note

If you create an interval by

DInterval x(0.1, 0.1) 

it will NOT contain 0.1. The reason is that 0.1 is not representable and it will be rounded to the nearest representable by compiler before passing to the constructor.
The most appropriate way to enclose not-representable number 0.1 is to do the following

DInterval x(1);
x /= 10;

(*) The state of the interval a depends on a flag INTERVAL_INIT_0. If this flag is set in file capdAlg/include/capd/interval/intervalSettings.h then a = [0.0, 0.0] (this is the default behaviour), otherwise a is not initialized.

How to access interval end points?

To obtain left or right end point of the interval one can use leftBound or rightBound functions. They are implemented both as member and global functions.

DInterval c(2.0, 3.0);
 
// member functions
c.leftBound();                   // the result is 2.0
c.rightBound();                  // the result is 3.0
 
// or global functions
leftBound(c);                    // the result is 2.0
rightBound(c);                   // the result is 3.0

To get point interval that contains left or right end point use function left or right correspondigly

c.left();          // or
left(c);           // in both cases the result is an interval [2.0, 2.0]
 
c.right();         // or
right(c);          // in both cases the result is an interval [3.0, 3.0]

Note

To change one of the the endpoints use setLeftBound or setRightBound.

c.setLeftBound(3.2);

Writing and reading intervals

Intervals can be written to any C++ stream using operator <<. The output depends on parameters of a stream e.g precision.

   DInterval x(1.0, 2.0);
   cout << x << "  ";                          // output: [1,2]
   cout << fixed << setprecision(6) << x;      // output: [1.000000,2.000000]

To read intervals from given stream (e.g. keyboard, file or memory) use operator >>. The format of an input should be :

[leftEnd,rightEnd]

where leftEnd and rightEnd are in the form that can be read into endpoint type (BoundType) with operator >>.

   std::istringstream myStr("[3.21312312, 4.324324324]");
   myStr >> a;

Note

On output and input interval endpoints are rounded to the nearest representable. Therefore is not is not guaranteed that result will enclose given interval. The reason is that when you output interval to a file with high enough precision (at least 17 digits for double precision) than reading it will restore the original interval without overestimations.

Exact input and output

To save and restore intervals exactly you can use binary format or text formats in binary or hexadecimal bases.

   std::stringstream inout("", ios::binary | ios::in | ios::out );
   binWrite(inout, x);
   binRead(inout, a);

Text output in binary base

DInterval x(-1,2);
bitWrite(cout, x); 
bitRead(cin, x);

The output is [1:01111111111:0000000000000000000000000000000000000000000000000000, 0:10000000000:0000000000000000000000000000000000000000000000000000].

Endpoints have the following format sign:exponent:mantisa as in IEEE 754 standard.

Text output in hexadecimal base

DInterval x(-1,2);
hexWrite(cout, x); 
hexRead(cin, x);

The output is [1:3ff:0000000000000,0:400:0000000000000].

Arithmetic operators

Arithmetic operations for intervals are implemented in this way that their result always contains all possible results.

For example if

DInterval a(-1,0, 2.0), b(1.0, 2.0);

then

Operation	Code	Result
Sum	a + b;	[0.0, 4.0]
Substraction	a - b;	[-3.0, 1.0]
Product	a * b;	[-2.0, 4.0]
Division	a / b;	[-1.0, 2.0]

Note

If in division b contains 0 then an exception is thrown.

Every arithmetic operation of form

a = a + b;
a = a - b;
a = a * b;
a = a / b;

can be also shorten to

a += b;
a -= b;
a *= b;
a /= b;

Elementary functions

Most of the basic functions has its interval version. To be rigorous returned value is always an upper estimate of the true result. Functions are called exactly in the same way as its corresponding floating point versions.

List of all implemented functions:

Function	For an interval x it returns:
power(x, n)	xn, where n is an integer
power(x, a)	xa, where a is an interval
sqrt(x)	square root of x
sin(x), cos(x), tan(x), cot(x)	sinus of x, etc.
sinh(x), cosh(x), tanh(x), coth(x)	hyperbolic sinus of x, etc.
exp(x)	exponens of x
log(x)	natural logarithm of x

Logical operators and inclusions

Operator	True if
b==c;	both end points are the same.
b!=c;	at least one end point differs.
b>c; b>=c; b<c; b<=c;	it is true for any two points from intervals b and c. For example: b>c if leftBound(b) > rightBound(c).

The same operators can be applied if one of the intervals is replaced by a number (the number is treated as point interval) e.g. b == 1.0; b < 2.0;

Note

Both b>c and b<=c can be false at the same time e.g. in the case when intervals b and c overlap.

Inclusions

For two intervals one can check inclusions.

	True if
c.contains(b); c.contains(2.5);	c contains b c contains number 2.5
c.containsInInterior(b);	c contains b in the interior
c.subset(b);	c is subset of b
c.subsetInterior(b);	c is subset of the interior of b

Note

On standard output true is converted into integer value 1 and false into 0.

Interval specific functions

In this section we collect several useful functions.

• mid - middle point of the interval
  

  DInterval a(1.0, 5.0);
  std::cout << a.mid(); // displays on the screen [3.0,3.0] (the middle point of interval [1.0, 5.0])
  std::cout << mid(a);

• diam - an upper bound for the diameter of the interval
  

  DInterval a(1.0, 5.0);
  std::cout << diam(a); // displays on the screen [4.0, 4.0]

• width - non-rigorous width (diameter) of the interval
  

  DInterval a(1.0, 5.0);
  std::cout << width(a); // displays on the screen 4.0

• intersection - intersection of two intervals
  function bool intersection(a, b, result) for given two intervals a and b returns:
  • true and intersection in the result variable if intersecton is non empty.
  • false if intersection is empty.

  DInterval a(1.0, 3.0), b(2.0, 4.0), c(5.0, 6.0), r1, r2;
  intersection(a, b, r1);
  if(!intersection(a,c,r2))
     std::cout << "intersection is empty";
  // r1 is equal to [2.0, 3.0], r2 is not initialized

• intervalHull - interval hull of two given intervals
  For given two intervals iv1 and iv2 function intervalHull(iv1, iv2) returns the smallest possible interval containing iv1 and iv2

   DInterval a(1.0, 3.0), b(5.0, 6.0), result;
  result = intervalHull(a, b);
  // result is equal to [1.0, 6.0]

• imin, imax - minimum and maximum of two intervals
  for any element a of ia and any element b of ib we have that imin(ia,ib) contains min(a,b) and imax(ia,ib) contains max(a,b)

  DInterval ia(1.0, 10.0), ib(3.0, 5.0);
  imin(ia,ib);                  // result:  [1.0, 5.0]
  imax(ia,ib);                  // result:  [3.0, 10.0]

• iabs - interval containing absolute values of all elements of given interval
• split - splits interval into the center and the radius/the remainder
  There are 4 functions that split interval. They differ in the output.
  Suppose that we have

  DInterval a(1.0,3.0);
  interval center, remainder, radius;
  double r;

  then

  Command	Result
  a.split(center,remainder);	a = [1.0, 3.0] center = [2.0, 2.0] remainder = [-1.0, 1.0]
  a.split(remainder);	a = [2.0, 2.0] remainder = [-1.0, 1.0]
  split(a, center,radius);	a = [1.0, 3.0] center = [2.0, 2.0] radius = [1.0, 1.0]         !!!
  split(a, center,r);	a = [1.0, 3.0] center = [2.0, 2.0] radius = 1.0

Constants

Two constants : pi and euler are provided by static member fuctions pi and euler. Their output is an interval that containts true value of the constant.

Example:
// returns interval that contains pi constant
DInterval::pi();
 
// returns interval that contains euler constant
DInterval::euler();

Note

When using multiple precision endpoints, the returned value depends also on the precision currently used.

Interval Settings

The following applies only to native CAPD intervals and do not influence FILIB intervals. In file "capdAlg/include/capd/interval/IntervalSetting.h" there are several flags which can be switched on/off by (un)commenting appropriate line of code:

Flag	If switched on	Default
__DEBUGGING__	it turns on debugging mode. We check intervals  during each operation and throw exception if interval is not valid.	off
__INTERVAL_INIT_0__	default constructor initializes intervals to be [0.0,0.0]. By default this option is switched off and an interval is not initialized.	on
__INTERVAL_SPEED_OPTIMIZED__	it speeds up computations but enlarges programm size. It couses many functions to be defined as inline	on
__INTERVAL_DEPRECATED__	it allows use of deprecated functions for backward compatibility.	off