実装上の問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/07/25 08:41 UTC 版)
任意精度演算は、プロセッサのレジスタの大きさに合わせた数値型の演算より大幅に性能が劣る。固定精度演算はハードウェアでの実装が比較的容易であるのに対して、任意精度演算はメモリ管理などソフトウェアで実装しなければならない部分がある（多倍長ないし任意精度の演算のハードウェアサポートは過去広くみられる）。整数の除算や浮動小数点演算はサポートしていないプロセッサもあるが、ソフトウェアでそれらをサポートするとしても通常は1ワードまたは2ワードの数値型を使い、任意長の処理は行わない。 一般に除算では循環小数が発生することがある。任意精度演算ではどこかで打ち切るか、循環をなんらかの形で表現するか、有理数演算を併用する。 多倍長整数であれば任意長の整数演算を、任意精度浮動小数点であれば任意精度の浮動小数点の処理をおこなう。任意精度数の大きさは使用可能な記憶装置の容量で制限されるだけでなく、数値を表す配列のインデックスのサイズでも制限される。一般にインデックスは固定長である。 任意精度の数値の演算を効率的に行うためのアルゴリズムがいくつも考案されてきた。特に、桁数を N {\displaystyle N} としたとき、 N {\displaystyle N} が大きい場合の計算量を最小にするようなアルゴリズムが必要とされる。 加算や減算の最も単純なアルゴリズムは、単純に桁ごとに順次加算・減算していき、繰り上げや繰り下げを必要に応じて行うものである。この計算量は O ( N ) {\displaystyle O(N)} である（ランダウの記号参照）。 乗算の場合、最も単純なアルゴリズムは筆算の計算方法をそのまま採用する手法で O ( N 2 ) {\displaystyle O(N^{2})} の計算量である。計算量が O ( N log ( N ) log ( log ( N ) ) ) {\displaystyle O(N\log(N)\log(\log(N)))} の乗算アルゴリズムとして、高速フーリエ変換に基づくショーンハーゲ・ストラッセン法（Schönhage-Strassen-Algorithmus）がある。また、カラツバ法では O ( n log 2 3 ) {\displaystyle O(n^{\log _{2}3})} の計算量である。 N {\displaystyle N} があまり大きくない場合、カラツバ法の方が性能がよい（前者の性能が勝つのは少なくとも1万桁以上の場合）。
※この「実装上の問題」の解説は、「任意精度演算」の解説の一部です。
「実装上の問題」を含む「任意精度演算」の記事については、「任意精度演算」の概要を参照ください。
- 実装上の問題のページへのリンク
