CGAL 6.1  Number Types

This chapter gives an overview of the number types supported by CGAL. Number types must fulfill certain syntactical and semantic requirements, such that they can be successfully used in CGAL code. In general they are expected to be a model of an algebraic structure concepts and in case they model a subring of the real numbers they are also a model of RealEmbeddable
. For an overview of the algebraic structure concepts see Section Algebraic Foundations Reference.
The builtin number types float
, double
and long double
have the required arithmetic and comparison operators. They lack some required routines though which are automatically included by CGAL. The functions can be found in the header files CGAL/int.h
, CGAL/float.h
, CGAL/double.h
and CGAL/long_long.h
.
All builtin number types of C++ can represent a discrete (bounded) subset of the rational numbers only. We assume that the floatingpoint arithmetic of your machine follows IEEE floatingpoint standard. Since the floatingpoint 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 builtin number types are inherently potentially inexact. Be aware of this if you decide to use the efficient builtin 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 builtin integer types overflow might occur.
CGAL provides several number types 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 parameterized with a number type which can represent integers.
The number type MP_Float
is able to represent multiprecision floating point values, a generalization of integers scaled by a (potentially negative) power of 2. It allows to deal with ring operations over floatingpoint values with requiring rational numbers. By plugging it in Quotient
, one obtains rational numbers. Note that MP_Float
may not be as efficient as the integer types provided by GMP or LEDA, but it has the advantage to make more parts of CGAL independent on these external libraries for handling robustness issues.
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 NT
.
A number type for doing interval arithmetic, Interval_nt
, is provided. This number type helps in doing arithmetic filtering in many places such as Filtered_predicate
.
Sqrt_extension
is a number type that allows to represent algebraic numbers of degree 2 as well as nested forms. A generic function make_root_of_2()
allows to build this type generically.
A debugging helper Number_type_checker<NT1,NT2,Comparator>
is also provided which allows to compare the behavior of operations over two number types.
CGAL provides wrapper classes for number types defined in the GNU Multiple Precision arithmetic library [2]. The file CGAL/Gmpz.h
provides the class Gmpz
, a wrapper class for the arbitraryprecision integer type mpz_t
, which is compliant with the CGAL number type requirements. The file CGAL/Gmpq.h
provides the class Gmpq
, a wrapper class for the arbitraryprecision rational type mpq_t
, which is compliant with the CGAL number type requirements.
The file CGAL/Gmpzf.h
provides the class Gmpzf
, an exact arbitraryprecision floatingpoint type. Hence, It does not support operators like /
to guarantee exactness of the operations. The arithmetic operations on this type are restricted to +
, 
, *
and integral_division()
. On some platforms, the file CGAL/Mpzf.h
provides the class Mpzf
, a faster alternative to Gmpzf
that doesn't support integral_division()
.
The file CGAL/Gmpfr.h
provides the class Gmpfr
, a fixedprecision floatingpoint number type. Since the precision (number of bits used to represent the mantissa of the number) is fixed for each object, the result of each operation is rounded when necessary. Though not necessary at first, the user will take full advantage of this number type by understanding the ideas behind floatingpoint arithmetic, such as precision and rounding, and understanding the flags set by this library after each operation. For more details, the reader should refer to [5] and the Gmpfr
reference manual.
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 these classes, GMP and MPFR 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 builtin 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 floatingpoint 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 floatingpoint numbers, the name leda_real
does not describe the number type precisely, but intentionally. leda_real
is a subset of real algebraic numbers. Any integer is leda_real
and leda_real
is closed under the operations \( +,,*,/\) and \( k\)th root computation. For LEDA version 5.0 and or later leda_real
is also able to represent real roots of polynomials. leda_real
s guarantee that all comparisons between expressions involving leda_real
produce the exact result.
The files CGAL/leda_integer.h
, CGAL/leda_rational.h
, CGAL/leda_bigfloat.h
and CGAL/leda_real.h
provide the necessary functions to make these classes compliant to the CGAL number type requirements.
In principle Core [3] provides the same set of number types as LEDA. The type CORE::BigInt
represent integers and CORE::BigRat
represent rationals of arbitrary length. The number type CORE::BigFloat
is a variable precision floatingpoint type. It is also possible to interpret it as an interval type, since it also carries the error of a computed value. As for LEDA, the most sophisticated number type in Core is CORE::Expr
, which is in its functionality equivalent to leda_real
.
Interval arithmetic is very important for geometric programming. It is a fundamental tool for filtering predicates. For many problems, intervals of machine doubleprecision numbers are sufficient, but it is not always enough. For example, one approach for determining the sign of an expression is to evaluate its sign using interval arithmetic and to repeatedly increase the precision of the bounds of the intervals until either the interval does not contain zero or its width is less than the separation bound of the polynomial.
For intervals of machine doubleprecision numbers, CGAL provides the class Interval_nt
. For intervals of floatingpoint arbitraryprecision numbers, CGAL provides the class Gmpfi
.
Endpoints of Gmpfi
intervals are represented as Gmpfr
numbers. Each interval has an associated precision, which is the maximum precision (number of bits used to represent the mantissa) of its endpoints. The result of the operations is guaranteed to be always contained in the returned interval. Since the interval arithmetic is implemented on top of Gmpfr
, the global flags are inherited from the Gmpfr
interface. See [4] and the Gmpfi
reference manual for details.
To use the Gmpfi
class, MPFI must be installed.
In order to use your own number type it must be a model of the according algebraic structure concept, in particular you must provide a specialization of Algebraic_structure_traits
and also of Real_embeddable_traits
in case it is a sub ring of the real numbers. If you even want to provide a related ensemble of number types you should also provide specializations for Coercion_traits
in order to reflect their interoperability.
This package was naturally one of the first packages implemented in CGAL. It initially contained the Quotient
, Gmpz
and Gmpq
classes, together with the interfaces to the number types provided by LEDA, which were implemented by Stefan Schirra and Andreas Fabri. LEDA's class rational
has been the basis for Quotient
.
Later, around 19982002, Sylvain Pion implemented Interval_nt
, MP_Float
and Lazy_exact_nt
, together with the interfaces to the mpz_class
and mpq_class
types from GMP.
Number type concepts were then refined, notably by Lutz Kettner and Susan Hert, who also contributed utility algorithms.
The work on concepts was further extended within the Exacus project, and was finally contributed to CGAL by Michael Hemmer in 2006, as what is now the separate package Algebraic Foundations, together with a rewritten interface to operations on number types.
The class Sqrt_extension
was contributed by Michael Hemmer and Ron Wein around 2006. In 2010 it went through a considerable reinvestigation by Sébastien Loriot, Michael Hemmer, and Monique Teillaud. As a result it got further improved and now replaces several similar types such as Root_of_2
, which had been contributed by Pedro M. M. de Castro, Sylvain Pion and Monique Teillaud, and is deprecated since CGAL3.8.
In 20082010, Bernd Gärtner added the Gmpzf
class, while Luis Peñaranda and Sylvain Lazard contributed the Gmpfi
and Gmpfr
classes.