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

问题描述

有关 1＆LT; = N ＆LT; = 10亿，我需要计算 2 <我> N 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?

推荐答案

通过平方和二进制方法检查幂< A HREF =htt​​p://en.wikipedia.org/wiki/Modular_exponentiation>模幂

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