What is the fastest way to calculate a large power 2 modulo a number

Question

For 1 <= N <= 1000000000 I need to calculate 2 N mod 1000000007 , and it should be very fast!
My current approach:

 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 he doesn't seem fast enough. Any idea?

Answer 1

Check exponentiation and binary modular exponentiation

Answer 2

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

Answer 3

This method does not use recursion with complexity O (log (n)). Check this.

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

And this is a pseudo from Wikipedia (see the Binary Method from Right to Left section)

 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 

Answer 4

You can solve it in O(log n) .

For example, for n = 1234 = 10011010010 (in base 2) we have n = 2 + 16 + 64 + 128 + 1024 and, therefore, 2 ^ n = 2 ^ 2 * 2 ^ 16 * 2 ^ 64 * 2 ^ 128 * 2 ^ 1024.

Note that 2 ^ 1024 = (2 ^ 512) ^ 2, so if you know 2 ^ 512, you can calculate 2 ^ 1024 in a couple of operations.

The solution will be like this (pseudo-code):

 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 // (eg 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; } 

Note that O(log n) in practice O(1) for ulong arguments (like log n <63); and that this code is compatible with any uint MODULO (MODULO <2 ^ 32), regardless of whether MODULO is simple or not.

Answer 5

It can be solved in O ((log n) ^ 2). Try this approach: -

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

This is a recursive approach and quickly enough to meet the demands of the times in most programming competitions.

Answer 6

If u also wants to keep this array, i.e. (2 ^ i)% mod [i = 0 to any] than:

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

I hope this will be helpful to someone.