# Implementing basic Mathematical operations (Exponential)

You’re given two integers a and n. You’ve to compute an.

###### Using inbuilt-function pow
#include <iostream>
#include <math.h>
using namespace std;

int main () {
cout<<"7 ^ 3 = "<<pow (7, 3)<<endl;
return 0;
}


Output

7 ^ 3 = 343

Drawback of this method is that it will cause int overflow, if we need to compute: An mod p, where A can be as large as 1018 and p is a prime = 109 + 7. This is because pow( ) method will calculate the exponential before taking the modulo.

###### Iterative Approach
//
//  main.cpp
//  Power function
//
//  Created by Himanshu on 19/09/21.
//

#include <iostream>
#include <math.h>
using namespace std;
long long mod = 1000000007;

int main () {
long long temp, A = 1000000000, result = 1;
int n = 10;

for (int i=1; i<=n; i++) {
result = (result*A)%mod;
}

cout<<"Result using iterative approach "<<result<<endl;

temp = pow(A, n);
result = temp%mod;

cout<<"Result using pow() "<<result<<endl;

return 0;
}



Output

Result using iterative approach 282475249
Result using pow() -291172004

Time complexity: O(n)

Problem with this method is that it will give TLE (Time Limit Exceeded) in competitive programming when along with A, n is also as large as 1012. In other words, it will not be computed in polynomial time.

###### Logarithmic approach

Consider this statement:

An  = { (A(n/2))2, when n is even,
(A((n-1)/2))2*A, when n is odd }  

Pseudocode (Bottom-up approach)

Power(A, n)
1. result = 1
2. while n > 0:
3.   if (n is odd):
4.     result = result*A;
5.   A = A*A
6.   n = n/2
7. return result

Code Implementation

//
//  main.cpp
//  Modular Exponentiation
//
//  Created by Himanshu on 19/09/21.
//

#include <iostream>
#include <math.h>
using namespace std;
typedef long long ll;
ll mod = 1000000007;

ll power (ll a, ll n) {
ll result = 1;

while (n > 0) {
if (n%2 == 1) {
result = (result*a)%mod;
}

a = (a*a)%mod;
n = n/2;
}

return result;
}

int main () {
ll a = 1000000000;
ll n = 100000000000;

ll result = power(a, n);

cout<<"Result using Modular Exponentiation "<<result<<endl;

return 0;
}



Output

Result using Modular Exponentiation 296055122

Time complexity: O(logn)