Chapter 6
Number Types

Michael Hemmer, Susan Hert, Lutz Kettner, Sylvain Pion, and Stefan Schirra

Table of Contents

6.1 Introduction
6.2 Built-in Number Types
6.3 Number Types Provided by CGAL
6.4 Number Types Provided by GMP
6.5 Number Types Provided by LEDA
6.6 Number Types Provided by CORE
6.7 User-supplied Number Types

6.1   Introduction

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 5.7.

6.2   Built-in Number Types

The built-in 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. 1

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.

6.3   Number Types Provided by CGAL

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 multi-precision floating point values, a generalization of integers scaled by a (potentially negative) power of 2. It allows to deal with ring operations over floating-point 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.

CGAL::Root_of_2 is a number type that allows to represent algebraic numbers of degree up to 2 over a RingNumberType. A generic function CGAL::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.

6.4   Number Types Provided by GMP

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.

The file CGAL/Gmpzf.h provides the class Gmpzf, an exact floating-point type based on mpz_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.

6.5   Number Types Provided by LEDA

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_reals are a subset of real algebraic numbers. Any integer is leda_real and leda_reals are 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_reals guarantee that all comparisons between expressions involving leda_reals 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.

6.6   Number Types Provided by CORE

In principle CORE [KLPY99] 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 floating-point 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.

The files CGAL/CORE_BigInt.h, CGAL/CORE_BigRat.h, CGAL/CORE_BigFloat.h and CGAL/CORE_Expr.h provide the necessary functions to make these classes compliant to the CGAL number type requirements.

CORE version 1.7 or later is required.

6.7   User-supplied Number Types

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 CGAL::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 CGAL::Coercion_traits in order to reflect their interoperability.


Footnotes

 1  The functions can be found in the header files CGAL/int.h, CGAL/float.h, CGAL/double.h and CGAL/long_long.h.