How to efficiently compute large powers of 2?

Question

I'm trying to calculate, for 0 < n ≤ 10⁹, the value of

re=(2^n)%1000000007

I wrote this code:

int main()
{
    int n,i,re=1;
    scanf("%d",&n);
    for(i=0; n>i; i++) re=(2*re)%1000000007;
    printf("%d",re);
}

When n is 10⁹, my code takes too long.

What can I do to make it faster?

Answer 1

You can do it in logarithmic time of n by computing power computation faster.

#include <stdio.h>
#include <stdint.h>

const int kMod = 1000000007;

int Pow(int b, int p) {
    if (p == 0) return 1;
    int x = Pow(b, p >> 1);
    return ((((int64_t)x * x) % kMod) * (p & 1? b : 1)) % kMod;
}

int main()
{
    int n;
    scanf("%d", &n);
    //for(i=0; n>i; i++) re=(2*re)%1000000007;
    int re = Pow(2, n);
    printf("%d\n", re);
    return 0;
}

For example, 2⁵ means computation of x = 2² and x * x * 2.