2

非常に大きな累乗モジュロ (2^32) を計算する必要があります。つまり、次の結果が必要です。

y = (p^n) mod (2^32)

p is a prime number
n is a large integer

Javaでこれを効率的に行うための秘訣はありますか?

それとも、n回の反復でループでそれを行うことに固執していますか?

4

5 に答える 5

4

2 ^ 32を変更する簡単な方法は、を使用すること& 0xFFFFFFFFLです。また、自然に最低の32ビットを保持するタイプがありintます;）これを使用する場合&は、結果が得られるまで実行する必要はありません（したがって、答えは符号なしです）。このため、必要なのは答えの最後の32ビットを保持します。速度を上げるには^n、正方形、正方形、正方形などを計算できます。たとえば、nが0b11111の場合、p ^ 16 * p ^ 8 * p ^ 4 * p ^ 2*pを掛ける必要があります。

intつまり、 32ビットの精度と値のみが必要であり、コストはO（ln n）であるため、プレーンを使用できます。ここnで、は電力です。

int prime = 2106945901;
for (int i = 0; i < 10; i++) {
    long start = System.nanoTime();
    long answer1 = BigInteger.valueOf(prime)
                             .modPow(
                                 BigInteger.valueOf(prime), 
                                 BigInteger.valueOf(2).pow(32)).longValue();

    long mid = System.nanoTime();
    int answer2 = 1;
    int p = prime;
    for (int n = prime; n > 0; n >>>= 1) {
        if ((n & 1) != 0)
            answer2 *= p;
        p *= p;
    }
    long end = System.nanoTime();
    System.out.printf("True answer %,d took %.3f ms, quick answer %,d took %.3f ms%n",
            answer1, (mid - start) / 1e6, answer2 & 0xFFFFFFFFL, (end - mid) / 1e6);
}

最後に印刷します

True answer 4,169,684,317 took 0.233 ms, quick answer 4,169,684,317 took 0.002 ms
于 2012-12-12T08:59:37.417 に答える
4

2乗することで累乗を利用できます。まず、与えられた の 2 の累乗に分解しますn。p^n (mod x) == p^(k1) (mod x) . p^(k2) (mod x) . ... p^(kn) (mod x)whereからsum k_i = n、これと連続する 2 の累乗を利用して、これをO(log n)段階的に計算できます。

于 2012-12-12T07:45:09.313 に答える
3

他の答えに加えて、いくつかの初等数論を使用して、奇数のn mod 2 32をO(1) に計算するのに必要な時間を短縮できます。aオイラーのファイ関数とオイラーの定理を併用すると、n の下位 31 ビットを除くすべてを破棄できます。

φ(2 32 ) = 2 31であり、φ(2 32 ) = 1 mod 2 32です。

したがって、n = q*(2 31 ) + r, 0 <= r < 2 31の場合、a n mod 2 32 = a r mod 2 32

r は単に n の下位 31 ビット、つまりn & 0x7fffffff. 実際、カーマイケルの定理によって、(文字通り) もう少しうまくいくことができ、n の下位 30 ビット、つまりn & 0x3fffffff. これらを一度事前計算して、特定の base に対してサイズ 4 GB のテーブルに格納できますa。例として、Java コードをいくつか示します。

import java.math.BigInteger;

public class PowMod2_32 {

    private static final long MASK32 = 0xffffffffL;

    public static long pow32(final int a, final int exponent)
    {
        int prod = 1;

        for (int i = 29; i>=0; i--) {
            prod *= prod; // square
            if (((exponent >> i) & 1) == 1) {
                prod *= a;  // multiply
            }
        }
        return prod & MASK32;
    }

    public static long pow32(BigInteger a, BigInteger exponent) {
        return pow32(a.intValue(), exponent.intValue());
    }
}
于 2012-12-13T23:57:26.437 に答える
2

私が知っているJavaにはトリックはありませんが、数学にはいくつかのトリックがあります。

これらをアルゴリズムとして実装すると、計算が高速化されるはずです。

5 と 6 を見てください。2 の累乗が常に偶数の場合は 4 も見てください。

于 2012-12-12T07:43:34.120 に答える
-2

クラス Bigintiger を使用します。これがどのように動作するかの例です/それを使って

public String higherPow() {
    BigIntiger i = new Bigintger("2");
    // doing a power(2^32)
    i = i.pow(32);
    // after 2^32 was made, do mod 100
    i = i.mod(new Bigintiger("100"));
    return i.toString();
}
于 2012-12-12T07:43:37.113 に答える