任意精度演算
任意精度演算(にんいせいどえんざん)[1]とは、数値の精度を必要ならいくらでも伸ばしたりできるような演算システム(実際上は利用可能なメモリ容量に制限されるが)による演算である。
概要
多倍長整数(たばいちょうせいすう)などを内部処理に利用し、必要な桁数の浮動小数点計算を行う。固定長の整数や一般的な固定精度の浮動小数点方式は、ハードウェアで高速に処理できるのに対し、任意精度演算はソフトウェアで実装され、重い処理を必要とする。十進の0.1を2進で表現しようとする場合のように、有限の桁数では表現し切れない場合もあることから、2進でなく十進で処理するものや、有理数演算を併用したりもする。
多倍長演算(たばいちょうえんざん)[2]とも言うが、プログラミング言語によっては、多倍長整数 (特に区別する場合は bigint
などと言う) の名前が bignum
であることもある。
最近のプログラミング言語の中には、多倍長整数を言語仕様でサポートしているものもあり、他の言語でも多倍長整数や任意精度の浮動小数点数を扱うライブラリが存在する。任意長の配列に格納するような実装になっている。
任意精度演算は、演算速度が重要視されない用途や大きな数についての正確な演算結果を必要とする場合に使われる。
数式処理システムとの違い
数式処理システムの記号計算(代数処理)では、たとえば a + b
という式はそういう記号による式のまま表現し、たとえばその3倍は代数法則に従い 3a + 3b
のように処理するので、任意の計算可能数を無限の精度で「表現」できるが、任意精度演算とは異なったものである。しかし、個々の数式処理システムの設計者の考え次第であるが、数式からシームレスに、あるいは明確なアクションを経て、任意精度演算や有理数演算に繋げられるものもある。
用途
典型的用途として数百から数千桁の整数の演算を必要とする、公開鍵暗号がある。また、人間中心のアプリケーションで桁数制限やオーバフローが不適切な場合にも使用される。また、固定精度演算の結果をチェックするのにも使え、方程式の係数(例えばガウス求積に出てくる カテゴリ
多倍長乗算
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/06/15 03:40 UTC 版)
詳細は「多倍長乗算」および「乗算アルゴリズム(英語版)」を参照 カラツバ法(1960年) en:Toom–Cook multiplication(1963年)カラツバ法はToom-3の特別な場合である。 ショーンハーゲ・ストラッセン法(1971年)1965年に高速フーリエ変換/離散フーリエ変換のCooley-Tukey型FFTアルゴリズム(英語版)が発見され、FFTを使う方法が開発された。ショーンハーゲ・ストラッセン法は、カラツバ法やToom-3より高速なアルゴリズムである。 en:Fürer's algorithm(2007年)Schönhage–Strassenより高速。
※この「多倍長乗算」の解説は、「乗法」の解説の一部です。
「多倍長乗算」を含む「乗法」の記事については、「乗法」の概要を参照ください。
- 多倍長乗算のページへのリンク