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
– willeM_ Van Onsem, Commented Dec 10, 2015 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
– willeM_ Van Onsem, Commented Dec 10, 2015 at 20:42
@CommuSoft: Unless you have googols of bytes of RAM, bignums aren't going to cut it. — user2357112
– user2357112, Commented Dec 10, 2015 at 20:46
@jboyda5, You don't need to write this function. Use the built-in pow(). — Mark Tolonen
– Mark Tolonen, Commented Dec 10, 2015 at 20:59

Community · Accepted Answer · 2017-05-23 12:15:47Z

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.

Espoir Murhabazi · Accepted Answer · 2017-06-23 08:44:13Z

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')

Collectives™ on Stack Overflow

Using recursion to calculate powers of large digit numbers

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related