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)
One thought on “Implementing basic Mathematical operations (Exponential)”