任意精度演算

コンピュータサイエンスにおいて、任意精度演算（多倍長演算、多倍長演算、あるいは無限精度演算とも呼ばれる）とは、計算対象の数値の精度が、ホストシステムの利用可能なメモリ容量によってのみ制限される可能性があることを意味します。これは、ほとんどの算術論理演算ユニット（ALU）ハードウェアに搭載されている、より高速な固定精度演算とは対照的です。固定精度演算は通常、8ビットから64ビットの精度を提供します。

いくつかの最新のプログラミング言語は、多倍長整数を組み込みでサポートしており、^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]}その他にも、任意精度整数および浮動小数点演算用のライブラリが用意されています。これらの実装では、プロセッサレジスタのサイズに関連する固定ビット数として値を格納するのではなく、通常は可変長の桁配列を使用します。

任意精度演算は、演算速度が制約要因とならないアプリケーション、または非常に大きな数値に対して正確な結果が求められるアプリケーションで使用されます。これは、多くの数式処理システムが提供する記号計算と混同してはなりません。数式処理システムは、 π・sin(2)などの式で数値を表現し、あらゆる計算可能な数値を無限の精度で表現できます。

一般的な応用例としては、公開鍵暗号があり、そのアルゴリズムでは一般的に数百桁の整数を用いた算術演算が用いられます。^{[ 5 ] [ 6 ]}また、人工的な制限やオーバーフローが不適切な 状況でも使用されます。さらに、固定精度計算の結果をチェックしたり、数式に必要な係数の最適値またはほぼ最適値を決定するのにも役立ちます。${\textstyle {\sqrt {\frac {1}{3}}}}$ガウス積分に現れる。^{[ 7 ]}

任意精度演算は、 πなどの基本的な数学定数を数百万桁以上の桁数で計算したり、桁列の特性を分析したり^{[ 8 ]} 、あるいはより一般的には、解析的手法では調査が難しい特定の問題があるリーマンゼータ関数などの関数の正確な挙動を調査するためにも使用されます。別の例としては、マンデルブロ集合に見られるような、非常に高い倍率でフラクタル画像をレンダリングする場合が挙げられます。

任意精度演算は、固定精度演算の固有の制限であるオーバーフローを回避するためにも使用できます。自動車の走行距離計の表示が99999から00000に変わるのと同様に、固定精度整数は、数値が固定精度レベルで表現するには大きすぎるとラップアラウンドを起こす可能性があります。一部のプロセッサは、代わりに飽和によってオーバーフローを処理できます。これは、結果が表現できない場合、最も近い表現可能な値に置き換えることを意味します。（16ビット符号なし飽和の場合、65535に任意の正の数を加えると、結果は65535になります。）一部のプロセッサは、演算結果が使用可能な精度を超えた場合に例外を生成できます。必要に応じて、例外をキャッチして回復できます。たとえば、任意精度演算を使用するソフトウェアで操作を再開できます。

多くの場合、タスクまたはプログラマーは、特定のアプリケーションにおける整数値がオーバーフローを引き起こすほど大きくならないことを保証できます。このような保証は、実用的な制限に基づいている場合があります。例えば、学校の出席管理プログラムでは、タスクの制限が4,000人の生徒数となる場合があります。プログラマーは、中間結果が指定された精度範囲内に収まるように計算を設計することができます。

Lisp、Python、Perl、Haskell、Ruby、Rakuなどの一部のプログラミング言語では、すべての整数演算に任意精度数を使用するか、または任意精度数を使用するオプションが用意されています。これにより、整数はシステムの利用可能なメモリによってのみ制限される任意のサイズまで拡張できます。これはパフォーマンスを低下させますが、単純なオーバーフローによる誤った結果（または例外）の懸念を解消します。また、特定のマシンのワードサイズに関係なく、すべてのマシンで演算結果が同じになることをほぼ保証できます。プログラミング言語で任意精度数のみを使用することで、数値は数値であり、異なる精度レベルを表すために複数の型が必要ないため、言語が簡素化されます。

任意精度演算は、プロセッサレジスタに完全に収まる数値を使用する演算よりもかなり遅くなります。これは、後者は通常ハードウェア演算で実装されるのに対し、前者はソフトウェアで実装する必要があるためです。コンピュータが特定の演算（整数除算やすべての浮動小数点演算など）のためのハードウェアを欠いており、代わりにソフトウェアが提供されている場合でも、使用可能なハードウェアレジスタに密接に関連する数値サイズ、つまり1ワードまたは2ワードのみが使用されます。例外もあり、1950年代と1960年代の特定の可変ワード長マシン、特にIBM 1620、IBM 1401、およびHoneywell 200シリーズは、使用可能なストレージによってのみ制限される数値を操作でき、値の範囲を区切る追加のビットがありました。

