Fast Exponentiation in Python

Topic: Fast exponentiation in Python.

What is Exponentiation?

Well, if you want to compute the power of some number in respect to some other number, that is called exponentiation. Now, if we want to compute 2^4 or pow(2,4) , then in general what we will do …….

Simply, run a loop from 1 to 4 and multiply 2 that no of times. So, below is the approach where we can compute the power value.

#Compute power(a,b)
s=1
for i in range(b):
    s=s*a
return s

So, in the above approach, the complexity would be O(b).

Now, how we can minimize the complexity. For that, we will learn here Fast Exponentiation.

What is Fast Exponentiation?

In this approach, we will simply divide our algorithm in the following steps. Here if we want to compute some power then we will simply divide the power value in the below manner.

You may learn: Math module of python

How to find Fast Exponentiation in Python

Let us take an example of pow(2,10). In the above approach of normal expo we have to run our loop 10 times. Now, what if we perform fast expo here..

P(2,10) ——-> (2^5)^2

p(2,5) ———> (2^2)^2 * 2

P(2,2) ———> 2 * 2

Now , we  can see that the previous computation of the power can be done in only 3 steps. Isn’t it cool?

Let us simply take a look at the algorithm/code below.

In general, the algorithm will be like:

  1. If we compute pow(a,2n), then it would be (a^n)^2
  2. If we compute pow(a,2n+1), then it would be (a^n)^2 * a

Here is the code below in Python :

#Fast Expo In Python ------ <Codespeedy>
def Power(a,n):
    if(n==0):
      return 1
    x=power(a,n/2)
    x=x*x
    if(n%2==1):
      x=x*a
    return x
a=2 #Input 1
n=4 #Input 2
print(Power(a,n))

#Output : 16

 

Time Complexity of Fast Exponentiation is O(logn). You can easily find that in our above example where we have reduce a 10 step problem into 3 steps.

I hope you have liked the article and thanks for reading!!!!!

Leave a Reply

Your email address will not be published. Required fields are marked *