97

私はCを学ぼうとしていますが、本当に大きな数（つまり、100桁、1000桁など）を処理できないことに気づきました。これを行うためのライブラリが存在することは承知していますが、自分で実装してみたいと思います。

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

4

8 に答える 8

172

数値を小さな部分として扱うのは、すべて適切なストレージとアルゴリズムの問​​題です。が0から99までしか指定できないコンパイラがあり、int999999までの数値を処理したいとします（ここでは、単純にするために正の数のみを考慮します）。

あなたはそれぞれの数に3を与えint、足し算、引き算、その他の基本的な操作のために小学校で学んだのと同じ規則を使用することによってそれを行います。

任意精度ライブラリでは、メモリが保持できるものに関係なく、数値を表すために使用される基本型の数に固定の制限はありません。

例の追加123456 + 78::

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

最下位からの作業：

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

実際、これは、CPU内のビットレベルで加算が一般的にどのように機能するかを示しています。

減算は似ており（キャリーの代わりに基本タイプの減算と借用を使用）、乗算は加算の繰り返し（非常に遅い）または外積（高速）で実行でき、除算はトリッキーですが、数値のシフトと減算によって実行できます関与している（あなたが子供の頃に学んだであろう長い分裂）。

私は実際に、2乗したときに整数に収まる最大10の累乗を使用してこの種のことを行うライブラリを作成しました（int16ビットintが0から99に制限されるなど、2を乗算するときのオーバーフローを防ぐため）二乗すると9,801（<32,768）を生成するか、int0から9,999を使用して32ビットを生成して99,980,001（<2,147,483,648））を生成し、アルゴリズムを大幅に簡素化します。

注意すべきいくつかのトリック。

1 /数値を加算または乗算するときは、必要な最大スペースを事前に割り当て、それが多すぎる場合は後で減らします。たとえば、2つの100 "数字"（数字はint）の数字を追加しても、101桁を超えることはありません。12桁の数値に3桁の数値を掛けても、15桁を超えることはありません（桁数を加算してください）。

2 /速度を上げるには、どうしても必要な場合にのみ、数値を正規化します（必要なストレージを減らします）。私のライブラリでは、これを別の呼び出しとして使用して、ユーザーが速度とストレージのどちらを問題にするかを決定できるようにしました。

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

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とがゼロまたは正の数であると仮定します。-bab

さらに、符号が異なる場合は、否定の減算を使用します。

-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の各桁を一度に1つずつ（逆方向に）抽出し、addを使用して結果に追加する値（最初はゼロ）を計算します。

ShiftLeft演算は、 aをラップ値（「実際の」数学の場合は10）でShiftRightすばやく乗算または除算するために使用されます。LongInt上記の例では、475をゼロに2回（32の最後の桁）追加して950を取得します（結果= 0 + 950 = 950）。

次に、左シフト475で4750を取得し、右シフト32で3を取得します。4750をゼロに3回追加して14250を取得し、950の結果に追加して15200を取得します。

左シフト4750で47500、右シフト3で0になります。右シフト32がゼロになったので、終了しました。実際、475x32は15200になります。

除算も注意が必要ですが、初期の算術（「入る」ための「ガジンタ」法）に基づいています。次の筆算を検討してください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があります。確認：4576

  457 x 27 + 6
= 12339    + 6
= 12345

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

次に、27を下回るまで27を減算します。減算の数は、一番上の行に追加されたセグメントです。

ダウンさせるセグメントがなくなると、結果が得られます。

これらはかなり基本的なアルゴリズムであることに注意してください。数値が特に大きくなる場合は、複雑な演算を行うためのはるかに優れた方法があります。GNU Multiple Precision Arithmetic Libraryのようなものを調べることができます。これは、私自身のライブラリよりも大幅に優れており、高速です。

メモリが不足すると単に終了するというかなり不幸な誤解がありますが（私の意見では、汎用ライブラリにとってはかなり致命的な欠陥です）、それを過ぎて見ることができれば、それは何をするのかかなり良いです。

ライセンス上の理由で（または明確な理由なしにアプリケーションを終了したくないために）使用できない場合は、少なくともそこからアルゴリズムを取得して、独自のコードに統合することができます。

また、 MPIR（GMPのフォーク）にある組織は、潜在的な変更についての議論に適していることもわかりました。これらは、開発者にとってより使いやすいもののようです。

于 2009-08-02T04:49:27.997 に答える
10

車輪の再発明はあなたの個人的な啓蒙と学習にとって非常に良いことですが、それはまた非常に大きな仕事でもあります。重要な演習であり、私が自分で行った演習であるとあなたを思いとどまらせたくはありませんが、より大きなパッケージが対処する微妙で複雑な問題が仕事にあることに注意する必要があります。

たとえば、乗算。素朴に、あなたは「男子生徒」の方法を考えるかもしれません。つまり、ある数字を他の数字の上に書き、学校で学んだように長い掛け算をします。例：

      123
    x  34
    -----
      492
+    3690
---------
     4182

ただし、この方法は非常に低速です（O（n ^ 2）、nは桁数）。代わりに、最新のbignumパッケージは、離散フーリエ変換または数値変換のいずれかを使用して、これを本質的にO（n ln（n））演算に変換します。

そして、これは整数用です。ある種の数値の実際の表現（log、sqrt、expなど）でより複雑な関数に入ると、事態はさらに複雑になります。

理論的な背景が必要な場合は、Yapの本の最初の章「アルゴリズム代数の基本的な問題」を読むことを強くお勧めします。すでに述べたように、gmpbignumライブラリは優れたライブラリです。実数については、MPFRを使用して気に入っています。

于 2009-08-02T06:02:53.293 に答える
7

車輪の再発明をしないでください。正方形になる可能性があります。

