剰余演算による多項式の符号判定と計算幾何学への応用
スポンサーリンク
概要
- 論文の詳細を見る
計算幾何学のアルゴリズムには入力が単長整数でも,計算機内で入力変数の多項式の値の符号を判定する必要が生じ,加減乗算の結果,桁数が2倍長や3倍長程度に達するものが少なくない.一般に多倍長整数の符号判定のために多倍長演算を用意すると各演算に時間がかかる.剰余演算を利用して演算時間を短縮する方法が知られているが,剰余から数値を復元するために,結局多倍長演算と変わらないことになる.本稿では,2,3倍長程度の整数に対し,剰余演算の結果から直接に符号判定を行なう方法を提案する.さらに,その方法と普通の多倍長演算による方法をシミュレートした凸包構成プログラムで計算時間を比較した結果を報告する.
- 一般社団法人情報処理学会の論文
- 1994-05-13
著者
関連論文
- 図形の可逆なミンコフスキー和の提案
- 図形のミンコフスキー和の逆演算は何か
- 誤差による破綻の心配のない線分 Voronoi 図構成算法
- 点ボロノイ図を利用した線分ボロノイ図の位相構造決定法
- 自然造形物・工芸品における曲面の曲率線抽出とその性質分析
- ICIAM 99 Edinburgh報告 その2(学術会合報告)
- 平面グラフが凸図形のVoronoi図であることの確認法
- 剰余計算の並列化による誤差なし図形処理とその実装
- 幾何的アルゴリズムの簡易な退化解除法
- 多項式の符号判定のための剰余演算の利用法と計算幾何学への応用
- 組合せ構造を優先した多角形Voronoi図の構成法
- 剰余演算による多項式の符号判定と計算幾何学への応用