next up previous contents index
Next: Modular Arithmetic in LEDA Up: Number Types and Linear Previous: The data type real   Contents   Index


Interval Arithmetic in LEDA ( interval )

Definition

An instance of the data type interval represents a real interval I = [a, b]. The basic interval operations + , - ,*,/,$ \sqrt{{\phantom{x}}}$ are available. Type interval can be used to approximate exact real arithmetic operations by inexact interval operations, as follows. Each input number xi is converted into the interval {xi} and all real operations are replaced by interval operations. If x is the result of the exact real calculation and I the interval computed by type interval, it is guaranteed that I contains x. I can be seen as a more or less accurate approximation of x. In many cases the computed interval I is small enough to provide a useful approximation of x and the exact sign of x. There are four different implementations of intervals (consult the implementation section below for details):

The interface of all interval variants are identical. However, note that the types interval_round_inside and interval_round_outside are only available on some explicitly supported UNIX platforms, currently including SPARC, MIPS, i386 (PC's compatible to 80386 or higher), and ALPHA. For all platforms, the name interval stands for the default implementation interval_bound_absolute.

#include < LEDA/numbers/interval.h >

interval x creates an instance x of type interval and initializes it with the interval {0}

interval x(VOLATILE_I double a) creates an instance x of type interval and initializes it with {a}

interval x(int a) creates an instance x of type interval and initializes it with {a}

interval x(long a) creates an instance x of type interval and initializes it with {a}

interval x(const integer& a) creates an instance x of type interval and initializes it with the smallest possible interval containing a

interval x(const bigfloat& a) creates an instance x of type interval and initializes it with the smallest possible interval containing a

interval x(const real& a) creates an instance x of type interval and initializes it with the smallest possible interval containing a

interval x(const rational& a) creates an instance x of type interval and initializes it with the smallest possible interval containing a

Operations

The arithmetic operations +,-,*,/,sqrt,+=,-=,*=,/= and the stream operators are all available. Important: If the advanced implementation interval_round_outside is used, the user has to guarantee that for each interval operation the IEEE754 rounding mode ''towards + $ \infty$'' is active. This can be achieved by calling the function fpu::round_up(). To avoid side effects with library functions that require the default IEEE754 rounding mode to_nearest, the function fpu::round_nearest() can be used to reset the rounding mode.

double x.to_double() returns the midpoint of the interval x as an approximation for the exact real number represented by x.

double x.get_double_error() returns the diameter of the interval x which is the maximal error of the approximation x.to_double() of the exact real number represented by x.

bool x.is_a_point() returns true if and only if the interval x consists of a single point.

bool x.is_finite() returns true if and only if the interval x is a finite interval.

bool x.contains(double x) returns true if and only if the interval x contains the number x

double x.upper_bound() returns the upper bound of the interval x.

double x.lower_bound() returns the lower bound of the interval x.

void x.set_range(VOLATILE_I double x, VOLATILE_I double y)
    sets the current interval to [x, y].

void x.set_midpoint(VOLATILE_I double num, VOLATILE_I double error)
    sets the current interval to a superset of [num - error, num + error], i.e., to an interval with midpoint num and radius error.

bool x.sign_is_known() returns true if and only if all numbers in the interval x have the same sign

int x.sign() returns the sign of all numbers in the interval x if this sign is unique; aborts with an error message if x.sign_is_known() gives false

Implementation

The types interval_round_inside and interval_round_outside represent intervals directly by (the negative of) its lower bound and its upper bound as doubles. Here all arithmetic operations require that the IEEE754 rounding mode ''towards + $ \infty$'' is active. For type interval_round_inside this is done inside each operation, and for type interval_round_outside the user has to do this manually ''from outside the operations'' by an explicit call of fpu::round_up().

The types interval_bound_absolute and interval_bound_relative represent intervals by their double midpoint NUM and diameter ERROR. The interpretation is that NUM is the numerical approximation of a real number and ERROR is a bound for the absolute, respectively relative error of NUM.


next up previous contents index
Next: Modular Arithmetic in LEDA Up: Number Types and Linear Previous: The data type real   Contents   Index
root 2008-01-09