Number Type Support

CGAL kernel classes are parameterized by number types. Depending on the problem and the input data that have to be handled, one has to make a trade-off between efficiency and accuracy in order to select an appropriate number type and kernel class.

In homogeneous representation, two number types are involved,
although only one of them appears as a template parameter in
the homogeneous kernel classes.
This type, for the sake of simplicity and readability called ring type, is
used for the representation of homogeneous coordinates and all
internal computations.
If it is assured that the second operand divides the first one, these
internal computations are basically division-free.
The ring type is a placeholder for an integer type (or an integral
domain type) rather than for elements of arbitrary rings.
The name should remind you that the division operation is not
needed for this number type.
Of course, also more general number types can be used as a ring type
in a homogeneous kernel class. In some computations, e.g. accessing
Cartesian coordinates, divisions cannot be avoided. In these computations a
second number type, the field type, is used. CGAL automatically generates
this number type as a *Quotient*. For the Cartesian kernels
there is only one number type that is used for all calculations.

The kernel classes provide access to the number types
involved in the representation, although it is not expected that
such access is needed at this level, since low-level geometric
operations are wrapped in geometric primitives provided by CGAL.
This access can be useful if appropriate primitives are missing.
In a homogeneous kernel class *K*, ring type and field
type can be accessed as *K::RT* and *K::FT*, respectively.
The number type used in Cartesian kernels is considered as
ring type or as field type depending on the context.
If can be accessed as *K::RT* and *K::FT*, according
to the use of number types used in the homogeneous counterpart.

Number types must fulfill certain requirements, such that they can be successfully used in CGAL code. The syntacitical requirements of number types are described in the concepts RingNumberType and FieldNumberType included in the kernel reference manual. Of course, number types also have evident semantic constraints. They should be meaningful in the sense that they approximate the integers or the rationals or some other subfield of the real numbers.

The number type concepts mentioned in the previous section list all the required functionality. For the user of a number type it is handy to have a larger set of operations available. CGAL defines a number of such operations, to compute, for example, the minimum or maximum of two numbers, and the absolute value, square, sign or square root of a number. These are available both as global functions and as functors. See the reference manual for more details.

Those routines are implemented using the required operations from the number type concepts. They are defined by means of templates, so you do not have to supply all those operations when you write a new number type. But if you have a better implementation for any of them, you can provide a corresponding overloading function with the same name for your number types, which will get preference over the template functions listed above.

For the number types *int*, and *double* there is
also a random numbers generator *CGAL::Random*.

The built-in number types *float* and *double* have the
required arithmetic and comparison operators. They lack some required
routines though which are automatically included by CGAL.

All built-in number types of C++ can represent a discrete (bounded)
subset of the rational numbers only. We assume that the
floating-point arithmetic of your machine follows IEEE
floating-point standard. Since the floating-point culture has much
more infrastructural support (hardware, language definition and
compiler) than exact computation, it is very efficient.
Like with all number types with finite precision representation
which are used as approximations to the infinite ranges of
integers or real numbers, the built-in number types are inherently
potentially inexact.
Be aware of this if you decide to use the efficient built-in
number types: you have to cope with numerical problems.
For example, you can compute the intersection point of two lines and
then check whether this point lies on the two lines.
With floating point arithmetic,
roundoff errors may cause the answer of the check to be *false*.
With the built-in integer types overflow might occur.

CGAL provides several number types that are that can be used for
exact computation. These include the *Quotient* class that can
be used to create, for example, a number type that behaves like a rational
number. When used in conjunction with the number type *MP_Float* that
is able to represent multi-precision floating point values, you achieve
an exact rational number representation. The templated number type
*Lazy_exact_nt<NT>* is able to represent any number that *NT* is able
to represent, but because it first tries to use an approximate value to
perform computations it can be faster than the provided number type *NT*.
CGAL also provides a fixed-precision number type,
*Fixed_precision_nt* that provides 24-bit numbers in fixed point
representation. This number type provides some specialized predicates
that are exact and efficient for numbers known to be representable using
24 bits.
Two number types for doing interval arithmetic, *Interval_nt* and
*Interval_nt_advanced*, are also provided. These number types
help in doing filtering of predicates.

CGAL defines the functions needed to use the number type *CORE::Expr*
provided by CORE [KLPY99]. To use CORE with CGAL, just
install CGAL with CORE support, and include the file
*CGAL/CORE_Expr.h*. CORE version 1.5 or later is required.

*CORE::Expr*s are a subset of real algebraic numbers. Any integer is a
*CORE::Expr* and *CORE::Expr*s are closed under the operations
$$*+,-, × ,/* and $$*sqrt()*. *CORE::Expr*s guarantee that all
comparisons between expressions involving *CORE::Expr*s produce the exact
result.

This number type provides an equivalent functionality to *leda_real*.

CGAL provides wrapper classes for number types defined in the
GNU Multiple Precision arithmetic library [Gra].
The file `CGAL/Gmpz.h` provides the class *Gmpz*,
a wrapper class for the integer type *mpz_t*, that is compliant with the
CGAL number type requirements. The file `CGAL/Gmpq.h` provides the class *Gmpq*,
a wrapper class for the rational type *mpq_t*, that is compliant
with the
CGAL number type requirements.

In addition, it is possible to directly use the C++ number types provided by
GMP : *mpz_class*, *mpq_class* (note that support for
*mpf_class* is incomplete). The file `CGAL/gmpxx.h` provides the
necessary functions to make these classes compliant to the CGAL number type
requirements.

To use this, GMP must be installed.

LEDA provides number types that can be used for exact computation
with both Cartesian and homogeneous representations. If you are using
homogeneous representation with the built-in integer types
*short*, *int*, and *long* as ring type, exactness of
computations can be guaranteed only if your input data come from a
sufficiently small integral range and the depth of the computations is
sufficiently small. LEDA provides the number type *leda_integer* for
integers of arbitrary length. (Of course the length is
somehow bounded by the resources of your computer.) It can be used as
ring type in homogeneous kernels and leads to exact
computation as long as all intermediate results are rational. For the
same kind of problems, Cartesian representation with number type
*leda_rational* leads to exact computation as well.
The number type *leda_bigfloat* in LEDA is a variable precision
floating-point type. Rounding mode and precision (i.e. mantissa length) of
*leda_bigfloat* can be set.

The most sophisticated number type in LEDA is the number type called
*leda_real*. Like in Pascal, where the name *real* is used for
floating-point numbers, the name *leda_real* does not describe the
number type precisely, but intentionally.
*leda_real*s are a subset of real algebraic
numbers. Any integer is *leda_real* and *leda_real*s are closed under
the operations $$*+,-,*,/* and $$*k*-th root computation.
*leda_real*s guarantee that
all comparisons between expressions involving *leda_real*s produce the
exact result.

You can also use your own number type with the CGAL kernel classes, e.g. the BIGNUM package [SVH89]. Depending on the arithmetic operations carried out by the algorithms that you are going to use, the number types must fulfill the corresponding requirements from Section .

Next chapter: Number Type Support

The CGAL Project .
Tue, December 21, 2004 .