java.math.biginteger pow（exponent）質問

StackOverflow https://stackoverflow.com/questions/2932869

  •  05-10-2019
  •  | 
  •  

質問

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

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

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

結果：

  • var | MSの時間
  • 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);
    }
役に立ちましたか？

解決

アルゴリズムは繰り返される二乗を使用します（squareToLen）および乗算（multiplyToLen）。これらの操作が実行される時間は、関連する数値のサイズによって異なります。計算の終わり近くの多数の乗算は、最初のものよりもはるかに高価です。

乗算は、この条件が真である場合にのみ行われます。 ((exponent & 1)==1). 。正方形の操作の数は、数のビット数（主要なゼロを除く）に依存しますが、1に設定されたビットには乗算は必要です。数の表現：

2000000: 0000111101000010010000000
2500000: 0001001100010010110100000
3000000: 0001011011100011011000000
3500000: 0001101010110011111100000
4000000: 0001111010000100100000000
4500000: 0010001001010101000100000
5000000: 0010011000100101101000000

2.5mと4.5mは、周囲の数字よりも高いビットセットが少ないという点で幸運であることに注意してください。次回これが起こるのは8.5mです：

8000000: 0011110100001001000000000
8500000: 0100000011011001100100000
9000000: 0100010010101010001000000

スイートスポットは2の正確なパワーです。

1048575: 0001111111111111111111111 // 16408 ms
1048576: 0010000000000000000000000 //  6209 ms

他のヒント

ただの推測：

指数は少しずつ処理され、最小の重要なビットが1つの追加作業が完了します。

lが指数のビット数、aが1とt1のビット数である場合、共通部分を処理する時間、t2がLSBitが1の場合の追加時間処理を処理する場合の場合

その後、実行時間はそうなるでしょう

lT1 + aT2

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

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

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

あなたが物事をうまくやり遂げたと仮定すると、数学で取ることができる多くのショートカットがあることを忘れないでください。 5^6を計算するには、5*5*5*5*5*5操作を行う必要はありません。

これをより迅速に行う方法の1つは次のとおりです。 http://en.wikipedia.org/wiki/exponentiation_by_squaring

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top