[解決済み] 任意精度の算術演算 解説

質問

C言語を勉強しているのですが、非常に大きな数字（100桁、1000桁など）を扱うことができないことに気がつきました。これを行うためのライブラリが存在することは承知していますが、私は自分自身でそれを実装することを試みたいと考えています。

私は、誰かが任意精度の算術の非常に詳細な、おぼろげな説明を持っているか、提供できるかどうか知りたいだけです。

どのように解決するのですか？

すべては、適切なストレージと、数を小さな部品として扱うアルゴリズムの問題です。例えば、あるコンパイラで int が 0 から 99 までの数字しか扱えず、999999 までの数字を扱いたいコンパイラがあるとします (ここでは単純にするために正の数だけを扱うことにします)。

これを行うには、各数字に3つの int を与え、小学校で習った（はずの）足し算、引き算、その他の基本的な演算と同じルールで計算します。

任意精度ライブラリでは、数字を表現するために使用される基本型の数に固定的な制限はなく、メモリが保持できるものであれば何でも使用できます。

例えば足し算です。 123456 + 78 :

12 34 56
      78
-- -- --
12 35 34

最下位から順に作業する。

• 初期キャリー = 0。
• 56 + 78 + 0キャリー = 134 = 1キャリーで34
• 34 + 00 + 1キャリー = 35 = 0キャリーで35
• 12 + 00 + 0キャリー = 12 = 0キャリーの12

実は、CPU内部のビットレベルでは、一般的にこのように足し算が行われているのです。

引き算も同様で（基本型の引き算とキャリーの代わりにボローを使用）、掛け算は加算の繰り返し（非常に遅い）または交差積（より速い）で行うことができ、割り算はよりトリッキーですが、関係する数のシフトと引き算（子供のころに習ったであろう長い割り算）で行うことができます。

私は実際に、2乗したときに整数に収まる最大の10のべき乗を使用してこの種のことを行うライブラリを書きました（2つを掛けるときにオーバーフローを防ぐために int のような、2 つの int を 0 ～ 99 に制限して 2 乗すると 9,801 (<32,768) になる、あるいは 32 ビットの int を使用すると 99,980,001 (<2,147,483,648) が生成されます。

気をつけるべきいくつかのトリック

1/ 数字の足し算や掛け算をするときは、あらかじめ必要な最大のスペースを確保し、多すぎると感じたら後で減らすようにします。たとえば、2 つの 100-"digit" を加算する場合 (digit は int を使用）2つの数字を足しても101桁を超えることはありません。12桁の数字に3桁の数字を掛けても、15桁以上にはなりません（桁数を足してください）。

2/ 速度を上げるために、絶対に必要な場合のみ、数字を正規化 (必要なストレージを減らす) します。私のライブラリはこれを別の呼び出しとして持っており、ユーザーは速度とストレージの懸念の間で決定することができます。

3/ 正と負の数の加算は減算であり、負の数の減算は等価な正の数の加算と同じです。符号を調整した後に加算と減算のメソッドが互いに呼び出すようにすることで、かなりの量のコードを節約することができます。

4/ 小さな数から大きな数を引くことは避けてください。

         10
         11-
-- -- -- --
99 99 99 99 (and you still have a borrow).

その代わり、11から10を引いて、否定してください。

11
10-
--
 1 (then negate to get -1).

これは、私がこれをしなければならなかったライブラリの1つからのコメント（テキストに変換された）です。コード自体は残念ながら著作権で保護されていますが、4つの基本的な操作を処理するのに十分な情報を拾い出すことができるかもしれません。以下では、次のように仮定します。 -a と -b は負の数を表し a と b は0または正の数です。

については 加算 の場合、符号が異なる場合は否定の引き算を用いる。

-a +  b becomes b - a
 a + -b becomes a - b

について 減算 の場合、符号が異なる場合は否定の加算を用いる。

 a - -b becomes   a + b
-a -  b becomes -(a + b)

また、大きな数字から小さな数字を引き算していることを確認するために特別な処理を行います。

small - big becomes -(big - small)

乗算 は、以下のように初歩的な計算を行います。

475(a) x 32(b) = 475 x (30 + 2)
               = 475 x 30 + 475 x 2
               = 4750 x 3 + 475 x 2
               = 4750 + 4750 + 4750 + 475 + 475

この方法は、32の各桁を一度に（逆に）抽出し、addを使って結果（最初は0）に追加する値を計算するものです。

ShiftLeft と ShiftRight の演算は、乗算や除算を素早く行うために使用されます。 LongInt をラップ値（quot;real"数学の場合は10）ですばやく乗算または除算するために使用されます。上の例では、475 を 0 に 2 回 (32 の最後の桁) 加えると、950 になります (結果 = 0 + 950 = 950)。

次に、475 を左シフトして 4750 を得、32 を右シフトして 3 を得ます。 4750を0に3回足して14250とし、950の結果に足して15200とします。

4750を左シフトして47500、右シフトして3を0にします。右シフトした32は0になったので、これで終わりですが、実は475×32は15200になるのです。

分割 も厄介ですが、初期の算数に基づいています ("gazinta" の "goes into" のメソッド)。次のような長い割り算を考えてみましょう。 12345 / 27 :

       457
   +-------
27 | 12345    27 is larger than 1 or 12 so we first use 123.
     108      27 goes into 123 4 times, 4 x 27 = 108, 123 - 108 = 15.
     ---
      154     Bring down 4.
      135     27 goes into 154 5 times, 5 x 27 = 135, 154 - 135 = 19.
      ---
       195    Bring down 5.
       189    27 goes into 195 7 times, 7 x 27 = 189, 195 - 189 = 6.
       ---
         6    Nothing more to bring down, so stop.

したがって 12345 / 27 は 457 となり、余りは 6 . 検証してください。

  457 x 27 + 6
= 12339    + 6
= 12345

これは、ドローダウン変数（最初は0）を使って、12345のセグメントを27以上になるまで一度に1つずつ下げていくことで実装されています。

それから、27以下になるまで単純に27を引きます。引き算の数が、一番上の行に追加されるセグメントです。

これ以上下げるセグメントがなくなったら、結果が出ます。

これらは非常に基本的なアルゴリズムであることに留意してください。数値が特に大きくなる場合は、複雑な演算を行うはるかに良い方法があります。次のようなものを調べることができます。 GNU 多重精度算術ライブラリ - のようなものを調べてみてください。これは私自身のライブラリよりもかなり優れていて高速です。

このライブラリには、メモリを使い果たした場合に単純に終了してしまうという、かなり残念な欠点がありますが（私の意見では、汎用ライブラリとしてはかなり致命的な欠点です）、それを克服できるなら、それが行うことについてはかなり優れていると思います。

ライセンス上の理由で (あるいは明白な理由もなくアプリケーションを終了させたくないために) それを使用できない場合、少なくともそこからアルゴリズムを入手して、あなた自身のコードに統合することは可能でしょう。

また、私が見つけたのは MPIR (GMP のフォーク) の人たちは、潜在的な変更についての議論にもっと従順で、より開発者に優しい人たちのようです。