Modular Arithmetics Essay, Research Paper

MODULAR ARITHMETIC:

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 developped 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

work has been done in common with , , Victor Pan

and. See the bibliography for details.

At the moment, only the tools to compute without

filters are available. The aim is now to build a

compiler, that produces exact geometric

predicates with the following scheme: filter +

modular computation. This approach is not

compulsory optimal in all cases, but it has the

advantage of simpleness in most geometric tests,

because it’s general enough.

Concerning the implementation, the Modular

Package contains routines to compute sign of

determinants and polynomial expressions, using

modular arithmetic. It is already usable, to

compute signs of determinants, in any dimension,

with integer entries of less than 53 bits. In the

near future, we plan to add a floating point filter

before the modular computation.

Bibliography

Explains basically the definition of modular arithmetic, and contents of it.