多項式の符号判定のための剰余演算の利用法と計算幾何学への応用

概要

論文の詳細を見る
Not a few geometric algorithms determine signs of values of polynomials whose variables are input data to decide the structure of geometric objects. Such algorithms require double or triple long integer arithmetics such as addition, subtraction and multiplication even if all the input data are integers of the single length. In the standard method, multiple long integer arithmetic takes much time, especially in multiplication. It has been known that modular arithmetic reduces time. Modular arithmetic, however, has to use multiple long integer arithmetics to get back the values themselves from their residues and it takes the same or more time compared to the standard method. In this paper, we show some techniques to determine the sign of a double or triple long integer directly from the result of modular arithmetic method, and show the performances of these techniques applied to some geometric problems.
日本応用数理学会の論文
1995-06-15