¿Cuál es la forma más rápida de calcular la potencia grande de 2 módulo un número

Question

Para 1 <= N <= 1000000000, necesito calcular 2N mod 1000000007, y debe ser realmente rápido!
Mi enfoque actual es:

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

pero no parece ser lo suficientemente rápido. ¿Alguna idea?

Answer 1

Comprobar exponentiation by squaring y método binario de modular exponentiation

Answer 2

Puede resolverlo en O(log n).

Por ejemplo, para n = 1234 = 10011010010 (en la base 2) tenemos n = 2 + 16 + 64 + 128 + 1024, y por lo tanto 2^n = 2^2 * 2^16 * 2^64 * 2^128 * 2^1024.

Tenga en cuenta que 2^1024 = (2^512)^2, de modo que, dado que conoce 2^512, puede calcular 2^1024 en un par de operaciones.

La solución sería algo como esto (pseudocódigo):

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

Tenga en cuenta que O(log n) es, en la práctica, O(1) para ulong argumentos (como log n < 63); y que este código es compatible con cualquier uint MODULO (MODULO < 2^32), independientemente de si MODULO es principal o no.

Answer 3

Esto será más rápido (código en 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 4

Se puede resolverse en O ((log n)^2). Pruebe este enfoque: -

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

Este es un enfoque recursivo y es bastante lo suficientemente rápido como para satisfacer los requisitos de tiempo en la mayor parte de las competencias de programación.

Answer 5

Este método no utiliza recursividad con complejidad O (log (n)). Mira esto.

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

Y esto es seudo desde Wikipedia (ver de derecha a izquierda binaria sección del método)

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 6

U Si también desea almacenar esa matriz es decir. (2^i) mod% [i = 0 a lo que sea] que:

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

espero que va a ser útil a alguien.