Modular arithmetic for geometric predicates
|
| Modular arithmetic for geometric predicates |
|
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 Hervé Brönnimann, Ioannis Z. Emiris, Victor Pan and Sylvain Pion. 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.
Here are the sources in C of the package. It compiles a library of functions, usable in C++ too. The current version is 2.4, 4 February 1998. To install the package, just type: "gunzip -c modular.tar.gz | tar xvf -" (or just "tar zxvf modular.tar.gz", with GNU-tar), then read the instructions in the README file. For problems or questions, don't hesitate to contact the author at the e-mail adress (Sylvain.Pion at sophia.inria.fr).
You can read the paper accepted to the ACM '97 conference in Nice, as well as the slides corresponding to the talk that was given there.