Skip to main content

Fast Exponentiation

Write a program to calculate pow(x,n)?

1)Given two integers x and n, you need to find x^n (given that: x and n are small and no overflow takes place)?

A)Naive approach:

since there is no issue of overflow, we can directly multiply x, to itself n times to get the desired result!!

Code-

Add caption

Time Complexity: O(n)
Space Complexity: O(1)

The demerit of this approach is that it is more prone to overflow.
As the values of x and n increases, the value of pow(x,n) becomes too large to be accommodated in int or even long long int.

B)Time Optimization:

The Time complexity of the naive method is O(n), which can further be improved to O(log(n)) by using a divide and conquerer approach.

IDEA: 

if n is even :
    we calculate pow(x*x,n/2);
else :
    we calculate x*pow(x*x,(n-1)/2);

and we do so, till the value of n becomes == 0;

By doing so, we are reducing n by factors of 2, which ultimately will give us the complexity of O(log(n)). 

Code-


Time Complexity: O(log(n)).
Space Complexity: O(1).

C)Modular Exponentiation:

Now that we have seen, different approaches to find pow(x,n); it's time to get rid of the assumption taken in the above two approaches. i.e the assumption that x and n are small.

We will use modular exponentiation to get rid of our assumptions.

Pre-requisite: (a*b)%m=((a%m)*(b%m))%m

Example: (54*36)%25=19.
         (54%25)=4.  and (36%25)=11
         (4*11)%25 = (44%25) = 19.

Code-



Time Complexity: O(log(n)).
Space Complexity: O(1).

This was all about how we can solve pow(x,n), optimally for large values of x,n. Keep Learning!!😊

Comments

Post a Comment

Popular posts from this blog

String tokenizer in C++

Tokenizing a string denotes " splitting " a string with respect to a delimiter. E.g: str = "I love playing PC games!!" tokenized string     =  "I" | "love" | "playing" | "PC" | "games!!" (delimiter = " ") Ways of tokenizing a string in C++ : Using strtok() function : strtok() function splits the string on the basis of delimiter passed to it by the user. Template : strtok(str,<delimiter>)  : will return a char pointer to the first token of the string. ** NOTE : For the second token onward, instead of str, we need to pass a "NULL"; so that we can get the next token from the string. We do so, because; the internal implementation of the strtok() function stores the last starting address of the string passed; and if we keep passing the same string again and again, it will return us back with the same token(1st token) of the string. **NOTE: If we w...
Post a Comment
Read more

INTRODUCTION

Hello Guys!! This is Deepanshu Raj. I am currently pursuing my B.Tech from MNNIT(Motilal Nehru National Institute Of Technology). I am currently a 2nd Year U.G. Since the start of my second year in college, I had this wish in my heart, to write something of my own. Recently, I have gotten myself into the world of competitive coding. Well, Not being Much aware of what to do, and what not to; right from the start of the college, I faced a lot of difficulties starting (from learning a computer language, to understanding the intricacies of competitive coding). And in my way to this day from the day I started to code for the first time, I learnt a lot many things. So I decided, to mix my bit of knowledge and experience at coding, and in general competitive coding with this world full of tech talents. This blog consists of all the important, explanations and applications of various data Structures and Algorithms used in competitive Programming.             ...
2 comments
Read more