剰余演算による多項式の符号判定と計算幾何学への応用

• Item type: SIG Technical Reports(1)
• 公開日: 1994-05-13
• タイトル: 剰余演算による多項式の符号判定と計算幾何学への応用
• タイトル / 言語: en
• タイトル: Modular Methods to Determine the Sign of the Values of Polynomials and Their Applications to Computational Geometry
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学工学部
• 著者所属(英): en
• 著者所属(英): University of Tokyo, Faculty of Engineering
• 著者名: 今井, 敏行
• 著者名(英): Toshiyuki, Imai
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 計算幾何学のアルゴリズムには入力が単長整数でも，計算機内で入力変数の多項式の値の符号を判定する必要が生じ，加減乗算の結果，桁数が2倍長や3倍長程度に達するものが少なくない．一般に多倍長整数の符号判定のために多倍長演算を用意すると各演算に時間がかかる．剰余演算を利用して演算時間を短縮する方法が知られているが，剰余から数値を復元するために，結局多倍長演算と変わらないことになる．本稿では，2，3倍長程度の整数に対し，剰余演算の結果から直接に符号判定を行なう方法を提案する．さらに，その方法と普通の多倍長演算による方法をシミュレートした凸包構成プログラムで計算時間を比較した結果を報告する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Not a few geometric algorithms determine signs of values of polynomials whose variables are input data to decide the structure of geometric objects and require double or triple long integer arithmetics such as addition, subrtaction and multiplication even if all the input data are integers of 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 of such calculations. 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 the applications to a geometric problem of making a convex hull.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1994, 号 35(1994-AL-039), p. 17-24, 発行日 1994-05-13
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会