任意精度演算

任意精度演算

任意精度演算とは、数値の精度を必要に応じていくらでも拡張できる演算システムのことです。実際には利用可能なメモリ容量に制限されます。

概要

任意精度演算は、多倍長整数などを内部処理に利用し、必要な桁数の浮動小数点計算を行います。固定長の整数や一般的な固定精度の浮動小数点方式は、ハードウェアで高速に処理できますが、任意精度演算はソフトウェアで実装され、より多くの処理を必要とします。

例えば、十進の0.1を2進で表現しようとする場合のように、有限の桁数では表現しきれない場合があります。そのため、2進ではなく十進で処理したり、有理数演算を併用したりすることがあります。

任意精度演算は、多倍長演算とも呼ばれます。プログラミング言語によっては、多倍長整数（特に区別する場合は bigint などと言います）の名前が bignum であることもあります。

最近のプログラミング言語の中には、多倍長整数を言語仕様でサポートしているものもあり、他の言語でも多倍長整数や任意精度の浮動小数点数を扱うライブラリが存在します。任意長の配列に格納するような実装になっています。

任意精度演算は、演算速度が重要視されない用途や、大きな数についての正確な演算結果を必要とする場合に使用されます。

数式処理システムとの違い

数式処理システムの記号計算（代数処理）では、例えば `a + b` という式は記号による式のまま表現し、その3倍は代数法則に従い `3a + 3b` のように処理します。これは任意の計算可能数を無限の精度で「表現」できる点で、任意精度演算とは異なります。しかし、数式処理システムによっては、数式からシームレスに、あるいは明確なアクションを経て、任意精度演算や有理数演算に繋げられるものもあります。

用途

任意精度演算は、以下のような用途で利用されます。

公開鍵暗号: 数百から数千桁の整数の演算を必要とする場合に利用されます。
人間中心のアプリケーション: 桁数制限やオーバーフローが不適切な場合に利用されます。
固定精度演算の結果のチェック: 固定精度演算の結果を検証するために使用されます。
方程式の係数の最適値の決定: 例えばガウス求積に出てくる `±√(1/3)` などの最善値を決定するために使用されます。
基礎的数学定数の計算: 円周率などの基礎的な数学定数を数百万桁以上計算し、その数字列の特性を解析するために使用されます。
解析が難しい関数の調査: リーマンゼータ関数など、解析的手法では解明が難しい関数の正確な振る舞いを調べるために使用されます。
フラクタル画像の描画: マンデルブロ集合などのフラクタル画像を極めて高い倍率で描く場合に必要となります。
算術オーバーフローの防止: 固定精度演算では避けられない算術オーバーフローを防ぐために使用されます。

LISP、REXX、Python、Perl、Rubyといったプログラミング言語では、整数演算で値の範囲が固定長の範囲を越えるものを、自動的に多倍長整数にフォールバックする機能があります（オプションの場合もあります）。性能的には不利ですが、演算結果がオーバーフローで不正になる可能性を排除できます。また、ワードサイズの異なる機種間でも演算結果が常に同じになることを保証できます。

実装上の問題

任意精度演算は、プロセッサのレジスタの大きさに合わせた数値型の演算よりも大幅に性能が劣ります。固定精度演算はハードウェアでの実装が比較的容易であるのに対し、任意精度演算はメモリ管理などソフトウェアで実装しなければならない部分があります。

一般に除算では循環小数が発生することがあります。任意精度演算ではどこかで打ち切るか、循環をなんらかの形で表現するか、有理数演算を併用する必要があります。

任意精度数の大きさは、使用可能な記憶装置の容量で制限されるだけでなく、数値を表す配列のインデックスのサイズでも制限されます。一般にインデックスは固定長です。

任意精度の数値の演算を効率的に行うためのアルゴリズムがいくつも考案されています。特に、桁数を \(N\) としたとき、\(N\) が大きい場合の計算量を最小にするようなアルゴリズムが必要とされます。

加算や減算の最も単純なアルゴリズムは、単純に桁ごとに順次加算・減算していき、繰り上げや繰り下げを必要に応じて行うものです。この計算量は \(O(N)\) です。

乗算の場合、最も単純なアルゴリズムは筆算の計算方法をそのまま採用する手法で、\(O(N^2)\) の計算量です。計算量が \(O(N \log(N) \log(\log(N))))\) の乗算アルゴリズムとして、高速フーリエ変換に基づくショーンハーゲ・ストラッセン法があります。また、カラツバ法では \(O(n^{\log_2 3})\) の計算量です。

例

階乗の計算では、非常に素早く非常に大きな数を生成します。方程式などでは他の項との組合せで出現するので、評価の順序を工夫することで、全体の計算では多くの場合問題になりません。正確な値が必要な場合は、整数型の限界を超えることが問題となります。

歴史

1959年に発売された IBM 1620 は、任意精度演算を実装した初期の例です。1620 は可変ワード長の十進コンピュータであり、メモリの許す限り任意の桁数の数値について計算が可能でした。

IBM 初のビジネス用コンピュータ IBM 702 は、511桁までの任意精度の数値の演算をハードウェアで実装していました。

ソフトウェアでの初期の多倍長整数の実装としては、Maclisp が有名です。1980年代になると、VAX のオペレーティングシステムで数字の文字列を数値として計算する関数群が多倍長整数機能として用意されるようになりました。また、 IBM では REXX が多倍長整数をサポートしていました。

任意精度演算をサポートしているソフトウェア

Mathematica
PARI/GP
bc
Maxima
Ultra Fractal
Fractint
Virtual Calc 2000
Calc
SpeedCrunch
TTCalc
Big Online Calculator
Full Precision Calculator
高精度計算サイト『keisan』-フリー計算
多倍長電卓LM

任意精度演算をサポートしているプログラミング言語

Common Lisp
dc
Erlang
Haskell
Java
.NET
OCaml
Perl
Python
REXX
Ruby
Scheme
Scala
Smalltalk
* JavaScript

もう一度検索