What Is the Fastest Way to Compute Large Power of 2 Modulo a Number

How to calculate 2 to the power of a large number modulo another large number?

To calculate the result, the three-argument pow does this efficiently, as mentioned by @MarkDickinson in the comments.

A simplified explanation of how this works:

• to calculate 2**N mod M, first find K = 2**(N//2) mod M
• if N was even, 2**N mod M = K * K mod M
• if N was odd, 2**N mod M = K * K * 2 mod M
  That way, there is no need to calculate huge numbers. In reality, pow uses more tricks, is more general and doesn't need recursion.

Here is some demonstration code:

def pow_mod(B, E, M):
    if E == 0:
        return 1
    elif E == 1:
        return B % M
    else:
        root = pow_mod(B, E // 2, M)
        if E % 2 == 0:
            return (root * root) % M
        else:
            return (root * root * B) % M

M = 115792089237316195423570985008687907853269984665640564039457584007908834671663
E = 96514807760119017459957299373576180339312098253841362800539826362414936958669

print(pow_mod(2, E, M))
print(pow(2, E, M))

C++ : How to calculate modulo of a number raised to large power?

Evaluating 10^n mod M:

What you need is Modular Exponentiation. It can compute (a^b)%m in log_2(b)(log base 2).

Example

Let's say you need to compute 10^9.

1. One way is you sequentially multiple 10, 9 times.

2. Or, use divide and conquer approach.

   10^9 = (10^8)*(10^1)

   10^8 = (10^4)*(10^4) : Do you need to compute 10^4 twice?

   10^4 = (10^2)*(10^2) : Do you need to compute 10^2 twice?

   10^2 = (10^1)*(10^1)

   10^1 = (10^1)*(10^0)

   10^0 is the base case.

   So, what we basically do is:

   1. If power is an odd number, then we compute base^(power-1) and multiply it with base to get base^power. [base^power = (base^(power-1)) * base)]
   2. If power is an even number, then we compute base^(power/2) and multiply it with itself to get base^power. [base^power = (base^(power/2)) * (base^(power/2))]. But we compute base^(power/2) only once.

Computational Complexity:

As stated here:

A brief analysis shows that such an algorithm uses floor(log_2(n)) squarings and
at most floor(log_2(n)) multiplications. More precisely, the
number of multiplications is one less than the number of ones present
in the binary expansion of n.

So, we can say that the runtime is of the order of log_2(n). (O(log_2(power)))

Evaluating the modulo part:

It is easy to notice that while computing a value as large as 10^(10^18), we are bound to overflow even largest of the primitive types (long long int). And here enters the Modular Multiplication, according to which (a * b) % c = ((a % c) * (b % c)) % c. As a side note, you might not see this rule in use when you directly look at code, but it is being used if you evalute the recursive calls.

Problem solved?

We prevent overflow by computing the modulo on the run. Say, if we got some value as 10^9 and we need to multiply it with itself. Overflow? Nah, not this time.

ans = ((10^9 % 1000000007) * (10^9 % 1000000007)) % 1000000007
ans = 10^18 % 1000000007
ans = 49

Code:

While there are multiple implementations, here is a simple one:

const int M = 1e9 + 7;
long long int powxy(long long int x, long long int y) {
    if (y == 0) return 1;
    if (y%2 == 1) return (x*powxy(x, y-1))%M;
    long long int t = powxy(x, y/2);
    return (t*t)%M;
}

Tested here.

Calculating very large power

Looking at the answer on maths.stackexchange where the formula comes from, it appears that the easiest thing to calculate are the a(n).

So, this can be calculated by recurence very simply, and this time, as we only use multiplications and additions, we can take advantage of the rules of modulo arithmetic and keep the numbers we manipulate small:

def s(n, mod):
    a1 = 1
    a2 = 3
    for k in range(n-1):
        a1, a2 = a2, (3*a2 + 2* a1) % mod
    return (a1 + a2) % mod

mod = 1000000007

print(s(10, mod))
# 363314, as with the other formulas...

print(s(10**6, mod))
# 982192189

%timeit s(10**6, mod)
# 310 ms ± 6.46 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit s(10**7, mod)
# 3.39 s ± 93.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

We get the same results as with the other formulas, (which is a really good thing...). As the numbers used during the calculation keep the same size, at most 5 times the modulo, the calculation time is about O(n) - s(10**7) takes only 10 times more time than s(10**6).

How to calculate modulus of large numbers?

Okay, so you want to calculate a^b mod m. First we'll take a naive approach and then see how we can refine it.

First, reduce a mod m. That means, find a number a1 so that 0 <= a1 < m and a = a1 mod m. Then repeatedly in a loop multiply by a1 and reduce again mod m. Thus, in pseudocode:

a1 = a reduced mod m
p = 1
for(int i = 1; i <= b; i++) {
    p *= a1
    p = p reduced mod m
}

By doing this, we avoid numbers larger than m^2. This is the key. The reason we avoid numbers larger than m^2 is because at every step 0 <= p < m and 0 <= a1 < m.

As an example, let's compute 5^55 mod 221. First, 5 is already reduced mod 221.

1. 1 * 5 = 5 mod 221
2. 5 * 5 = 25 mod 221
3. 25 * 5 = 125 mod 221
4. 125 * 5 = 183 mod 221
5. 183 * 5 = 31 mod 221
6. 31 * 5 = 155 mod 221
7. 155 * 5 = 112 mod 221
8. 112 * 5 = 118 mod 221
9. 118 * 5 = 148 mod 221
10. 148 * 5 = 77 mod 221
11. 77 * 5 = 164 mod 221
12. 164 * 5 = 157 mod 221
13. 157 * 5 = 122 mod 221
14. 122 * 5 = 168 mod 221
15. 168 * 5 = 177 mod 221
16. 177 * 5 = 1 mod 221
17. 1 * 5 = 5 mod 221
18. 5 * 5 = 25 mod 221
19. 25 * 5 = 125 mod 221
20. 125 * 5 = 183 mod 221
21. 183 * 5 = 31 mod 221
22. 31 * 5 = 155 mod 221
23. 155 * 5 = 112 mod 221
24. 112 * 5 = 118 mod 221
25. 118 * 5 = 148 mod 221
26. 148 * 5 = 77 mod 221
27. 77 * 5 = 164 mod 221
28. 164 * 5 = 157 mod 221
29. 157 * 5 = 122 mod 221
30. 122 * 5 = 168 mod 221
31. 168 * 5 = 177 mod 221
32. 177 * 5 = 1 mod 221
33. 1 * 5 = 5 mod 221
34. 5 * 5 = 25 mod 221
35. 25 * 5 = 125 mod 221
36. 125 * 5 = 183 mod 221
37. 183 * 5 = 31 mod 221
38. 31 * 5 = 155 mod 221
39. 155 * 5 = 112 mod 221
40. 112 * 5 = 118 mod 221
41. 118 * 5 = 148 mod 221
42. 148 * 5 = 77 mod 221
43. 77 * 5 = 164 mod 221
44. 164 * 5 = 157 mod 221
45. 157 * 5 = 122 mod 221
46. 122 * 5 = 168 mod 221
47. 168 * 5 = 177 mod 221
48. 177 * 5 = 1 mod 221
49. 1 * 5 = 5 mod 221
50. 5 * 5 = 25 mod 221
51. 25 * 5 = 125 mod 221
52. 125 * 5 = 183 mod 221
53. 183 * 5 = 31 mod 221
54. 31 * 5 = 155 mod 221
55. 155 * 5 = 112 mod 221

Therefore, 5^55 = 112 mod 221.

Now, we can improve this by using exponentiation by squaring; this is the famous trick wherein we reduce exponentiation to requiring only log b multiplications instead of b. Note that with the algorithm that I described above, the exponentiation by squaring improvement, you end up with the right-to-left binary method.

a1 = a reduced mod m
p = 1
while (b > 0) {
     if (b is odd) {
         p *= a1
         p = p reduced mod m
     }
     b /= 2
     a1 = (a1 * a1) reduced mod m
}

Thus, since 55 = 110111 in binary

1. 1 * (5^1 mod 221) = 5 mod 221
2. 5 * (5^2 mod 221) = 125 mod 221
3. 125 * (5^4 mod 221) = 112 mod 221
4. 112 * (5^16 mod 221) = 112 mod 221
5. 112 * (5^32 mod 221) = 112 mod 221

Therefore the answer is 5^55 = 112 mod 221. The reason this works is because

55 = 1 + 2 + 4 + 16 + 32

so that

5^55 = 5^(1 + 2 + 4 + 16 + 32) mod 221
     = 5^1 * 5^2 * 5^4 * 5^16 * 5^32 mod 221
     = 5 * 25 * 183 * 1 * 1 mod 221
     = 22875 mod 221
     = 112 mod 221

In the step where we calculate 5^1 mod 221, 5^2 mod 221, etc. we note that 5^(2^k) = 5^(2^(k-1)) * 5^(2^(k-1)) because 2^k = 2^(k-1) + 2^(k-1) so that we can first compute 5^1 and reduce mod 221, then square this and reduce mod 221 to obtain 5^2 mod 221, etc.

The above algorithm formalizes this idea.

how to calculate 2^n modulo 1000000007 , n = 10^9

f(n) = (2*f(n-1)) + 2 with f(1)=1

is equivalent to

(f(n)+2) = 2 * (f(n-1)+2)
         = ...
         = 2^(n-1) * (f(1)+2) = 3 * 2^(n-1)

so that finally

f(n) = 3 * 2^(n-1) - 2

where you can then apply fast modular power methods.

Modulus power of big numbers

some pseudo code

function powermod(base, exponent, modulus) {
    if (base < 1 || exponent < 0 || modulus < 1)
        return -1

    result = 1;
    while (exponent > 0) {
       if ((exponent % 2) == 1) {
           result = (result * base) % modulus;
       }
       base = (base * base) % modulus;
       exponent = floor(exponent / 2);
    }
    return result;
}

and call

powermod(45, x, 257)    

---

Related Topics