Implementing basic Mathematical operations (Exponential)

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

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: A^n mod p, where A can be as large as 10^18 and p is a prime = 10^9 + 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 10^12. In other words, it will not be computed in polynomial time.

Logarithmic approach

Consider this statement:

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

Pseudocode

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)

Leave a Reply

Your email address will not be published.