Modular Arithmetics

MODULAR ARITHMETICS

Modular arithmetic can be used to compute

exactly, at low cost, a set of simple computations.

These include most geometric predicates, that

need to be checked exactly, and especially, the

sign of determinants and more general polynomial

expressions.

Modular arithmetic resides on the Chinese

Remainder Theorem, which states that, when

computing an integer expression, you only have to

compute it modulo several relatively prime integers

called the modulis. The true integer value can then

be deduced, but also only its sign, in a simple and

efficient maner.

The main drawback with modular arithmetic is its

static nature, because we need to have a bound on

the result to be sure that we preserve ourselves

from overflows (that can't be detected easily

while computing). The smaller this known bound is,

the less computations we have to do.

We have developed

a set of efficient tools to deal

with these problems, and we propose a filtered

approach, that is, an approximate computation

using floating point arithmetic, followed, in the bad

case, by a modular computation of the expression

of which we know a bound, thanks to the floating

point computation we have just done. Theoretical