Exponentiation algorithm analysis

Following text is provided about exponentation

We have obvious algorithm to compute X to power N uses N-1 multiplications. A recursive algorithm can do better. N<=1 is the base case of recursion. Otherwise, if n is even, we have xn = xn/2 . xn/2, and if n is odd, x to power of n = x(n-1)/2 x(n-1)/2 x.

Specifically, a 200-digit number is r开发者_JAVA百科aised to a large power (usually another 200-digit number), with only the low 200 or so digits retained after each multiplication. Since the calculations require dealing with 200-digit numbers, efficiency is obviously important. The straightforward algorithm for exponentiation would require about 10 to power of 200 multiplications, whereas recursive algorithm presented requires only about 1,200.

My questions regarding above text 1. How does author came with 10 to power of 200 multiplications for simple alogorithm and recursive algorithm only about 1, 200? How author came with above numbers Thanks!

Because complexity of the first algorithm is linear and of the second is logarithmic (due to N). 200-digit number is about 10^200 and log_2(10^200) is about 1,200.

The exponent has 200 digits, thus it is about 10 to power of 200. If using naive exponentiation you'll have to do this amount of multiplications.

On the other hand, if you use the recursive exponentiation, the number of multiplications depends on exponent's number of bits. Since the exponent is almost 10^200, it has log(10^200) = 200*log(10) bits. This is 600, the 2 in there stems from the fact that if you have a 1 bit you'll have to do two multiplications.

Here are the 2 possible algorithms :

algo gives a^N

SimpleExp(a,N):
   return a*simpleExp(a,N-1) 

so it's N operation, so for a^(10^200) it's 10^200

OptimizedAlgo(a,N):
      if N == 0:
                 return 1
      if (N mod 2) == 0:
                return OptimizedAlgo(a,N/2)*OptimizedAlgo(a,N/2)  // 1 operation
      else:
                return a*OptimizedAlgo(a,(N-1)/2)*OptimizedAlgo(a,(N-1)/2)  //2 operations

here for a^(10^200) you have between log2(N) and 2* log2(N) operations (2^(log2(N) = N )

and log2(10^200) = 200 * log2(10) ~ 664.3856189774724

and 2*log2(10^200) =1328.771237954945

so the number of operations lies between 664 and 1328