Binary Exponentiation

Binary exponentiation computes aⁿ by repeatedly squaring and selecting powers corresponding to the binary digits of n. It uses only logarithmically many multiplications, unlike multiplying a by itself n times. The operation need only be associative, which later allows matrix exponentiation. Here we give iterative and recursive modular versions in one complete program, with explicit bounds that make every product safe.

Prerequisites: Modular Arithmetic; bit operations; recursion.

Build the idea

1. 1. Split the exponent into powers of two

   For n=13, binary 1101 means 13=8+4+1, so a¹³=a⁸·a⁴·a. Starting from a, repeatedly square to obtain powers a²,a⁴,a⁸. Include a power when the corresponding exponent bit is one. No floating-point pow is needed for exact modular integer results.

   $$a^{13}=a^8·a^4·a$$

2. 2. Maintain the iterative invariant

   result starts at 1 modulo m and base at normalized a. The product result·base^remaining stays congruent to the original aⁿ. If remaining is odd, move one base into result; then square base and halve remaining. This preserves the invariant and decreases the exponent. When it reaches zero, result is the answer.

3. 3. Derive the recursive version

   Let half=power(a,floor(n/2)). For even n, return half²; for odd n, return half²·a, reducing each multiplication modulo m. Crucially compute half once: making two identical recursive half calls would repeat work and lose logarithmic runtime. The exponent-zero base case returns 1%m, including zero when m=1.

4. 4. Trace 3¹³ modulo 17

   Selected powers are 3¹≡3, 3²≡9, 3⁴≡13 and 3⁸≡16. Multiply the selected 8,4,1 powers: 16·13·3≡12. The iterative loop reads four bits; the recursive version reaches the same answer by halving 13→6→3→1→0. Both outputs should agree, making one a useful cross-check.

5. 5. Separate exponent growth from numeric growth

   Reducing modulo m keeps each factor below m, but products still need a safe type. This program uses m≤10^9 so long long suffices. Without a modulus, aⁿ can overflow after very few steps even though the algorithm is fast. We use the conventional exponent-zero result 1, including for base zero; negative exponents would need inverses and are not accepted.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 2. Maintain the iterative invariant result starts at 1 modulo m and base at normalized a.
#include<iostream>
using ll=long long;
ll power(ll a,unsigned long long exponent,ll mod){
    a=(a%mod+mod)%mod;
    ll result=1%mod;
    while(exponent>0){
        if(exponent&1ULL){
            result=result*a%mod;
        }
        a=a*a%mod;
        exponent>>=1;
    }
    return result;
}
ll recursivePower(ll a,unsigned long long exponent,ll mod){
    if(exponent==0){
        return 1%mod;
    }
    ll half=recursivePower(a,exponent/2,mod);
    ll result=half*half%mod;
    return exponent%2?result*a%mod:result;
}
int main(){
    ll a,m;
    unsigned long long n;
    std::cin>>a>>n>>m;
    ll normalized=(a%m+m)%m;
    std::cout<<power(a,n,m)<<' '<<recursivePower(normalized,n,m)<<'\n';
}

Complexity analysis

O(log(n+1)) modular multiplications for each method. Iterative version O(1) auxiliary space; recursive version O(log(n+1)) stack. Running both preserves logarithmic time but the complete program has logarithmic auxiliary stack. Input n≤10^18, 1≤m≤10^9 and |a|≤10^18.

Example input and output

Read a n m under the stated bounds and print the iterative and recursive values of aⁿ mod m.

Input

3 13 17

Output

12 12

13=8+4+1; modular powers 16,13,3 multiply to residue 12.

Practical applications

Use for powers modulo m, modular inverses under valid theorems, repeated transformations and transition matrices. The same pattern works for any associative multiplication with an identity; changing the operation changes the multiplication cost in the total complexity.

Check your understanding

What keeps the recursive version logarithmic?

Put it into practice

Test exponent zero, base zero, negative bases and modulus one.