Modular Arithmetic in LEDA ( residual )

**Definition**

The data type *residual* provides an implementation of exact integer arithmetic using modular computation.
In contrast to the LEDA type *integer* which offers similar functionality as *residual*, the user of *residual* has to specify for each calculation the maximal bit length *b* of the integers she wants to be exactly representable by *residual*s.
This is done by a call of *residual*::*set_maximal_bit_length*(*b*) preceding the calculation. The set of integers in the interval
[- 2^{b}, 2^{b})
is called the *current range* of numbers representable by *residual*s.

A residual number *x*
that is outside the current range is said to *overflow*. As an effect of its overflow, certain operations cannot be applied to *x*
and the result is undefined.
These critical operations include e.g. all kinds of conversion, sign testing and comparisons.
It is important to realize that for an integer *x*
given by a division-free expression it only matters whether the *final result* *x*
does not overflow.
This is sometimes useful and hence overflow is not always checked by default.

Division is available for *residual*s, but with certain restrictions.
Namely, for each division *x*/*y* the user has to guarantee at least one of the following two conditions:

*y*.*is_invertible*() is*true**x*/*y*is integral*and**x*and*y*do not overflow.

If the result of an operation is not integral, the computation will usually proceed without warning. In such cases the computation produces a nonsensical result that is likely to overflow but otherwise is a perfect *residual*. However, the operations mentioned above check for overflow.
Note that the implemented overflow checks are not rigorous, detecting invalidity only with empirically high probability. Overflow checking can be switched off by calling *set_maximal_bit_length* with a second, optional parameter *residual*::*no_overflow_check*.

#include < LEDA/numbers/residual.h >