2

私はここでSRM573のソリューションでこの機能を見てきました：

long modPow(long x, long y)
{
    //Caculates x raised to the y-power modulo MOD
    //in O(log(y)) time by using  repeated squaring
    long r = 1;
    while(y > 0){
        if( (y&1) != 0) {
            r = (r * x) % MOD;
        }
        x = (x * x)%MOD;
        y >>= 1;
    }
    return r;
}

しかし、 ;のモジュラー値を計算するこの関数に混乱しています。x^y%MOD
関数になぜx = (x * x)%MOD;必要なのですか？
それは私には意味がありません。

4

4 に答える 4

1

tl; dr：これは最適化です。

xが2で、MODが3であると想像してください。xが使用されるのはrにxを掛けることだけであることに注意してください。

ここで、xを2乗するとします。x * x =4。これで、r * 4％3は1、2、3、4、5 ...に等しくなります（r = 1、2、3、4、5 ...の場合）。xが1の場合と同じです。実際、xをx*xだけでなくx*x％3に設定すると、同じ結果が得られます。

しかし、次のステップはどうですか？4 * 4 = 16、％3 = 1. 1 * 1 = 1、％3も= 1です。したがって、操作を早めに、遅めに、またはまったく行わない場合でも、同じ残差でスタックします。

于 2013-03-27T02:32:17.597 に答える
1
于 2013-03-27T03:34:53.037 に答える
0

Elaborating a little on @jwpat7 's answer, let's think about why

(x % MOD)*(x % MOD) ≡ (x*x) % MOD.

We can always write x as x = n*MOD + r for some naturals n and r with r < MOD (if also x < MOD that implies x = r and n = 0).

Now, we always get x % MOD = (n*MOD + r) % MOD = r, and therefore we get

(x % MOD)*(x % MOD) = r * r.

On the other hand, consider what (x*x) % MOD evaluates to:

x*x = (n*MOD + r)*(n*MOD +r) = n*n*MOD*MOD + 2*n*r*MOD + r*r, and therefore we get (x*x) % MOD = (n*n*MOD*MOD + 2*n*r*MOD + r*r) % MOD = r*r

This is why Patashu said that it doesn't matter whether you apply the modulo operator early or late, because the remainder r is all that is actually relevant to the modulo operation and is also the only thing that carries over to the next iteration.

于 2013-03-27T03:44:41.950 に答える
0

Forget about the modular part for a while, and ask yourself, “How can I efficiently calculate x^n for n a positive integer?” You can calculate x^2 with one multiplication: x * x. You can calculate x^3 with two multiplications: x^3 = x * x^2. You can calculate x^4 with two multiplications: x^4 = x^2^2 = x^2 * x^2. You can calculate x^n in general with this recursion:

For even n = 2*m, x^n = (x^2)^m.

For odd n = 2*m + 1, x^n = x * (x^m)^2.

So, we get x^10 as:

x^10 = (x^2)^5
     = x^2 * (x^4)*2

Compute x^2, x^4, x^8, x^10, for 4 multiplications.

Note that this is a good general method, but it is not guaranteed to be the most efficient. Try x^15, for example. This method gives you x * (x^2)^7 = x * x^2 * (x^2)^6 = x * x^2 ^ (x^4)^3 = x ^ x^2 * x^4 * (x^4)^2. You compute x^2, x^4, x^8, and then x * x^2 * x^4 * x^8, for 6 multiplications. Faster is 

y = x^3 = x * x^2, 2 multiplications.
x^15 = y^5 = y * (y^2)^2, 3 more multiplications,
This is a total of 5 multiplications.

In fact, for an exponent n, define an addition chain as a sequence of numbers starting at 1 and ending at n, where each number in the list is the sum of 2 previous numbers in the sequence (and you can repeat).

The algorithm for 15 gives

1, 2, 3, 6, 7, 14, 15.

The shorter one is

1, 2, 3, 6, 12, 15.

It turns out to be computationally hard to find the shortest addition chain ending at a target number.

于 2013-03-27T04:22:12.007 に答える