6

pow(exponent) メソッドでいくつかのテストを行いました。残念ながら、私の数学のスキルは、次の問題を処理できるほど強力ではありません。

私はこのコードを使用しています：

BigInteger.valueOf(2).pow(var);

結果：

  • 変数 | 時間 (ミリ秒)
  • 2000000 | 11450
  • 2500000 | 12471
  • 3000000 | 22379
  • 3500000 | 32147
  • 4000000 | 46270
  • 4500000 | 31459
  • 5000000 | 49922

見る？2,500,000 の指数は、2,000,000 とほぼ同じ速さで計算されます。4,500,000 は、4,000,000 よりもはるかに高速に計算されます。

何故ですか？

参考までに、BigInteger.pow(exponent) の元の実装を次に示します。

 public BigInteger pow(int exponent) {
    if (exponent < 0)
        throw new ArithmeticException("Negative exponent");
    if (signum==0)
        return (exponent==0 ? ONE : this);

    // Perform exponentiation using repeated squaring trick
        int newSign = (signum<0 && (exponent&1)==1 ? -1 : 1);
    int[] baseToPow2 = this.mag;
        int[] result = {1};

    while (exponent != 0) {
        if ((exponent & 1)==1) {
        result = multiplyToLen(result, result.length, 
                                       baseToPow2, baseToPow2.length, null);
        result = trustedStripLeadingZeroInts(result);
        }
        if ((exponent >>>= 1) != 0) {
                baseToPow2 = squareToLen(baseToPow2, baseToPow2.length, null);
        baseToPow2 = trustedStripLeadingZeroInts(baseToPow2);
        }
    }
    return new BigInteger(result, newSign);
    }
4

3 に答える 3

9

このアルゴリズムは、2乗（squareToLen）と乗算（）を繰り返し使用しmultiplyToLenます。これらの操作が実行される時間は、関係する数値のサイズによって異なります。計算の終わり近くの大きな数の乗算は、最初の乗算よりもはるかにコストがかかります。

乗算は、この条件が真の場合にのみ実行されます((exponent & 1)==1)。平方演算の数は、数値のビット数（先行ゼロを除く）によって異なりますが、乗算は1に設定されたビットに対してのみ必要です。バイナリを見ると、必要な演算がわかりやすくなります。数の表現：

2000000：0000111101000010010000000
2500000：0001001100010010110100000
3000000：00001011011100011011000000
3500000：0001101010110011111100000
4000000：0001111010000100100000000
4500000：0010001001010101000100000
5000000：0010011000100101101000000

2.5Mと4.5Mは、周囲の数値よりも上位ビットが少ないという点で幸運であることに注意してください。次にこれが発生するのは8.5Mです。

8000000：0011110100001001000000000
8500000：0100000011011001100100000
9000000：0100010010101010001000000

スイートスポットは正確に2の累乗です。

1048575：0001111111111111111111111//16408ミリ秒
1048576：0010000000000000000000000//6209ミリ秒
于 2010-05-28T22:47:45.733 に答える
1

推測：

指数はビットごとに処理され、最下位ビットが 1 の場合、追加の作業が行われます。

L を指数のビット数、A をビット数として 1 とすると、t1 は共通部分を処理する時間、t2 は LSbit が 1 の場合の追加の処理時間です。

実行時間は

L t1 + A t2

または、時間はバイナリ表現の 1 の数に依存します。

私の理論を検証するために小さなプログラムを書いています...

于 2010-05-28T22:39:18.647 に答える
1

タイミングを何回実行したかわかりません。一部のコメンターが指摘しているように、良い結果を得るには何度も操作の時間を計る必要があります (それでも間違っている可能性があります)。

うまくタイミングを計ったと仮定すると、数学には多くの近道があることを覚えておいてください。5^6 を計算するために 5*5*5*5*5*5 の操作を行う必要はありません。

これをはるかに迅速に行う 1 つの方法を次に示します。 http://en.wikipedia.org/wiki/Exponentiation_by_squaring

于 2010-05-28T22:40:39.453 に答える