CGAL 4.7 - Modular Arithmetic: CGAL::Residue Class Reference

\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)

CGAL 4.7 - Modular Arithmetic

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members
CGAL::Residue Class Reference
Modular Arithmetic Reference

`#include <CGAL/Residue.h>`

## Definition

The class `Residue` represents a finite field \( \mathbb{Z}{/p\mathbb{Z}}\), for some prime number \( p\).

The prime number \( p\) is stored in a static member variable. The class provides static member functions to change this value. However, already existing objects do not lose their value with respect to the old prime and can be reused after restoring the old prime. Since the type is based on double arithmetic the prime is restricted to values less than \( 2^{26}\). The initial value of \( p\) is 67108859.

Attention
  Note that changing the prime invalidates already existing objects of this type.

Advanced

The default primes \( p\) satisfy the additional property that \( 2\) is a primitive root of unity of maximum order (i.e., \( p-1\)) in \( \mathbb{Z}{/p\mathbb{Z}}\). Equivalently, \( 2\) generates the multiplicative group \( (\mathbb{Z}{/p\mathbb{Z}})^\times\).

Please note that the implementation of class `Residue` requires a mantissa precision according to the IEEE Standard for Floating-Point Arithmetic (IEEE 754). However, on some processors the traditional FPU uses an extended precision. Hence, it is indispensable that the proper mantissa length is enforced before performing any arithmetic operations. Moreover, it is required that numbers are rounded to the next nearest value. This can be ensured using `Protect_FPU_rounding` with `CGAL_FE_TONEAREST`, which also enforces the required precision as a side effect.

In case the flag `CGAL_HAS_THREADS` is undefined the prime is just stored in a static member of the class, that is, `Residue` is not thread-safe in this case. In case `CGAL_HAS_THREADS` the implementation of the class is thread safe using `boost::thread_specific_ptr`. However, this may cause some performance penalty. Hence, it may be advisable to configure CGAL with `CGAL_HAS_NO_THREADS`. See Section Thread Safety in the preliminaries.

Is Model Of:
  `Field`

## Creation

| Residue ()
| constructor which initializes with zero.
| Residue (const Residue &m)
| copy constructor.
| Residue (int i)
| constructor which initializes with \( i\mod p\).
| Residue (long i)
| constructor which initializes with \( i\mod p\).

## Operations

int | get_value () const
| returns the unique representative within the range \( [-p/2,p/2]\), where \( p\) is the current prime.
Residue | operator+ (Residue a)
Residue | operator- (Residue a)
Residue | operator+ (Residue a, Residue b)
Residue | operator- (Residue a, Residue b)
Residue | operator* (Residue a, Residue b)
Residue | operator/ (Residue a, Residue b)
Residue & | operator+= (Residue a)
Residue & | operator-= (Residue a)
Residue & | operator*= (Residue a)
Residue & | operator/= (Residue a)
Residue | operator== (Residue a, Residue b)
Residue | operator!= (Residue a, Residue b)
static int | set_current_prime (int p)
| sets the current prime to the given value and returns the old prime.
static int | get_current_prime ()
| returns the value of the current prime.