多数桁計算

円周率を 1000 桁以上求めよう、というような計算を行う場合、 一般的なプログラム言語で扱うことができる変数 (整数型、 単精度浮動小数型、倍精度浮動小数型など) では末尾の桁まで正確な値を表現することができない。 その解決策の1つとして、1 つの数を複数の変数に格納することで表現する方法が多倍長数である。

余談ではあるが、人間も1つの数字では0〜9の 10 個の数しか表現できないが、2つの数字を使うことで 0〜99 の100個の数、3つの数字で 1000 個の数を表現するのもある意味多倍長数の表現である。

多倍長ライブラリ

多倍長数を用いる場合には四則演算のレベルから演算方法をプログラムする他にも、 いくつかのプログラム環境には変数の型、 もしくは外部ライブラリとして多倍長数を計算できるものがある。 以下にその例を挙げる。 多くの処理系では多倍長乗算のアルゴリズムとして Karatsuba 法が採用されているため桁数 $n$ に対して $O(n^{1.4})$ 程度の計算時間になるので、1 万桁を超える精度の計算を ($\pi$や $e$ などの計算以外に使うのか分からないが) 行う場合は GMP など乗算コストが $O(n\log n)$ になるものを選ぶと良い。

多倍長整数
Python, Ruby, Perl, Haskell, U-BASIC, Java, C/C++(GMP)
多倍長浮動小数
Ruby, Perl, U-BASIC, Java, C/C++(GMP)

多倍長演算

以下では自分自身で多倍長演算を実装するために必要な情報について述べる。 あまり特定の言語に限定するつもりはないが、C++ に基づいた言及をすることがある。

その他計算アルゴリズム