Q: List and compare the methods to compute where a, b, n are positive integers.
A: We have four methods. The first one is to naively compute the value but this is unprofessional and does not work if is very large that might overflow (e.g. a 32-bit or 64-bit cannot hold numbers like .
However, in Python, if you write math expressions like the following, it will still work, I guess the implementation does not bruteforce compute the
print 2**999999%147
The answer 50 is computed almost instantly. However, if you write.
print 2**999999
The python console almost hangs.. So it is obvious a hidden power-mod rule applies. So the first function is simple but yet only ‘OK’ in Python. This certainly does not work for some other programming languages if the code is translated and compiled as the way it looks e.g. compute and do the module operator.
def powermod1(a, b, n): return a**b%n
The second method is to apply multiplication and mod iteratively for . Decompose this into a for loop that do multiplication with number a, b times. In order to avoid that becomes large, use % at each step which does not affect the final result. Therefore, the following is memory-efficient.
def powermod2(a, b, n): r = 1 for i in xrange(b): r = r * a % n return r
The third method and the fourth method are both based on the following property.
For any positive integers, a > 0, b > 0, n > 0, .
Therefore, the non-recurisve method decomposes the exponential value.
def powermod3(a, b, n): r = 1 while b > 0: if b & 1 == 1:# odd number r = r * a % n b /= 2 a = a * a % n return r
while the recursive presents the same idea.
def powermod4(a, b, n): if b == 1: return a % n r = powermod4(a, b / 2, n) r = r * r % n if (b & 1) == 1: # odd number r = r * a % n return r
Both approaches ensures the algorithm complexity of . The fourth method has one recurisve call that has half exponent (reduced complexity). For example, where and .
The following lists all these four methods and use package time to measure the performances. Be noted that we pick a relatively large exponent so a difference in time can be noticed. For small exponents, there is not much noticable performance difference on modern PCs.
#!/usr/bin/env python # https://helloacm.com from time import time def powermod1(a, b, n): return a**b%n def powermod2(a, b, n): r = 1 for i in xrange(b): r = r * a % n return r def powermod3(a, b, n): r = 1 while b > 0: if b & 1 == 1: r = r * a % n b /= 2 a = a * a % n return r def powermod4(a, b, n): if b == 1: return a % n r = powermod4(a, b / 2, n) r = r * r % n if (b & 1) == 1: r = r * a % n return r a = 2 b = 99999999 c = 147 starttime = time() print powermod1(a, b, c) print time() - starttime starttime = time() print powermod2(a, b, c) print time() - starttime starttime = time() print powermod3(a, b, c) print time() - starttime starttime = time() print powermod4(a, b, c) print time() - starttime
One output on Intel i7, Win7-64 bit, 16GB, Python 2.7 is
134 0.713000059128 134 7.82999992371 134 0.00400018692017 134 0.00300002098083
The third and last methods present the best performances.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Clone the MAC address in Wireless Router
Next Post: BrainFuck Interpreter, C# Console Application
> The python console almost hangs.. So it is obvious a hidden power-mod rule applies.
You are wrong 2**99999 % 50 is computed as simple exponentiation and then taking modulo, python does not do any optimization here. However if you write pow(2, 99999, 50) – you will get indeed the optimized version.
Why then 2**99999 % 50 is immediate, while 2**99999 hangs? You should have written x = 2**99999 then the time will be the same (and even less). If you write simply 2*99999 in the console, python has to convert the number from the internal representation into decimal to print it, that’s why it hangs.