什么是计算大的2次幂模一个数最快的方法？

Question

什么是计算大的2次幂模一个数最快的方法？

9

对于 1 <= N <= 1000000000，我需要计算 2^N mod 1000000007，并且计算速度必须非常快！
我的当前方法是：

ull power_of_2_mod(ull n) {
    ull result = 1;
    if (n <= 63) {
        result <<= n;
        result = result % 1000000007;
    }
    else {
        ull one = 1;
        one <<= 63;
        while (n > 63) {
            result = ((result % 1000000007) * (one % 1000000007)) % 1000000007;
            n -= 63;
        }

        for (int i = 1; i <= n; ++i) {
            result = (result * 2) % 1000000007;
        }

    }

    return result;
}

但是似乎速度不够快，有什么想法？

- roxrook

在我看来，这看起来非常不错。也许我会删除第一个“if”，即始终转到一般情况。 - valdo

1

这是一个数学问题... 1000000007 是素数，你应该在这里看一下：http://www.math.sunysb.edu/~scott/blair/Powers_modulo_prime.html - astreal

请查看平方取幂算法和模指数运算的二进制方法。 - MBo

@astreal：非常感谢。我应该注意“prime”，真是太丢人了！ - roxrook

可能是重复的问题：如何计算2^n模1000000007，其中n = 10^9 - phuclv

5个回答

6

这种方法不使用递归，时间复杂度为O(log(n))。看看这个。

#define ull unsigned long long
#define MODULO 1000000007

ull PowMod(ull n)
{
    ull ret = 1;
    ull a = 2;
    while (n > 0) {
        if (n & 1) ret = ret * a % MODULO;
        a = a * a % MODULO;
        n >>= 1;
    }
    return ret;
}

这是来自维基百科的伪代码（见从右到左二进制方法部分）

function modular_pow(base, exponent, modulus)
Assert :: (modulus - 1) * (base mod modulus) does not overflow base
result := 1
base := base mod modulus
while exponent > 0
    if (exponent mod 2 == 1):
       result := (result * base) mod modulus
    exponent := exponent >> 1
    base := (base * base) mod modulus
return result

- Freaking Prime

@chux a*a < 1000000007^2 < 2^60，而long long的极限是2^63，所以不用担心。 - Freaking Prime

是的 - 对于 OP 的范围 "1 <= N <= 1000000000"，a*a < N*N 没有问题。只适用于 ull 值大于等于 pow(2,32)。 - chux - Reinstate Monica

5

你可以用 O(log n) 的时间复杂度解决它。

例如，对于 n = 1234 = 10011010010（二进制），我们有 n = 2 + 16 + 64 + 128 + 1024，因此 2^n = 2^2 * 2^16 * 2^64 * 2^128 * 2 ^ 1024。

请注意，2^1024 = (2^512)^2，因此如果你知道 2^512，你可以在几个操作中计算出 2^1024。

一个解决方案可能是这样的（伪代码）：

const ulong MODULO = 1000000007;

ulong mul(ulong a, ulong b) {
    return (a * b) % MODULO;
}

ulong add(ulong a, ulong b) {
    return (a + b) % MODULO;
}

int[] decompose(ulong number) {
    //for 1234 it should return [1, 4, 6, 7, 10]
}

//for x it returns 2^(2^x) mod MODULO
// (e.g. for x = 10 it returns 2^1024 mod MODULO)
ulong power_of_power_of_2_mod(int power) {
    ulong result = 1;
    for (int i = 0; i < power; i++) {
        result = mul(result, result);
    }
    return result;
}

//for x it returns 2^x mod MODULO
ulong power_of_2_mod(int power) {
    ulong result = 1;
    foreach (int metapower in decompose(power)) {
        result = mul(result, power_of_power_of_2_mod(metapower));
    }
    return result;
}

请注意，对于参数（因为log n <63），O(log n)在实践中实际上是O(1)；而且这段代码与任何模数(MODULO <2 ^ 32)兼容，无论MODULO是否是质数。

- penartur

1

它可以在O((log n)^2)的时间内解决。尝试以下方法：-

unsigned long long int fastspcexp(unsigned long long int n)
{
    if(n==0)
        return 1;
    if(n%2==0)
        return (((fastspcexp(n/2))*(fastspcexp(n/2)))%1000000007);
    else
        return ( ( ((fastspcexp(n/2)) * (fastspcexp(n/2)) * 2) %1000000007 ) ); 
}

这是一种递归方法，足够快以满足大多数编程竞赛的时间要求。

- nikoo28

O(log(n)^2)的方法。你确定不应该手动消除公共子表达式吗？ - Aki Suihkonen

0

如果您也想存储该数组，即 (2^i)%mod [i=0 到任意值]，那么：

long mod = 1000000007;
long int pow_mod[ele]; //here 'ele' = maximum power upto which you want to store 2^i
pow_mod[0]=1; //2^0 = 1
for(int i=1;i<ele;++i){
    pow_mod[i] = (pow_mod[i-1]*2)%mod;
}

我希望这对某人有所帮助。

- Polish

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alexey Frunze · Accepted Answer

这是更快的方法（使用C代码）：

typedef unsigned long long uint64;

uint64 PowMod(uint64 x, uint64 e, uint64 mod)
{
  uint64 res;

  if (e == 0)
  {
    res = 1;
  }
  else if (e == 1)
  {
    res = x;
  }
  else
  {
    res = PowMod(x, e / 2, mod);
    res = res * res % mod;
    if (e % 2)
      res = res * x % mod;
  }

  return res;
}