2

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 raised 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!

1
  • Who is the author, where do you cite it from? Maybe he is known? Aug 29, 2011 at 13:29

3 Answers 3

3

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.

2
  • but log_2(10^200) is not 1200, how do we got that? Aug 29, 2011 at 13:23
  • Crunch it? log_2(10^200) = 200 * log_2(10) ~= 200 * 3 = 600. But the algorithm needs 2 multiplies per step if the remaining exponent is odd at the given step, which explains the additional factor of 2. In general, big O notation doesn't care about constants, so it is often off by a factor between say, .2 and 5. Aug 29, 2011 at 16:03
2

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.

1

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

3
  • In your first algorithm, N is 200, so the number of multiplications is 200, not 10^200. Same for your second algorithm, the number of multiplications is log2(N) = 8.
    – Jerome
    Aug 29, 2011 at 13:33
  • @Jerome, the number a is raised to a 200 digit number ( here 10^200) , I wasn't calculating 10^200. I updated my post so it's more understandable. thx. Aug 29, 2011 at 13:35
  • Enlightening! I think the OP made the same mistake as me. When calculating a^b, we are indeed talking about b=10^200, not b=200.
    – Jerome
    Aug 29, 2011 at 13:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.