3

9223372036854775807( ) などの大きな数が与えられた場合Int64.MaxValue、数字を合計する最も速い方法は何ですか?

現在、私は ToStringing を実行し、各文字を次のように再解析していintます。

num.ToString().Sum(c => int.Parse(new String(new char[] { c })));

これは確かに恐ろしく非効率的です。助言がありますか？

最後に、これを でどのように機能させますBigIntegerか?

ありがとう

4

6 に答える 6

14

さて、別のオプションは次のとおりです。

int sum = 0;
while (value != 0)
{
    int remainder;
    value = Math.DivRem(value, 10, out remainder);
    sum += remainder;
}

BigIntegerにもDivRemメソッドがあるため、同じアプローチを使用できます。

DivRem同じ演算を「手動で」実行するほど高速ではないことがわかっているので、速度に本当に関心がある場合は、それを検討することをお勧めします。

また、合計で事前計算された (たとえば) 1000 個の要素を持つルックアップ テーブルを考えてみましょう。

int sum = 0;
while (value != 0)
{
    int remainder;
    value = Math.DivRem(value, 1000, out remainder);
    sum += lookupTable[remainder];
}

これは反復回数が少ないことを意味しますが、反復ごとに配列アクセスが追加されます...

于 2011-03-11T17:55:27.713 に答える
2

BigIntegerバージョンについては誰も議論していません。そのために、あなたの値よりも小さい最後の10 2 nが見つかるまで、10 1、10 2、10 4、108などを調べます。数値divとmod102 nを使用して、 2つの小さい値を考え出します。洗浄、すすぎ、そして再帰的に繰り返します。（10の反復平方を配列に保持し、再帰部分で次に使用する累乗に関する情報を渡す必要があります。）

k桁のBigIntegerの場合、10で割るとO（k）になります。したがって、ナイーブアルゴリズムで数字の合計を見つけることはO（k 2）です。

C＃が内部で何を使用しているかはわかりませんが、kビットをkビット整数で乗算または除算するための非ナイーブアルゴリズムはすべて、時間O（k 1.6）以上で機能します（ほとんどの場合、はるかに優れています） 、ただし、「小さな大きな整数」の場合はさらに悪化するオーバーヘッドがあります）。その場合、最初のパワーのリストを準備し、1回分割するには、O（k 1.6）の時間がかかります。これにより、サイズO（（k / 2）1.6）= 2 -0.6 O（k 1.6）の2つの問題が発生します。次のレベルでは、別の2 -1.2 O（k 1.6）の作業に対して、サイズO（（k / 4）1.6 ）の4つの問題があります。すべての項を合計すると、2の累乗が定数に収束する等比数列になり、合計作業量はO（k1.6）。

これは間違いなく勝利であり、数千桁の数字を使用している場合、勝利は非常に明白になります。

于 2011-03-12T20:11:45.263 に答える
1 
    Int64 BigNumber = 9223372036854775807;

    String BigNumberStr = BigNumber.ToString();
    int Sum = 0;

    foreach (Char c in BigNumberStr)
        Sum += (byte)c;

    // 48 is ascii value of zero
    // remove in one step rather than in the loop
    Sum -= 48 * BigNumberStr.Length;
于 2011-03-12T20:28:41.170 に答える
1

はい、おそらくやや非効率的です。おそらく、繰り返し 10 で割って、そのたびに剰余を足し合わせるでしょう。

于 2011-03-11T17:55:56.957 に答える
1

パフォーマンス最適化の第 1 のルール: 代わりに乗算できる場合は、除算しないでください。次の関数は、0 ～ 9999 の 4 桁の数字を取り、要求どおりに実行します。中間計算は 16 ビットを超えています。その数に 1/10000 を掛けて、その結果を Q16 の固定小数点数とします。次に、10 を掛けて整数部分を取ることにより、数字が抽出されます。

#define TEN_OVER_10000 ((1<<25)/1000 +1) // .001 Q25

int sum_digits(unsigned int n)
{
    int c;
    int sum = 0;
    n = (n * TEN_OVER_10000)>>9; // n*10/10000 Q16
    for (c=0;c<4;c++)
    {
    printf("Digit: %d\n", n>>16);
        sum += n>>16;
        n = (n & 0xffff) * 10; // next digit
    }
    return sum;
}

これはより大きなサイズに拡張できますが、注意が必要です。固定小数点計算での丸めが常に正しく機能することを確認する必要があります。また、固定小数点乗算の中間結果がオーバーフローしないように、4 桁の数値も実行しました。

于 2011-03-11T19:20:37.337 に答える
0

int.parse の代わりに、各桁から「0」を引いて実際の値を取得してみませんか。

'9' - '0' = 9 であることを覚えておいてください。したがって、k (数値の長さ) の順序でこれを実行できるはずです。減算は 1 つの操作にすぎないため、速度が低下することはありません。

于 2011-04-23T18:11:07.137 に答える