3

この質問が重複して投票されたり、閉じられたりするリスクを冒して、この質問が出てきました。

バックグラウンド

int、long long などの「通常の」データ型では、2 進数の数値を 10 進数の文字列に変換するには、次のようにします (疑似コードで)。

Set length = 0
Set divisor to largest base10 value the data type will hold (Divisor).
  Loop
    Divide number in question by divisor.
    Place result in a string at position length.
    Increment the length by 1.
    Divide the divisor by 10.
Reverse the string.
Print the string.

(ほとんどの) どの言語でも、実際の実装は非常に簡単です。

問題

上記の方法で私が遭遇している問題は、大きな整数 (任意精度算術とも呼ばれます) では、最初から最大の 10 進数の値がないことです。問題は、「その値が何であるかを知る方法がない場合、除数を可能な限り最大の base10 値に初期化するにはどうすればよいですか?」ということです。

私が試したこと

まだ解決策を下書きしようとしています。

リサーチ

ここで見つけたリンクには、次のようなものがあります。

BigInteger クラスを使用せずに、「大きな」16 進数 (文字列形式) を 10 進数 (文字列形式) に変換します。

C: 基数 10 で BigInteger を出力します

BigInteger を 10 進 (Base 10) 文字列に変換する最速の方法は?

BigInteger クラスを使用せずに、「大きな」16 進数 (文字列形式) を 10 進数 (文字列形式) に変換します。

Google で検索すると、他のことがわかりましたが、私の質問に明確に答えるものは何もありませんでした。

アイデア

うまくいくかもしれないと私が思う1つの方法は次のとおりです（疑似コードで）：

Define p_divisor as previous divisor.
Set divisor = 1
  Loop:
    if divisor < dividend
      then
        Set p_divisor = divisor
        divisor = divisor * 10
      else
        end loop
  Loop:
    Divide number in question by divisor.
    Place result in a string at position length.
    Increment the length by 1.
    Divide the divisor by 10.
    if divisor == 1 then end loop
Reverse the string.
Print the string.

これは正しい方法でしょうか？私は大きな整数ライブラリを稼働させているので（乗算と除算を含む）、これをやってのけるのはそれほど難しくありません。この方法で見られる大きな問題はパフォーマンスです。最初の除数を取得するために乗算シーケンスを実行する必要があり、base10 の位置ごとに 2 回除算する必要があるためです。1 つは実際の除算用で、もう 1 つは除数用です。

4

4 に答える 4

4

これを行う 1 つの (かなり一般的な) 方法は、大きな整数型であろうと通常の整数型であろうと、数値を繰り返し 10 で割って、剰余を次の桁として保存することです (最下位から開始します)。数字がゼロになるまで続けます。検出された最初の数字が最下位であるため、最後に文字列を逆にするか、逆に構築する必要がある場合があります。

通常の使用例は次のunsigned intようになります。

void printUInt(unsigned x) {
  char buf[(sizeof(x) * CHAR_BIT) / 3 + 2]; // slightly oversize buffer
  char *result  = buf + sizeof(buf) - 1; // index of next output digit

  // add digits to result, starting at 
  //   the end (least significant digit)

  *result = '\0'; // terminating null
  do {
    *--result = '0' + (x % 10);  // remainder gives the next digit
    x /= 10;
  } while (x); // keep going until x reaches zero

  puts(result);
}

このプロセスは、大きな整数の場合とほぼ同じですが、可能であれば、除算を実行して剰余を 1 つのステップで見つけるのが最善です。

上記の例では、バッファの最後から文字列を構築します (そのため、最終的にはバッファresultの途中のどこかを指すことになります) が、最初から構築し、後で逆にすることもできます。

元の数値で使用されているビット数を決定できれば、出力に必要なサイズを見積もることができます (3 ビットあたり約 1 桁追加 -- わずかに少ない)。

于 2016-06-04T18:08:36.870 に答える
1

受け入れられた回答は、これを行う簡単な方法をすでに提供しています。それはうまく機能し、素晴らしい結果をもたらします。ただし、大きな値を文字列に変換する必要がある場合は、もっと良い方法があります。

私のソリューションは多くの読者が簡単に読むことができない Delphi で書かれており、かなり長い (100 行以上のコードにいくつかの関数があり、さらに他の関数を使用しているなど) ため、詳細には触れません。特に、変換ではいくつかの異なる基数が異なる方法で処理されるため、簡単な回答で説明されています)。

しかし、原理は、数を 10 の累乗である数で 2 つのほぼ等しいサイズの半分に分割することです。部品のいくつかの下限 (たとえば、32 ビット) に達すると、最終的に従来の方法で、つまり受け入れられた回答のように変換します。

次に、部分的な変換が「連結」されます (実際には、数字は正しいアドレスの単一バッファーに直接配置されます)。そのため、最後に、数字の巨大な文字列が 1 つ得られます。

これは少しトリッキーです。これについては、非常に多数の場合に調査したい人のためにのみ言及します。たとえば、100 桁未満の数字では意味がありません。

これは確かに再帰的な方法ですが、単純に 10 で除算する方法ではありません。

バッファのサイズは、次のようにして事前に計算できます。

bufSize = myBigInt.bitCount() * Math.log10(2) + some_extra_to_be_sure;

さまざまな基数に対して事前計算されたテーブルを使用していますが、それは実装の詳細です。

非常に大きな数値の場合、これは10 で除算を繰り返すループよりもはるかに高速です。特に、その方法では、数値全体を常に 10 で除算する必要があり、非常にゆっくりとしか小さくなりません。分割統治アルゴリズムは、より小さな数を分割するだけであり、部分を切り取るための (コストのかかる) 分割の総数ははるかに少なくなります (N ではなく log N が私の推測です)。したがって、（平均して）はるかに小さい数の分割が少なくなります。

参照。ブレント、ジマーマン、「現代のコンピューター算術」、アルゴリズム 1.26

私のコードと説明は、それがどのように機能するかを確認したい場合は、ここにあります: BigIntegers ユニット

于 2016-06-12T01:33:51.650 に答える
0

同様の問題に遭遇し、好みの解決策が見つからなかったので、私のowmを思いつきました。アイデアは、BigInt使用しているベースを、可能な限り大きく、現在のベースよりも小さいBigIntベースのべき乗に変換することです。10システムコールを使用して「数字」で変換し、結果を連結できること。そのため、明示的な除算はこれまで関与しておらず、システム ライブラリ関数に隠されているだけです。それでも、全体的な複雑さは 2 次です (他の除算ベースのソリューションと同様)。

friend std::ostream& operator<<(std::ostream& out, const BigInt_impl& x){
    using Big10 = BigInt_impl<char32_t, uint64_t, 1000000000>; // 1e9 is the max power of 10 smaller then BASE
    auto big10 = Big10(0);
    auto cm = Big10(1);
    for(size_t i = 0; i < x.digits.size(); ++i, cm *= BASE){
        big10 += cm*x.digits[i];
    }
    out << big10.digits.back();
    for(auto it = next(big10.digits.rbegin()); it != big10.digits.rend(); ++it){ 
        out << std::setfill('0') << std::setw(9) << *it;
    }
    return out;
}

このソリューションでは、魔法の定数 1e9 に注意してください。これは、 BASE = 2^32. それを適切に行うのが面倒でした。

(C++ の場合、申し訳ありませんが、質問は C に関するものであることに気付きましたが、アイデアの例として、ここにコードを残しておきたいと思います)

于 2016-08-04T14:15:03.160 に答える