advanced

CGAL::Interval_nt_advanced

Definition

The advanced class allows you to make faster computations with interval arithmetic, but you need to set the rounding mode of the FPU to 'round to infinity' (see below for how to do that) before doing any computation with this number type, and each function (arithmetic operators and conversion functions) leaves the rounding mode in this state if it needs to modify it internally.

Changing the rounding mode affects all floating point computations, and might cause problems with parts of your code, or external libraries (even CGAL), that expect the rounding mode to be the default (round to the nearest).

#include <CGAL/Interval_arithmetic.h>

Is Model for the Concept

Operations

Interval_nt_advanced convert_to<
	Interval_nt_advanced> ( NT)
		Several such functions provide a cast from the following numerical types to an Interval_nt_advanced containing the value. The following types are supported: leda_real, leda_rational, leda_integer, leda_bigfloat, Gmpz, Fixed_precision_nt, all built-in types that fit exactly in a double (which excludes long double and 64 bits integers, which must be treated separately), and all Quotient<RT> where RT is a type listed above. The user can add such functions for his own number types, see the files CGAL/Interval_arithmetic/IA_*.h for examples.

We provide the following interface to change the rounding mode:

typedef int	FPU_CW_t;	The type used by the following functions to deal with rounding modes. This is usually an int.
void	FPU_set_cw ( FPU_CW_t R)
		sets the rounding mode to R.
FPU_CW_t	FPU_get_cw ( void)	returns the current rounding mode.
FPU_CW_t	FPU_get_and_set_cw ( FPU_CW_t R)
		sets the rounding mode to R and returns the old one.

The macros CGAL_FE_TONEAREST, CGAL_FE_TOWARDZERO, CGAL_FE_UPWARD and CGAL_FE_DOWNWARD are the values corresponding to the rounding modes.

Example

The correct way to protect an area of code that uses operations on the class Interval_nt_advanced is the following:

  FPU_CW_t backup = FPU_get_and_set_cw(CGAL_FE_UPWARD);
  ... // The code to be protected.
  FPU_set_cw(backup);

Implementation

The basic idea is to use the directed rounding modes specified by the IEEE 754 standard, which are implemented by almost all processors nowadays. It states that you have the possibility, concerning the basic floating point operations ($$+,-,*,/,sqrt()) to specify the rounding mode of each operation instead of using the default, which is set to 'round to the nearest'. This feature allows us to compute easily on intervals. For example, to add the two intervals [a.i;a.s] and [b.i;b.s], compute $$c.i=a.i+b.i rounded towards minus infinity, and $$c.s=a.s+b.s rounded towards plus infinity, and the result is the interval [c.i;c.s]. This method can be extended easily to the other operations.

The problem is that we have to change the rounding mode very often, and the functions of the C library doing this operation are slow and not portable. That's why assembly versions are used as often as possible. Another trick is to store the opposite of the lower bound, instead of the lower bound itself, which allows us to never change the rounding mode inside simple operations. Therefore, all basic operations, which are in the class Interval_nt_advanced assume that the rounding mode is set to 'round to infinity', and everything works with this correctly set. The class Interval_nt takes care of this, but is a bit slower.

So, if the user needs the speed of Interval_nt_advanced, he must take care of setting the rounding mode to 'round to infinity' before each block of operations on this number type. And if other operations might be affected by this, he must take care to reset it to 'round to the nearest' before they are executed.

Notes:

• On Intel platforms (with any operating system and compiler), due to a misfeature of the floating point unit, which does not handle exactly IEEE compliant operations on doubles, we are forced to use a workaround which slows down the code, but is only useful when the intervals can overflow or underflow. If you know that the intervals will never overflow nor underflow for your code, then you can disable this workaround with the flag CGAL_IA_NO_X86_OVER_UNDER_FLOW_PROTECT. Other platforms are not affected by this flag.
• When optimizing, compilers usually propagate the value of variables when they know it's a constant. This can break the interval routines because the compiler then does some floating point operations on these constants with the default rounding mode, which is wrong. This kind of problem is avoided by stopping constant propagation in the interval routines. However, this solution slows down the code and is rarely useful, so you can disable it by setting the flag CGAL_IA_DONT_STOP_CONSTANT_PROPAGATION.

advanced