MODULAR ARITHMETIC:Modular arithmetic can be used to computeexactly,

MODULAR ARITHMETIC:Modular arithmetic can be used to computeexactly,

MODULAR ARITHMETIC:Modular arithmetic can be used to computeexactly, at low cost, a set of simple computations.These include most geometric predicates, thatneed to be checked exactly, and especially, thesign of determinants and more general polynomialexpressions. Modular arithmetic resides on the ChineseRemainder Theorem, which states that, whencomputing an integer expression, you only have tocompute it modulo several relatively prime integerscalled the modulis. The true integer value can thenbe deduced, but also only its sign, in a simple andefficient maner. The main drawback with modular arithmetic is itsstatic nature, because we need to have a bound onthe result to be sure that we preserve ourselvesfrom overflows (that can’t be detected easilywhile computing).

The smaller this known bound is,the less computations we have to do. We have developped a set of efficient tools to dealwith these problems, and we propose a filteredapproach, that is, an approximate computationusing floating point arithmetic, followed, in the badcase, by a modular computation of the expressionof which we know a bound, thanks to the floatingpoint computation we have just done. Theoreticalwork has been done in common with , , Victor Panand. See the bibliography for details. At the moment, only the tools to compute withoutfilters are available. The aim is now to build acompiler, that produces exact geometricpredicates with the following scheme: filter +modular computation. This approach is notcompulsory optimal in all cases, but it has theadvantage of simpleness in most geometric tests,because it’s general enough.

Concerning the implementation, the ModularPackage contains routines to compute sign ofdeterminants and polynomial expressions, usingmodular arithmetic. It is already usable, tocompute signs of determinants, in any dimension,with integer entries of less than 53 bits. In thenear future, we plan to add a floating point filterbefore the modular computation.

Mathematics Essays