РефератыИностранный языкMoModular Arithmetic Essay Research Paper Modular arithmetic

Modular Arithmetic Essay Research Paper Modular arithmetic

Modular Arithmetic Essay, Research Paper


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 co

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

Сохранить в соц. сетях:
Обсуждение:
comments powered by Disqus

Название реферата: Modular Arithmetic Essay Research Paper Modular arithmetic

Слов:353
Символов:2401
Размер:4.69 Кб.