# Compute the value of A raise to the power B using Fast Exponentiation

Here, we are going to compute the value of A raise to the power B using Fast Exponentiation.
Submitted by Ankit Sood, on December 05, 2018

Now here we are going to learn that how to compute the value of a^b i.e. "A" raise to the power "B" using an optimized algorithm called as "fast-exponentiation"?

we could have used a brute force approach to do the required task but then it would have taken O(b) i.e a brute force approach can solve the required task in linear time whereas the same task could be done in O(log b) using FAST–EXPONENTIATION.

Fast exponentiation uses a simple recursive approach whose recurrence relation can be written as :

F(a,b) = F(a,b/2)*F(a,b/2)

From the above recurrence relation, it can be easily seen that the time complexity would be O(log b).

## C++ program to find the value of A^B using fast exponentiation

```#include <iostream>
using namespace std;

//function to find a^b
int fcheck(int a,int b){
if(b == 0)
return 1;
if(b == 1)
return a;
return fcheck(a,b/2)*fcheck(a,b/2);
}

//main code
int main(){
int a,b;

cout<<"Enter the first number (value of a): ";
cin>>a;
cout<<"Enter the second number (Value of b): ";
cin>>b;

int x=fcheck(a,b);
if(b%2==0 || b==1)
cout<<a<<" raise to the power "<<b<<" is = " <<x<<endl;
else
cout<<a<<" raise to the power "<<b<<" is = " <<a*x<<endl;

return 0;
}
```

Output

```First run:
Enter the first number (value of a): 5
Enter the second number (Value of b): 3
5 raise to the power 3 is = 125

Second run:
Enter the first number (value of a): 5
Enter the second number (Value of b): 0
5 raise to the power 0 is = 1

Third run:
Enter the first number (value of a): 5
Enter the second number (Value of b): 1
5 raise to the power 1 is = 5
```

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates