Finding Exponent of a Number [5 approaches]

TABLE OF CONTENTS

• What is an Exponent?
• Understanding Problem Stamement
• Solution Approaches and Implimentations
  1. Naive Approach
  2. Recursive Approach
  3. Divide and Conquer approach
  4. Optimized Divide and Conquer
  5. Binary Operator Approach
• Applications
• Conclusion

Exponent is a method of expressing large numbers in terms of powers. It refers to how many times a number is multiplied by itself.

Understand the problem we have solved in this article:

• Given two numbers a and n, assume them to be small so that overflow doesn't happen in any case.
• We need to write a function exp(a,n) to compute a^n.
• We can use inbuilt pow() function, provided by C++ but in this article we will be seeing the logical way to find exponent.

Examples:

1. Input : a = 5, n = 2
   Output : 25
2. Input : a = 7, n = 0
   Output : 1

There are several approaches to solve this problem, lets look them one-by-one:

1. Naive Approach

A simple solution to calculate exp(a, n) would multiply 'a' exactly n times. We can do that by using a simple for loop.

Steps

1. Start with the base number(a) and the exponent (n)that you want to calculate.
2. There are two base cases at the beginning of the function:
   If 'n' is 0, it returns 1 because anything raised to the power of 0 is 1.
   If 'n' is 1, it returns 'a' itself because anything raised to the power of 1 is the base 'a'.
3. If 'n' is greater than 1 (i.e., neither of the base cases applies), it enters a loop that runs from 'i = 2' to 'n - 1'. This loop is supposed to multiply 'a' by itself 'n-1' times to calculate 'a' raised to the power of 'n'.
4. Finally, the function returns the result after the loop completes.

Implementation in C++

#include bits/stdc++.h
using namespace std;

long exp(int a, unsigned n)
{
	//Base Cases
        if(n == 0) return 1;
        if(n == 1) return a;

	// Multiply a for n times
	for (int i = 2; i < n; i++) {
		exp = exp * a;
	}

	return exp;
}

// Driver code
int main(void)
{

	int a = 5;
	unsigned n = 2;

	// Function call
	int result = exp(a, n);
	cout << result << endl;

	return 0;
}

Output: 25

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

2. Finding exponent using Recursion

We can use the same approach as above but instead of an iterative loop, we will use recursion for the purpose.

Why Recursion? For a recursive function, we only need to define the base case and recursive case, so the code becomes simpler and shorter than an iterative code.

Steps
1.Base Case for Exponent 0 and Base 0:

If 'n' is equal to 0, the function returns 1. This is because any non-zero number raised to the power of 0 is 1.
If 'a' is equal to 0, the function returns 0. This is because 0 raised to any power (except 0) is 0.

2. Recursive Call:

For all other cases, the function calculates 'a' raised to the power of 'n' using a recursive call.
The recursive call subtracts 1 from 'n' and multiplies 'a' by the result of the function call with the updated 'n'. This is because 'a^n' can be expressed as 'a * a^(n-1)'.

3. Recursive Breakdown:

The recursive function continues breaking down the problem until it reaches one of the base cases (either 'n' becomes 0 or 'a' becomes 0). When it does, it returns the appropriate value as per the base case.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

int exp(int a, int n)
{
	// If a^0 return 1
	if (n == 0)
		return 1;
	// If we need to find of 0^b
	if (a == 0)
		return 0;
	// For all other cases
	return a * exp(a, n - 1);
}

// Driver Code
int main()
{
	int x = 7;
	int n = 0;

	// Function call
	cout << (exp(a, n));
}

Output: 1

Time Complexity: O(n)
Auxiliary Space: O(n), n is the size of the recursion stack

3. Program to calculate exponent of a number using Divide and Conquer approach:

What is Divide and Conquer Approach?

Its basic idea is to decompose a given problem into two or more similar, but simpler, subproblems, to solve them in turn, and to compose their solutions to solve the given problem.

The problem can be recursively defined by:

power(x, n) = power(x, n / 2) * power(x, n / 2); // if n is even
power(x, n) = x * power(x, n / 2) * power(x, n / 2); // if n is odd

Steps
Divide and Conquer:

1. For all other cases, the function divides the problem into smaller subproblems using a divide and conquer strategy.

2. If 'n' is even, it calculates 'a' raised to the power of 'n' by computing 'a^(n/2)' and then squaring the result. This is based on the mathematical property that 'a^n' can be expressed as '(a^(n/2))^2' when 'n' is even.

3. f 'n' is odd, it calculates 'a' raised to the power of 'y' by multiplying 'a' with 'a^(n/2)' squared. This accounts for the odd exponent by splitting it into an even exponent and an additional 'a'. This is based on the mathematical property that 'a^n' can be expressed as 'a * (a^(n/2))^2' when 'n' is odd.

Implementation in C++:

#include <bits/stdc++.h>
using namespace std;
class opengenus {

	/* Function to calculate a raised to the power n */
public:
	int power(int a, unsigned int n)
	{
		if (n == 0)
			return 1;
		else if (n % 2 == 0)
			return power(a, n / 2) * power(a, n / 2);
		else
			return a * power(a, n / 2) * power(a, n / 2);
	}
};

/* Driver code */
int main()
{
	opengenus hd;
	int a = 5;
	unsigned int n = 2;

	// Function call
	cout << hd.power(a, n);
	return 0;
}

Output: 25
Time Complexity: O(n)
Auxiliary Space: O(n)

But there is a problem, we've used Divide And Conquer Approach but Time Complexity of the program is till O(n), which is same as in Naive Approach.
Why?
Because, the same subproblem is computed twice for each recursive call.

4. Optimized Divide and Conquer Solution

We can optimize the function by computing the solution of the subproblem once only.

Steps

1. For all other cases, the function uses a recursive approach with a divide and conquer strategy.

It calculates 'x' raised to the power of 'y' as follows:
2. First, it calculates 'mul' by recursively calling the power function with 'a' and 'n / 2'. This effectively reduces the problem size by half with each recursive call.
2.1 If 'n' is even (i.e., 'n % 2 == 0'), it returns 'mul' squared, which is equivalent to 'a^(n/2) * a^(n/2)'.
2.2 If 'y' is odd, it returns 'a * mul' squared. This accounts for the odd exponent by splitting it into 'a' and 'a^(n/2)' squared.

Implementation in C++

int exp(int a, unsigned int n)
{
	int mul;
	if (n == 0)
		return 1;
	mul = exp(a, n / 2);
    //If n is Even
	if (n % 2 == 0)
		return mul * mul;
    //If n is Odd
	else
		return a * mul * mul;
       
}

Time Complexity: O(log n)
Space Complexity: O(log n), for recursive call stack

Whoa!
We have seen a lot of approaches, but which is optimal and which is not?

Solution to this lies in time and space complexities of the code.
The lower the time complexity(preferred over space complexity), the more optimal is the program.

Let's see a last approach, here we solve the same problem having same time complexity as in optimized Divide and Conquer, but constant space. That sounds better :)

5. Program to calculate exponent of a number using Binary operators

To solve the problem, we will folLow the below given idea:

• Every number can be depicted as the sum of powers of 2
  

• We can traverse through all the bits of a number from LSB to MSB in O(log n) time.
  

How O(log n) time?
The idea is to use a binary counter to keep track of which bit we are currently at. We can start with the counter at 0, and then repeatedly shift it left by 1 bit.
This will move the counter to the next bit, and we can continue doing this until we reach the MSB.

The number of times we need to shift the counter is equal to the number of bits in the number. This can be determined by taking the logarithm of the number to the base 2.
Therefore, the total time complexity of traversing through all the bits of a number is O(log n).

Steps

1. Binary Exponentiation:
   The code uses a technique known as "binary exponentiation" to efficiently calculate 'x' raised to the power of 'n.'
   The key idea is to reduce the number of multiplications required to calculate the exponent by taking advantage of the binary representation of 'n.'

2. While Loop and Bitwise Operations:

The code enters a while loop that continues as long as 'n' is greater than 0.
2.1 Inside the loop, it checks whether the least significant bit of 'n' is 1 by using the bitwise AND operator (&). If the least significant bit is 1 (i.e., 'n' is odd), it multiplies the 'ans' by 'a.'

2.2 It then updates 'a' to 'a' squared (i.e., a * a), which corresponds to reducing the exponent by dividing it by 2.

2.3 It also updates 'n' by right-shifting it by 1 (i.e., n = n >> 1), which is equivalent to integer division by 2. This is because, in binary, right-shifting a number by 1 is the same as dividing it by 2.

Implementation in C++

#include bits<stdc++.h>
using namespace std;

int exp(int a, int n)
{
	int ans = 1;
	while (n > 0) {
		if (n & 1 == 1) // b is odd
		{
			ans = ans * a;
		}
		a = a * a;
		n = n >> 1; // b=b/2;
	}
	return ans;
}

// Driver Code
int main()
{
	int a = 7;
	int n = 2;

	// Function call
	cout << (ans(a, n));
	return 0;
}

Output: 49

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

Applications
Exponents are used in programming to perform calculations like:

• Exponential growth
• Power operations
• Handling large numbers

Conclusion

We've seen different approaches to solve this particular problem on finding exponent of a number. Starting from the Brute Force which had time complexity of O(n) to Optimized Divide and Conquer and Binary Operator Approach, we see the time complexity being O(n).
This is how algorithm works and provide efficIency.

Show your love if you find this OpenGenus article useful :)