REXXやooRexxなどの一部の言語では、計算を行う前にすべての計算の精度を設定する必要があります。一方、PythonやRubyなどの他の言語では、オーバーフローを防ぐために精度が自動的に拡張されます。

階乗の計算では、非常に大きな数値が容易に生成されることがあります。これは、多くの数式（テイラー級数など）での使用においては問題になりません。なぜなら、階乗は他の項とともに現れるため、評価の順序に注意すれば、中間計算値は問題にならないからです。階乗の近似値が必要な場合は、浮動小数点演算を用いたスターリング近似法が良好な結果をもたらします。下の表に示すように、固定サイズの整数変数で表現できる最大値は、比較的小さな引数でも超えてしまう可能性があります。浮動小数点数でもすぐに範囲を超えてしまうため、数値の対数を用いて計算を書き換えると良いでしょう。

しかし、大きな階乗の正確な値が必要な場合は、次の擬似コードのように、1、1 × 2、1 × 2 × 3、1 × 2 × 3 × 4、...といった連続する階乗数を計算する古典的なアルゴリズムを実装した特別なソフトウェアが必要です。

定数: Limit = 1000 % 十分な桁数。 Base = 10 % シミュレーション演算の基数。 FactorialLimit = 365 % 解くべき目標数、365! tdigit: 文字配列[0:9] = ["0","1","2","3","4","5","6","7","8","9"] 変数: digit: Array[1:Limit] of 0..9 % 大きな数。carry , d: Integer % 乗算中の補助。last : Integer % 大きな数の桁へのインデックス。text : Array[1:Limit] of character % 出力用のスクラッチパッド。 digit[*] := 0 % 配列全体をクリアします。 last := 1 % 大きな数値は 1 桁から始まります。 digit[1] := 1 % その唯一の桁は 1 です。for n := 1 to FactorialLimit: % 1!、2!、3!、4! などを生成するステップを順に実行します。 carry := 0 % n による乗算を開始します。for i := 1 to last: % 各桁を順に処理します。 d := digit[i] * n + carry % 1 桁を乗算します。 digit[i] := d mod Base % 結果の最下位桁を保持します。 carry := d div Base % 次の桁に繰り上げます。while carry > 0: % 残りのキャリーを大きな数値に格納します。if last >= Limit: error("overflow") last := last + 1 % 1桁追加。 digit[last] := 桁上げmod基数 carry := carry div Base % キャリーの最後の桁を削除します。 text[*] := " " % 出力を準備します。for i := 1 to last: % バイナリからテキストに変換します。 text[Limit - i + 1] := tdigit[digit[i ] ] % 順序を反転します。print text[Limit - last + 1:Limit], " = ", n, "!"

この例を踏まえると、いくつかの詳細について議論できる。最も重要なのは、大きな数の表現方法の選択である。この場合、桁には整数値のみが必要となるため、固定幅の整数配列で十分である。配列の連続する要素が基数のべき乗を表すようにすると便利である。

2番目に重要な決定は、算術の基数の選択です。ここでは10です。考慮すべき点はたくさんあります。スクラッチパッド変数dは、 1桁の乗算結果と前の桁の乗算からの繰り上がりを保持できる必要があります。10進数では、16ビット整数は最大32767まで許容するため、確かに十分です。ただし、この例では、nの値自体が1桁に制限されていないため、不正行為を行っています。このため、 n > 3200程度ではメソッドが失敗します。より一般的な実装では、nも複数桁の表現を使用します。このショートカットの2つ目の結果は、複数桁の乗算が完了した後、繰り上がりの最後の値を1桁だけでなく、複数の上位桁に繰り上げる必要がある場合があることです。

人間が理解しやすいように、結果を10進数で表示するという問題もあります。基数がすでに10なので、配列digitの各桁を順番に表示するだけで結果は示せますが、最上位桁が最後に表示されます（つまり、123 は "321" と表示されます）。配列全体を逆順に表示することもできますが、その場合、先頭にゼロが付加された数（"00000...000123"）が表示され、好ましくない可能性があるため、この実装ではスペースで埋めたテキスト変数に表現を構築し、それを表示します。最初のいくつかの結果（5桁ごとにスペースを入れ、注釈を追加したもの）は次のとおりです。

