6

序文

私は自分の BigInt ライブラリを作成して改良することで、コンピューター数学について学んでいます。これまでのところ、私の最初の化身は、10 進数のすべての数字をベクトルの連続する要素に格納しています。任意の精度で乗算および加算できます。基数 2^x に変換することにより、標準 C++ データ型で使用できるすべてのスペースを使用して、速度を上げたいと考えています。

情報

基数 10 の stdin から 1000 桁以上の数字を読み取っていますが、それらを基数 2^x に変換したいので、標準 C++ データ型のいずれか (unsigned int など) の配列またはベクトルに簡単に格納できます。基数変換、剰余法による繰り返し除算を行う方法について、私は1つのアイデアしか持っていません。そのメソッドを説明する C++ コードを次に示します。

vector<int> digits;
while(num!=0) {
   int mod = num%base;
   num = num/base;
   digits.push_back(mod);
}

難問

私が迷っていることのいくつかは、剰余による除算が大きな整数で基数変換を行う適切な方法であるかどうかです。GMPライブラリがどのようにそれを行うかを見てみました。gmp/mpn/generic/set_str.cは、「魔法」が発生する関連する c ソース ファイルですが、そこで何が起こっているのかはわかりません。Matt McCutchen のBigIntは、剰余法による除算の繰り返しを使用しているようです。この方法を使用する場合、基本的に BigInt クラスの 2 つのバージョンを作成する必要があります。

結論

  • 膨大な数を文字列から 32 ビット ワードの配列に変換する適切な手順についてアドバイスを提供してください。
  • GMP が文字列を 32 ビット ワードの配列に変換する方法を、抽象化の多くのレイヤーを経由せずに学習するのを手伝ってください。

例 4 ビット ワード サイズの使用

保存したい番号 (明らかに小さいサイズで): 123456789

符号なし文字の範囲は 0 ～ 255 です。数値を分割してベクトルに格納する場合は、次の 3 つの方法のいずれかを実行できます。

  • 底が 10 であるため、ベクトルは [1,2,3,4,5,6,7,8,9] のようになります。
    • これは、私の最初の実装での私のベクトルの外観です。
  • 基数 100 として、ベクトルは [1,23,45,67,89] のようになります。
    • 基数 10 から基数 100 への変換が簡単で、ciel (基数 10/2 の数字) 要素があります。
  • 基数 256 として、ベクトルは [7,91,205,21] のようになります。

明らかに、3 番目のソリューションが内部表現に最適であり、私が目指しているものです。

4

3 に答える 3

6

bigint ライブラリで機能する関数の乗算と加算が完了したら、文字列を bigint に変換するのは簡単です。ゼロの変換結果から開始します。処理する数字 (左から右) ごとに、前の結果を 10 倍し、新しい数字の値を加算します (bigint の乗算および加算関数を使用)。

于 2011-06-06T22:47:35.153 に答える
1

一般に、ある基数を別の基数に変換する (最上位桁から最小桁へ) アルゴリズムは次のとおりです。

output = 0
foreach digit in digits:
    output = output * base + digit

逆の順序では、次のとおりです。

output = 0
multiplier = 1
foreach digit in digits:
    output = output + multiplier * digit
    multiplier = multiplier * base

この数学を使用してbigintライブラリを再帰的に使用して、数値を格納する方法を理解できます。つまり、BigInt*BigInt と BigInt+BigInt を実装する必要があるので、これで基数を変換できます。これは最も効率的な方法ではありませんが、除算よりもはるかに高速です。

于 2011-06-06T22:51:37.550 に答える
0

FryGuy の投稿で言及されていないことの 1 つは、その方法では変換先の基数で演算を実行する必要があることですが、乗数として使用されている基数は元の数の基数と同じです。不要になったベースまたは変換元のベース。

整数の基数変換には 2 つの式があります。(1) は、(変換先の基数) に変換する基数 B を基数b で行われる算術演算と組み合わせた反復除数として使用します。ここで、b はから変換する基数です。(2) 一方、変換する数字の乗数として基数 b を使用します。これはたまたま同じ基数 b にあり、基数 B で演算を行います。

(1) 数式はパラメータとして B を使用し、基数 b で演算を行います

(2) 数式はパラメータとして b を使用し、基数 B で演算を行います

これは knuth、vol 2、4.4 基数変換の範囲外です

于 2012-08-16T21:22:13.180 に答える