TMC Series #1: Handing large exponents in code

The Problem

Published in

The Bit Theories

3 min readApr 26, 2017

Whenever we want to compute x^n (x raised to n) in a standard (x*x*x…x n-times) iterative/recursive manner, one of the two problems may occur when n is reasonably large:
1. Timeout: Due to large number of multiplications.

2. Garbage Output: Due to exceeding the range of native datatypes (int, long etc.) of the programming language.

For example: Computing 2¹⁰¹⁸ via the following code would fail:

int recursiveExponent(int x, int n){ 
    if(n==0)
        return 1;
    return x*recursiveExponent(x,n-1);
}

Note that above basic approach (or equivalent iterative one) has:
Time Complexity: O(n)

Space Complexity: O(n) (due to function stack of n recursive calls, O(1) for iterative)

The Solution

Solving Timeout Issue (1.):

We can solve it by reducing time complexity via binary exponentiation, this will reduce Time Complexity from O(n) to O(logn).

While calculating x^n, this approach relies on whether n is even or odd:

If n is even: x^n can be written as: (x²)^n/2 ( 3⁸ equals (3²)⁴)

If n is odd: x^n can be written as: x*(x^n-1) ( 2⁹ equals (2*2⁸))

and then n-1 becomes even.

So, now the computation steps (x*x*x…x n-times) is reduced to n/2.

Eg: 2¹⁰ => (2²)⁵ => 4⁵ => 4*(4⁴) => .. and so on.

//method1 to calculate x^n
int recursiveBinaryExponentiation(int x, int n){
    if(n == 0)
        return 1;
    else if(n%2 == 0)
        return recursiveBinaryExponentiation(x*x,n/2);
    else
        return x*recursiveBinaryExponentiation(x*x,(n-1)/2);
} //Time Complexity: O(logn) Space Complexity: O(logn)//method2 to calculate x^n
int iterativeBinaryExponentiation(int x, int n){
    int result = 1;
    while(n > 0){
        if(n%2 == 1)
            result = result *x;
        x = x*x;
        n=n/2;
    }
    return result;
}//Time Complexity: O(logn) Space Complexity: O(1)

Solving inherent data-type limit issue (2.):

Often large-exponents are needed, especially in cryptography. Data-type size limit issues can be solved via modular exponentiation.

In addition to (1.), We can solve (2.) by modifying the above binary exponentiation approach to modular + binary exponentiation.

int recursiveModularExponentiation(int x, int n, int M){
    if(n == 0)
    return 1;
    else if(n%2 == 0)
    return recursiveModularExponentiation((x*x)%M,n/2,M);
    else
    return (x*recursiveModularExponentiation((x*x)%M,(n-1)/2,M))%M;
} //Time Complexity: O(logn) Space Complexity: O(logn)int iterativeModularExponentiation(int x, int n, int M){
    int result  = 1;
    while(n>0){
        if(n%2==1)
            result = (result *x)%M;
        x = (x*x)%M;
        n = n/2;
    }
    return result;
} //Time Complexity: O(logn) Space Complexity: O(1)