この実装では、コンピュータの組み込み演算をより効果的に活用できます。簡単な拡張としては、基数を100（出力の変換プロセスもそれに合わせて変更）にするか、十分な幅のコンピュータ変数（32ビット整数など）があれば、10000などのより大きな基数を使用できます。コンピュータの組み込み整数演算に近い2のべき乗基数で処理すると利点がありますが、出力のために10進数基数に変換するのはより困難になります。一般的な最新のコンピュータでは、加算と乗算はオペランドの値に関係なく定数時間で実行されます（オペランドが単一のマシンワードに収まる限り）。そのため、桁配列の各要素にできるだけ多くの大きな数を詰め込むことで大きなメリットが得られます。コンピュータは、例のようにmodとdivの2つの演算を必要とせずに、積を桁と桁上げに分割する機能も提供している場合があります。また、ほぼすべての演算ユニットには、多倍長加算と減算で利用できる桁上げフラグが備わっています。こうした細かな部分は機械語プログラマーにとって重要な作業であり、適切なアセンブリ言語による多項式演算ルーチンは、こうした機能に直接アクセスできない高水準言語のコンパイル結果よりも高速に実行できる。高水準言語は、最適化コンパイラを用いて高水準の命令を対象マシンのモデルにマッピングするからである。

1桁の乗算の場合、作業変数は(基数 − 1) ² + キャリーの値を保持できなければなりません。ここで、キャリーの最大値は(基数 − 1)です。同様に、桁配列のインデックスに使用される変数自体も幅に制限があります。インデックスを拡張する簡単な方法は、ビッグナンバーの桁を適切なサイズのブロックで処理し、アドレス指定を (ブロックi、桁j ) で行うことであり、ここでiとj は小さな整数です。あるいは、インデックス変数にビッグナンバー技術を採用することもできます。最終的には、マシンの記憶容量と実行時間が問題のサイズに制限を課します。

IBM初のビジネスコンピュータであるIBM 702（真空管式コンピュータ、1950年代半ば）は、1桁から511桁までの任意の長さの数字列に対して、整数演算を完全にハードウェアで実装していました。任意精度演算のソフトウェア実装として最初に広く普及したのは、おそらくMaclispでしょう。その後、1980年頃になると、オペレーティングシステムのVAX/VMSとVM/CMSが、それぞれ文字列関数の集合として、またEXEC 2とREXXという言語で、多倍長整数演算機能を提供するようになりました。

初期の広く普及した実装例としては、 1959年から1970年にかけて製造されたIBM 1620が挙げられる。1620は、個別のトランジスタを使用する10進数演算マシンであったが、利用可能なメモリ容量に応じて2桁から任意の桁数までの数字列に対して整数演算を実行するためのハードウェア（ルックアップテーブルを使用）を備えていた。浮動小数点演算の場合、仮数は100桁以下に制限され、指数は2桁に制限されていた。最大メモリ容量は60,000桁であったが、 1620用のFortranコンパイラは10桁などの固定サイズを採用しており、デフォルト設定が不十分な場合は制御カードで指定することができた。

ほとんどのコンピュータソフトウェアにおける任意精度演算は、要求された精度で数値を格納し、計算を実行するためのデータ型とサブルーチンを提供する外部ライブラリを呼び出すことによって実装されます。

ライブラリによって任意精度数の表現方法は異なり、整数のみを扱うライブラリもあれば、浮動小数点数をさまざまな基数（10進数または2進数のべき乗）で格納するライブラリもあります。数値を単一の値として表現するのではなく、分子と分母のペア（有理数）として格納するものや、計算可能な数値を完全に表現できるものもありますが、ストレージ容量に制限があります。根本的に、チューリングマシンはすべての実数を表現することはできません。${\displaystyle \mathbb {R} }$の濃度を超える${\displaystyle \mathbb {Z} }$。

• フューラーのアルゴリズム
• カラツバアルゴリズム
• 混合精度演算
• シェーンハーゲ・シュトラッセンアルゴリズム
• トゥーム・クック乗算
• リトルエンディアンベース128

• クヌース、ドナルド（2008）。半数値アルゴリズム。コンピュータプログラミングの技法。第 2巻（第3 版）。アディソン・ウェスリー。ISBN 978-0-201-89684-8。セクション 4.3.1: 古典的アルゴリズム
• デリック・ウッド（1984）。『パラダイムとPascalによるプログラミング』コンピュータサイエンスプレス。ISBN 0-914894-45-5。
• リチャード・クランドール、カール・ポメランス（2005）。素数。シュプリンガー・フェルラーク。ISBN 9780387252827。第9章：大規模整数演算のための高速アルゴリズム

• ランドール・ハイド著『アセンブリ言語の芸術』の第9.3章では、多倍長演算について、 x86アセンブリ言語の例を用いて解説している。
• Rosetta Code タスク任意精度整数95 を超えるプログラミング言語が任意精度演算を使用して 5**4**3**2 の値を計算するスタイルのケース スタディ。