試され、テストされているGNUMPなどのサードパーティライブラリを使用します。

于 2009-08-02T04:35:33.797 に答える
4

あなたは基本的に鉛筆と紙で行うのと同じ方法でそれを行います...

  • malloc数値は、必要に応じて任意のサイズ（およびを使用することを意味します）をとることができるバッファー（配列）で表さreallocれます。
  • 言語でサポートされている構造を使用して、可能な限り基本的な算術演算を実装し、基数ポイントのキャリーと移動を手動で処理します
  • 数値解析テキストを精査して、より複雑な関数で処理するための効率的な引数を見つけます
  • 必要なだけ実装します。

通常、計算の基本単位として使用します

  • 0-99または0-255を含むバイト
  • 0-9999または0--65536を含む16ビットワード
  • を含む32ビットワード...
  • ..。

アーキテクチャによって決定されます。

2進数または10進数のどちらを選択するかは、スペース効率、人間の可読性、およびチップに2進化10進数（BCD）の数学サポートがないことを希望するかどうかによって異なります。

于 2009-08-02T04:43:37.043 に答える
3

究極のリファレンス（IMHO）の1つは、クヌースのTAOCPVolumeIIです。数値を表現するための多くのアルゴリズムと、これらの表現の算術演算について説明します。

@Book{Knuth:taocp:2,
   author    = {Knuth, Donald E.},
   title     = {The Art of Computer Programming},
   volume    = {2: Seminumerical Algorithms, second edition},
   year      = {1981},
   publisher = {\Range{Addison}{Wesley}},
   isbn      = {0-201-03822-6},
}
于 2012-09-16T21:09:23.553 に答える
3

あなたは数学の高校レベルでそれを行うことができます。実際には、より高度なアルゴリズムが使用されていますが。たとえば、2つの1024バイトの数値を追加するには：

unsigned char first[1024], second[1024], result[1025];
unsigned char carry = 0;
unsigned int  sum   = 0;

for(size_t i = 0; i < 1024; i++)
{
    sum = first[i] + second[i] + carry;
    carry = sum - 255;
}

one place最大値を処理するために加算する場合は、結果を大きくする必要があります。これを見てください：

9
   +
9
----
18

TTMathは、学びたい場合に最適なライブラリです。C++を使用して構築されています。上記の例はばかげた例でしたが、これは一般的に加算と減算が行われる方法です！

この主題に関する良い参考資料は、数学演算の計算の複雑さです。実装する各操作に必要なスペースを示します。たとえば、2つの数値がある場合、乗算の結果を保存N-digitする必要があります。2N digits

ミッチが言ったように、それを実装するのははるかに簡単な作業ではありません！C ++をご存知の場合は、TTMathをご覧になることをお勧めします。

于 2009-08-02T04:37:27.570 に答える
1

自分で大きな整数コードを書きたいと仮定すると、これは驚くほど簡単に実行でき、最近（MATLABでは）誰かが書いたように話されます。私が使用したトリックのいくつかを次に示します。

  • 個々の10進数をdoubleの数値として格納しました。これにより、多くの操作、特に出力が簡単になります。必要以上のストレージを使用しますが、ここではメモリが安価であり、ベクトルのペアを効率的に畳み込むことができれば、乗算が非常に効率的になります。または、小数点以下の桁数をdoubleに格納することもできますが、乗算を行うための畳み込みは、非常に大きな数で数値の問題を引き起こす可能性があることに注意してください。

  • 符号ビットを個別に保存します。

  • 2つの数値の加算は、主に数字を加算してから、各ステップで桁上げを確認することです。

  • 数値のペアの乗算は、少なくともタップで高速の畳み込みコードがある場合は、畳み込みとそれに続くキャリーステップとして行うのが最適です。

  • 数値を個々の10進数の文字列として格納する場合でも、除算（mod / rem opsも）を実行して、結果で一度に約13桁の10進数を取得できます。これは、一度に1桁の10進数でのみ機能する除算よりもはるかに効率的です。

  • 整数の整数乗を計算するには、指数の2進表現を計算します。次に、繰り返し二乗操作を使用して、必要に応じてパワーを計算します。

  • 多くの操作（因数分解、素数性テストなど）は、powermod操作の恩恵を受けます。つまり、mod（a ^ p、N）を計算するときは、pがバイナリ形式で表現されているべき乗の各ステップで結果のmodNを減らします。最初にa^pを計算してから、それをmodNに減らしてみてください。

于 2009-08-02T14:51:40.700 に答える
0

これは私がPHPで行った単純な（素朴な）例です。

「Add」と「Multiply」を実装し、指数の例に使用しました。

http://adevsoft.com/simple-php-arbitrary-precision-integer-big-num-example/

コードスニップ

// Add two big integers
function ba($a, $b)
{
    if( $a === "0" ) return $b;
    else if( $b === "0") return $a;

    $aa = str_split(strrev(strlen($a)>1?ltrim($a,"0"):$a), 9);
    $bb = str_split(strrev(strlen($b)>1?ltrim($b,"0"):$b), 9);
    $rr = Array();

    $maxC = max(Array(count($aa), count($bb)));
    $aa = array_pad(array_map("strrev", $aa),$maxC+1,"0");
    $bb = array_pad(array_map("strrev", $bb),$maxC+1,"0");

    for( $i=0; $i<=$maxC; $i++ )
    {
        $t = str_pad((string) ($aa[$i] + $bb[$i]), 9, "0", STR_PAD_LEFT);

        if( strlen($t) > 9 )
        {
            $aa[$i+1] = ba($aa[$i+1], substr($t,0,1));
            $t = substr($t, 1);
        }

        array_unshift($rr, $t);
     }

     return implode($rr);
}
于 2012-03-21T17:17:19.617 に答える