A class for an open interval providing interval arithmetic operations. More...

#include <OpenInterval.h>

Inheritance diagram for GiNaCRA::OpenInterval:

Collaboration diagram for GiNaCRA::OpenInterval:

Public Member Functions
	OpenInterval (const numeric &n)
	Constructs an open interval ]n-1, n+1[.
	OpenInterval (const numeric &l, const numeric &r) throw ( std::invalid_argument )
	Constructs an open interval ]l, r[.
	OpenInterval (const OpenInterval &i)
	Constructs an open interval from another.
	~OpenInterval ()
void	setLeft (const numeric &l) throw ( std::invalid_argument )
	Set new left bound for the interval.
void	setRight (const numeric &r) throw ( std::invalid_argument )
	Set new right bound for the interval.
const numeric	left () const
	Selects the left bound.
const numeric	right () const
	Selects the right bound.
const bool	isZero () const
const bool	isNormalized () const
const bool	contains (const numeric &n) const
const bool	contains (const OpenInterval &o) const
const bool	meets (const numeric &n) const
const OpenInterval	intersection (const OpenInterval &o) const
const numeric	midpoint () const
const numeric	sample () const
	Chooses a numeric value out of the interval with the smallest numeric representation.
const numeric	sampleFast () const
	Returns sample() if the bounds are small enough for machine computations and midpoint otherwise.
const OpenInterval	abs () const
	Computes the absolute value of this interval, i.e.
const OpenInterval	add (const OpenInterval &o) const
	Adds two intervals and returns their sum.
const OpenInterval	minus () const
	Returns the negative value.
const OpenInterval	mul (const OpenInterval &o) const
	Multiplies two intervals and returns their product.
const OpenInterval	div (const OpenInterval &o) const throw ( std::invalid_argument )
	Divides two intervals.
const OpenInterval	pow (unsigned e) const
	Computes the power to `e` of this interval.
const bool	isEqual (const OpenInterval &o) const
const bool	isLess (const OpenInterval &o) const
	Compares only the left bounds of the involved intervals.
const bool	isGreater (const OpenInterval &o) const
	Compares only the right bounds of the involved intervals.
Static Public Member Functions
static OpenInterval	evaluate (const ex &p, evalintervalmap m) throw ( std::invalid_argument )
Protected Member Functions
bool	is_equal_same_type (const basic &) const
void	do_print (const print_context &, unsigned level=0) const
ex	evalf (int level=0) const
unsigned	calchash () const
Static Private Member Functions
static const numeric	findSample (cln::cl_I numeratorL, cln::cl_I denominatorL, cln::cl_I numeratorR, cln::cl_I denominatorR)
	Finds a number t between l:=numeratorL/denominatorL and r:=numeratorR/denominatorR so that t has a minimal number of digits.
static const numeric	findSample (long numeratorL, long denominatorL, long numeratorR, long denominatorR)
	Finds a number t between l:=numeratorL/denominatorL and r:=numeratorR/denominatorR so that t has a minimal number of digits.
Private Attributes
numeric	mLeft
numeric	mRight

Detailed Description

A class for an open interval providing interval arithmetic operations.

All operations are performed in constant time.

Author:: Ulrich Loup

Since:: 2010-08-03

Version:: 2012-05-14

See also:: ISBN 0-387-94090-1 and ISBN-13: 978-3642069642

Definition at line 55 of file OpenInterval.h.

Constructor & Destructor Documentation

GiNaCRA::OpenInterval::OpenInterval ( const numeric & n )

Constructs an open interval ]n-1, n+1[.

Parameters:

n middle

Definition at line 71 of file OpenInterval.cpp.

Referenced by abs(), add(), intersection(), minus(), mul(), and pow().

GiNaCRA::OpenInterval::OpenInterval	(	const numeric &	l,
		const numeric &	r
	)		throw ( std::invalid_argument )

Constructs an open interval ]l, r[.

Parameters:

l	left bound of the open interval ]l, r[
r	right bound of the open interval ]l, r[

Definition at line 78 of file OpenInterval.cpp.

GiNaCRA::OpenInterval::OpenInterval ( const OpenInterval & i )

Constructs an open interval from another.

Parameters:

i	other open interval

Definition at line 90 of file OpenInterval.cpp.

GiNaCRA::OpenInterval::~OpenInterval ( )

Definition at line 97 of file OpenInterval.cpp.

Member Function Documentation

const OpenInterval GiNaCRA::OpenInterval::abs ( ) const

Computes the absolute value of this interval, i.e.

the maximum of the absolute values of its bounds.

Returns:: absolute value of the interval

See also:: Marc Daumas, Guillaume Melquiond, and Cesar Munoz - "Guaranteed Proofs Using Interval Arithmetic".

Definition at line 270 of file OpenInterval.cpp.

References mLeft, mRight, OpenInterval(), and GiNaC::sgn().

const OpenInterval GiNaCRA::OpenInterval::add ( const OpenInterval & o ) const

Adds two intervals and returns their sum.

Parameters:

o

Returns:: sum

Definition at line 283 of file OpenInterval.cpp.

References mLeft, mRight, and OpenInterval().

Referenced by GiNaCRA::operator+(), and GiNaCRA::operator-().

unsigned GiNaCRA::OpenInterval::calchash ( ) const [protected]

Definition at line 146 of file OpenInterval.cpp.

References mLeft, and mRight.

const bool GiNaCRA::OpenInterval::contains ( const numeric & n ) const

Parameters:

n

Returns:: true in case n is contained in this OpenInterval

Definition at line 179 of file OpenInterval.cpp.

References mLeft, and mRight.

Referenced by GiNaCRA::RationalUnivariatePolynomial::approximateRealRoot(), GiNaCRA::RealAlgebraicNumberIR::normalizeInterval(), GiNaCRA::RealAlgebraicNumberIR::operator=(), and GiNaCRA::RealAlgebraicNumberIR::refineAvoiding().

const bool GiNaCRA::OpenInterval::contains ( const OpenInterval & o ) const

Parameters:

o

Returns:: true in case o is a subset of this OpenInterval

Definition at line 184 of file OpenInterval.cpp.

References mLeft, and mRight.

const OpenInterval GiNaCRA::OpenInterval::div ( const OpenInterval & o ) const throw ( std::invalid_argument )

Divides two intervals.

Parameters:

o

Returns:: this interval divided by the argument

Exceptions:

invalid_argument in case the argument interval contains zero

Definition at line 315 of file OpenInterval.cpp.

References mLeft.

void GiNaCRA::OpenInterval::do_print	(	const print_context &	c,
		unsigned	level = `0`
	)		const `[protected]`

Definition at line 154 of file OpenInterval.cpp.

References mLeft, and mRight.

ex GiNaCRA::OpenInterval::evalf ( int level = 0 ) const [protected]

Definition at line 159 of file OpenInterval.cpp.

References mLeft, and mRight.

OpenInterval GiNaCRA::OpenInterval::evaluate	(	const ex &	p,
		evalintervalmap	m
	)		throw ( std::invalid_argument ) `[static]`

Parameters:

p
m

Returns:

Use Horner's method to perform the interval-arithmetic operations according to the polynomial p in the variable s.

Definition at line 348 of file OpenInterval.cpp.

Referenced by GiNaCRA::RealAlgebraicNumberFactory::evaluateIR(), and GiNaCRA::RealAlgebraicNumberFactory::realRootsEval().

const numeric GiNaCRA::OpenInterval::findSample	(	cln::cl_I	numeratorL,
		cln::cl_I	denominatorL,
		cln::cl_I	numeratorR,
		cln::cl_I	denominatorR
	)		`[inline, static, private]`

Finds a number t between l:=numeratorL/denominatorL and r:=numeratorR/denominatorR so that t has a minimal number of digits.

The algorithm uses cln arithmetic operations only.

Parameters:

numeratorL
denominatorL
numeratorR
denominatorR

Returns:

Definition at line 412 of file OpenInterval.cpp.

References GiNaC::denominator(), GiNaC::gcd(), GiNaC::lcm(), and GiNaC::numerator().

Referenced by sample().

const numeric GiNaCRA::OpenInterval::findSample	(	long	numeratorL,
		long	denominatorL,
		long	numeratorR,
		long	denominatorR
	)		`[inline, static, private]`

Finds a number t between l:=numeratorL/denominatorL and r:=numeratorR/denominatorR so that t has a minimal number of digits.

The algorithm uses machine integer arithmetic only.

Parameters:

numeratorL
denominatorL
numeratorR
denominatorR

Returns:

Definition at line 447 of file OpenInterval.cpp.

References GiNaC::denominator(), GiNaC::gcd(), GiNaC::lcm(), and GiNaC::numerator().

const OpenInterval GiNaCRA::OpenInterval::intersection ( const OpenInterval & o ) const

Parameters:

o

Returns:: intersection with the given OpenInterval and this OpenInterval, or (0, 0) in case the intersection is empty

Definition at line 194 of file OpenInterval.cpp.

References mLeft, mRight, and OpenInterval().

bool GiNaCRA::OpenInterval::is_equal_same_type ( const basic & o ) const [protected]

Definition at line 140 of file OpenInterval.cpp.

References isEqual().

const bool GiNaCRA::OpenInterval::isEqual ( const OpenInterval & o ) const

Parameters:

o

Returns:: true in case the other interval equals this

Definition at line 381 of file OpenInterval.cpp.

References mLeft, and mRight.

Referenced by is_equal_same_type(), GiNaCRA::operator!=(), and GiNaCRA::operator==().

const bool GiNaCRA::OpenInterval::isGreater ( const OpenInterval & o ) const

Compares only the right bounds of the involved intervals.

Parameters:

o

Returns:: true in case the other interval is greater then this

----------]------------[------- >= -----]------------[------------ or ----------]------------[------- >= -------------]----[------------ holds.

Definition at line 397 of file OpenInterval.cpp.

References mRight.

Referenced by GiNaCRA::operator>=().

const bool GiNaCRA::OpenInterval::isLess ( const OpenInterval & o ) const

Compares only the left bounds of the involved intervals.

Parameters:

o

Returns:: true in case the other interval is less then this

-----]------------[------------ <= ----------]------------[------- or -----]------------[------------ <= ----------]-----[-------------- holds.

Definition at line 386 of file OpenInterval.cpp.

References mLeft.

Referenced by GiNaCRA::operator<=().

const bool GiNaCRA::OpenInterval::isNormalized ( ) const

Returns:: true in case the interval is zero or it does not contain zero and its right bound is not zero itself (for root order determination)

Definition at line 174 of file OpenInterval.cpp.

References mLeft, and mRight.

const bool GiNaCRA::OpenInterval::isZero ( ) const

Returns:: true in case the bounds of the interval are both zero

Definition at line 169 of file OpenInterval.cpp.

References mLeft, and mRight.

Referenced by GiNaCRA::RealAlgebraicNumberIR::add(), GiNaCRA::RealAlgebraicNumberIR::is_equal_same_type(), GiNaCRA::RealAlgebraicNumberIR::isEqual(), GiNaCRA::RealAlgebraicNumberIR::minus(), GiNaCRA::RealAlgebraicNumberIR::mul(), GiNaCRA::RealAlgebraicNumberIR::normalizeInterval(), GiNaCRA::RealAlgebraicNumberFactory::realRootsEval(), and GiNaCRA::RealAlgebraicNumberIR::sgn().

const numeric GiNaCRA::OpenInterval::left ( ) const

Selects the left bound.

Returns:: numeric

Definition at line 115 of file OpenInterval.cpp.

References mLeft.

const bool GiNaCRA::OpenInterval::meets ( const numeric & n ) const

Parameters:

n

Returns:: true in case n meets the interval bounds or a point inbetween

Definition at line 189 of file OpenInterval.cpp.

Referenced by GiNaCRA::RealAlgebraicNumberIR::refineAvoiding().

const numeric GiNaCRA::OpenInterval::midpoint ( ) const

Returns:: the midpoint of this interval

Definition at line 212 of file OpenInterval.cpp.

References mLeft, and mRight.

Referenced by GiNaCRA::RealAlgebraicNumberIR::approximateValue(), GiNaCRA::RealAlgebraicNumberIR::evalf(), GiNaCRA::RealAlgebraicNumberIR::refine(), sampleFast(), and GiNaCRA::RealAlgebraicNumberFactory::searchRealRoots().

const OpenInterval GiNaCRA::OpenInterval::minus ( ) const

Returns the negative value.

Returns:: negative value

Definition at line 288 of file OpenInterval.cpp.

References mLeft, mRight, and OpenInterval().

Referenced by GiNaCRA::operator-().

const OpenInterval GiNaCRA::OpenInterval::mul ( const OpenInterval & o ) const

Multiplies two intervals and returns their product.

Parameters:

o

Returns:: product

Definition at line 293 of file OpenInterval.cpp.

References mLeft, mRight, and OpenInterval().

Referenced by GiNaCRA::operator*().

const OpenInterval GiNaCRA::OpenInterval::pow ( unsigned e ) const

Computes the power to e of this interval.

Parameters:

e exponent

Returns:: power to e of this interval

Definition at line 339 of file OpenInterval.cpp.

References mLeft, mRight, and OpenInterval().

const numeric GiNaCRA::OpenInterval::right ( ) const

Selects the right bound.

Returns:: numeric

Definition at line 120 of file OpenInterval.cpp.

References mRight.

const numeric GiNaCRA::OpenInterval::sample ( ) const

Chooses a numeric value out of the interval with the smallest numeric representation.

The core algorithm works with machine integer arithmetic whenever possible.

Runtime complexity:: O( lcm( denominator( Left() ) * denominator( Right() ) )^2 )

Returns:: a sample value with a minimal numeric representation

Goal: Compute a rational number within the isolating interval with the smallest number representation.

Definition at line 217 of file OpenInterval.cpp.

References GiNaC::denominator(), findSample(), mLeft, mRight, and GiNaC::numerator().

Referenced by GiNaCRA::RealAlgebraicNumberIR::refine(), sampleFast(), GiNaCRA::RealAlgebraicNumberIR::sampleValue(), and GiNaCRA::RealAlgebraicNumberFactory::searchRealRoots().

const numeric GiNaCRA::OpenInterval::sampleFast ( ) const [inline]

Returns sample() if the bounds are small enough for machine computations and midpoint otherwise.

Returns:: sample() if the bounds are small enough for machine computations and midpoint otherwise

Definition at line 170 of file OpenInterval.h.

References GiNaCRA::RealAlgebraicNumberSettings::MAX_FASTSAMPLE_BOUND, midpoint(), mLeft, mRight, and sample().

Referenced by GiNaCRA::RealAlgebraicNumberIR::refineAvoiding().

void GiNaCRA::OpenInterval::setLeft ( const numeric & l ) throw ( std::invalid_argument )

Set new left bound for the interval.

Parameters:

l	new left bound

Definition at line 103 of file OpenInterval.cpp.

Referenced by GiNaCRA::RealAlgebraicNumberIR::normalizeInterval(), GiNaCRA::RealAlgebraicNumberIR::refine(), and GiNaCRA::RealAlgebraicNumberIR::refineAvoiding().

void GiNaCRA::OpenInterval::setRight ( const numeric & r ) throw ( std::invalid_argument )

Set new right bound for the interval.

Parameters:

r	new right bound

Definition at line 109 of file OpenInterval.cpp.

Referenced by GiNaCRA::RealAlgebraicNumberIR::normalizeInterval(), GiNaCRA::RealAlgebraicNumberIR::refine(), and GiNaCRA::RealAlgebraicNumberIR::refineAvoiding().

Field Documentation

numeric GiNaCRA::OpenInterval::mLeft [private]

Definition at line 266 of file OpenInterval.h.

Referenced by abs(), add(), calchash(), contains(), div(), do_print(), evalf(), intersection(), isEqual(), isLess(), isNormalized(), isZero(), left(), midpoint(), minus(), mul(), pow(), sample(), and sampleFast().

numeric GiNaCRA::OpenInterval::mRight [private]

Definition at line 267 of file OpenInterval.h.

Referenced by abs(), add(), calchash(), contains(), do_print(), evalf(), intersection(), isEqual(), isGreater(), isNormalized(), isZero(), midpoint(), minus(), mul(), pow(), right(), sample(), and sampleFast().

The documentation for this class was generated from the following files:

Public Member Functions

Static Public Member Functions

Protected Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Field Documentation