Cách nhanh nhất để tính toán công suất lớn của 2 modulo là số

Question

Đối với 1 <= N <= 1000000000, tôi cần tính 2N mod 1000000007 và phải thật nhanh!
cách tiếp cận hiện tại của tôi là:

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

nhưng nó dường như không đủ nhanh. Bất kỳ ý tưởng?

Answer 1

Kiểm tra exponentiation by squaring và phương pháp nhị phân của modular exponentiation

Answer 2

Bạn có thể giải quyết trong O(log n). Ví dụ, đối với n = 1234 = 10011010010 (trong cơ sở 2), chúng tôi có n = 2 + 16 + 64 + 128 + 1024, và do đó 2^n = 2^2 * 2^16 * 2^64 * 2^128 * 2^1024.

Lưu ý rằng 2^1024 = (2^512)^2, do đó, cho bạn biết 2^512, bạn có thể tính 2^1024 trong một vài thao tác.

Các giải pháp sẽ là một cái gì đó như thế này (giả):

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

Lưu ý rằng O(log n) là, trong thực tế, O(1) cho ulong đối số (như log n < 63); và mã này tương thích với bất kỳ uint MODULO (MODULO < 2^32), độc lập cho dù MODULO là nguyên tố hay không.

Answer 3

này sẽ nhanh hơn (mã trong 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

Nó có thể được giải quyết trong thời gian O ((log n)^2). Hãy thử phương pháp này: -

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

Đây là một cách tiếp cận đệ quy và là khá đủ nhanh để đáp ứng yêu cầu thời gian trong hầu hết các cuộc thi lập trình.

Answer 5

Phương pháp này không sử dụng đệ quy với độ phức tạp O (log (n)). Kiểm tra này ra.

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

Và đây là giả từ Wikipedia (xem Right-to-left nhị phân phần phương pháp)

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

Nếu u cũng muốn lưu trữ rằng mảng tức. (2^i)% mod [i = 0 thành bất kỳ điều gì] hơn:

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

Tôi hy vọng nó sẽ hữu ích cho ai đó.