Qual è il modo più veloce per calcolare una grande potenza di 2 modulo un numero

Question

Per 1 <= N <= 1000000000, ho bisogno di calcolare 2N mod 1000000007, e deve essere veramente veloce!
mio approccio attuale è:

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

ma non sembra essere abbastanza veloce. Qualche idea?

Answer 1

Controllare exponentiation by squaring e metodo binario di modular exponentiation

Answer 2

È possibile risolverlo in O(log n).

Ad esempio, per n = 1234 = 10011010010 (in base 2) abbiamo n = 2 + 16 + 64 + 128 + 1024, e quindi 2^n = 2^2 * 2^16 * 2^64 * 2^128 * 2^1024.

Nota che 2^1024 = (2^512)^2, in modo che, dato che conosci 2^512, puoi calcolare 2^1024 in un paio di operazioni.

La soluzione sarebbe qualcosa come questo (pseudocodice):

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

noti che O(log n) è, in pratica, per O(1)ulong argomenti (come log n < 63); e che questo codice è compatibile con qualsiasi MODULO uint (MODULO < 2^32), indipendentemente dal fatto che MODULO sia primo o meno.

Answer 3

Questo sarà più veloce (codice 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 4

Si può essere risolto in O ((log n)^2). Prova questo approccio: -

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

Questo è un approccio ricorsivo ed è abbastanza abbastanza veloce per soddisfare i requisiti di tempo nella maggior parte delle gare di programmazione.

Answer 5

Questo metodo non utilizza la ricorsione con complessità O (log (n)). Controllalo.

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

E questo è pseudo da Wikipedia (vedi da destra a sinistra binario sezione Metodo)

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

Se u vuole anche per memorizzare tale matrice cioè. (2^I)% mod [i = 0 a qualunque cosa] che:

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

Spero che sarà utile a qualcuno.