计算 2 模数的大幂的最快方法是什么 [英] What is the fastest way to compute large power of 2 modulo a number

问题描述

对于 1 <= N <= 1000000000，我需要计算 2N mod 1000000007，它一定非常快！
我目前的做法是:

For 1 <= N <= 1000000000, I need to compute 2N mod 1000000007, and it must be really fast!
My current approach is:

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;
}

但它似乎不够快.有什么想法吗?

but it doesn't seem to be fast enough. Any idea?

推荐答案

这样会更快(C 代码):

This will be faster (code in 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;
}

这篇关于计算 2 模数的大幂的最快方法是什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！