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

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 residuals, 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 first condition is satisfied, there is an alternative way to do the division x/y. Introducing the residual variable z = y.inverse(), the call x/y is equivalent to the call x*z. The latter form is advantageous if several divisions have the same divisor y because here the time-consuming inversion of y, which is implicit in the division x/y, has to be performed only once.

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 >