Using recursion to calculate powers of large digit numbers

Question

The goal is to calculate large digit numbers raised to other large digit numbers, e.g., 100 digit number raised to another 100 digit number, using recursion.

My plan was to recursively calculate exp/2, where exp is the exponent, and making an additional calculation depending on if exp is even or odd.

My current code is:

def power(y, x, n):
    #Base Case
    if x == 0:
        return 1

    #If d is even
    if (x%2==0): 
        m = power(y, x//2, n)
        #Print statment only used as check
        print(x, m)
        return m*m

    #If d is odd
    else:
        m = y*power(y, x//2, n)
        #Print statement only used as check
        print(x, m)
        return m*m

The problem I run into is that it makes one too many calculations, and I'm struggling to figure out how to fix it. For example, 2^3 returns 64, 2^4 returns 256, 2^5 returns 1024 and so on. It's calculating the m*m one too many times.

Note: this is part of solving modulus of large numbers. I'm strictly testing the exponent component of my code.

Your indentation is (at least on the question side) incorrect. — Willem Van Onsem, Dec 10 '15 at 20:37
Furthermore what do you mean with *too many*. Please provide an example and show which statements you think should not be there... — Willem Van Onsem, Dec 10 '15 at 20:42
That's not your goal. Your real goal is to compute some function of this ridiculously huge, impossible-to-represent exponential. Maybe you want to find its last digit, or some other property. You don't need, and you cannot possibly hope to compute, the whole thing. — user2357112, Dec 10 '15 at 20:43
@user2357112: well you can using big integers, that use an arbitrary amount of memory. But the point is indeed that it is - in many cases - simply useless. — Willem Van Onsem, Dec 10 '15 at 20:44
@CommuSoft: Unless you have googols of bytes of RAM, bignums aren't going to cut it. — user2357112, Dec 10 '15 at 20:46
"Note: this is part of solving modulus of large numbers" - yep, of course. Probably something like Project Euler, right? You can't break this problem into exponentiation and modulus parts separately; you need to do something more sophisticated. — user2357112, Dec 10 '15 at 20:50
Just use `pow()`. It is a built-in function that computes `pow(x,y) -> x**y` but with three parameters computes `pow(x,y,z) -> (x**y)%z`. It is efficient for huge numbers. — Mark Tolonen, Dec 10 '15 at 20:51
@user2357112 yeah, I'm simply changing the return statement to 'return m*m % n' — jboyda5, Dec 10 '15 at 20:52
@jboyda5: that's not gonna fix it. Arithmetic on huge number takes huge amounts of memory and processing time. The solution is more sophisticated. — Willem Van Onsem, Dec 10 '15 at 20:53
@CommuSoft the program runs almost near instantaneously by adding % n to my return statement, it's just producing the wrong result as it calculates m*m one too many times. And my test numbers are all 100 digit numbers. — jboyda5, Dec 10 '15 at 20:57
@jboyda5, You don't need to write this function. Use the built-in `pow()`. — Mark Tolonen, Dec 10 '15 at 20:59
@jboyda5: I've added an answer that explains the error and provides a way to calculate this much faster. — Willem Van Onsem, Dec 10 '15 at 21:03
@MarkTolonen Thanks! I was unaware of the 3 parameters. Is there source code for that so I can see how it works so I can understand where I went wrong in my attempt? — jboyda5, Dec 10 '15 at 21:03
@MarkTolonen: there is indeed a builtin, but this is part of *Project Euler* and it is not much use by making a delegate to a builtin only. The aim is to understand what is exploited, etc. — Willem Van Onsem, Dec 10 '15 at 21:03
@MarkTolonen: I think you have to read through the comments. — Willem Van Onsem, Dec 10 '15 at 21:25

score 1 · Accepted Answer · edited May 23 '17 at 12:15

First of all there is a weird thing with your implementation: you use a parameter n that you never use, but simply keep passing and you never modify.

Secondly the second recursive call is incorrect:

else:
    m = y*power(y, x//2, n)
    #Print statement only used as check
    print(x, m)
    return m*m

If you do the math, you will see that you return: (y y^x//2)²=y^2*(x//2+1) (mind the // instead of /) which is thus one y too much. In order to do this correctly, you should thus rewrite it as:

else:
    m = power(y, x//2, n)
    #Print statement only used as check
    print(x, m)
    return y*m*m

(so removing the y* from the m part and add it to the return statement, such that it is not squared).

Doing this will make your implementation at least semantically sound. But it will not solve the performance/memory aspect.

Your comment makes it clear that you want to do a modulo on the result, so this is probably Project Euler?

The strategy is to make use of the fact that modulo is closed under multiplication. In other words the following holds:

(a b) mod c = ((a mod c) * (b mod c)) mod c

You can use this in your program to prevent generating huge numbers and thus work with small numbers that require little computational effort to run.

Another optimization is that you can simply use the square in your argument. So a faster implementation is something like:

def power(y, x, n):
    if x == 0: #base case
        return 1
    elif (x%2==0): #x even 
        return power((y*y)%n,x//2,n)%n
    else: #x odd
        return (y*power((y*y)%n,x//2,n))%n

If we do a small test with this function, we see that the two results are identical for small numbers (where the pow() can be processed in reasonable time/memory): (12347**2742)%1009 returns 787L and power(12347,2742,1009) 787, so they generate the same result (of course this is no proof), that both are equivalent, it's just a short test that filters out obvious mistakes.

Thanks for all the help. I was under the assumption that by multiplying y by power(y, x, n) would produce the same result as multiplying y in the return statement. — jboyda5, Dec 10 '15 at 21:06

score 0 · Answer 2 · answered Jun 23 '17 at 08:44

here is my approach accornding to the c version of this problem it works with both positives and negatives exposents:

def power(a,b):
  """this function will raise a to the power b but recursivelly"""
  #first of all we need to verify the input
  if isinstance(a,(int,float)) and isinstance(b,int):
    if a==0:
      #to gain time
      return 0
    if b==0:
        return 1
    if b >0:
      if (b%2==0): 
      #this will reduce time by 2 when number are even and it just calculate the power of one part and then multiply 
        if b==2:
          return a*a
        else:
          return power(power(a,b/2),2)
      else:
      #the main case when the number is odd
        return a * power(a, b- 1)
    elif not b >0:
      #this is for negatives exposents
      return 1./float(power(a,-b))
  else:
    raise TypeError('Argument must be interfer or float')

Using recursion to calculate powers of large digit numbers

2 Answers2

Linked