Binary Exponentiation

Binary exponentiation (commonly referred as squaring exponentiation) is a technique that allows you to calculate aⁿ using just O(log n) multiplications (rather than the O(n) multiplications required by the sensible approach).

It could also be used through any operations that have the attribute of associativity, making it useful in a wide range of activities not connected to arithmetic: (X⋅Y)⋅Z=X⋅(Y⋅Z)

This clearly applies to modular multiplication, matrices multiplication, and other problems that we will examine further down.

Algorithm

Rising a to the power of n is naively represented as multiplying by a n1 times: aⁿ=aa…a. However, for large a or n, this method is impractical.

aᵇ⁺ᶜ = aᵇ⋅aᶜ and aᵇ = aᵇ⋅aᵇ = (aᵇ)²

The objective behind binary exponentiation is to divide the work using the exponent’s binary representation.

For reference, let’s write n in base 2:

If we know the powers a¹,a²,a⁴,a⁸,…,a⌊ˡᵒᵍ ⁿ⌋, we simply need to execute O(log n) multiplications because the integer n has exactly ⌊log₂ n⌋+1 digits in base 2.

So all we need is a quick mechanism to compute them. Fortunately, because each element in the series is simply the square of the previous element, this is a simple task.

So we only need to multiply three of them to reach the final result for 3¹³ (skipping 3² because the matching bit in n is not set): 3¹³=6561⋅81⋅3=1594323

The total complexity of this procedure is O(log n): we must compute log n powers of a and then multiply them by at least log n to get the final answer.

The concept is represented in the following recursive approach:

Implementation

Firstly, there’s the recursive approach, which is a correct equivalent of the recursive formula:

The second method achieves the same result without using recursion. In a loop, it calculates all the powers and multiplies the ones by the matching set bit in n. Despite the fact that both procedures are equally sophisticated, this one will be faster in practice since it avoids the overhead of recursive calls.

Applications

Effective computation of large exponents modulo a number

Problem: Compute xⁿ mod m. This is a rather typical procedure. It’s used to compute the modular multiplicative inverse, for example.

Solution: Because the module operator does not conflict with multiplications a ⋅ b = (a mod m)⋅(b mod m)(mod m), we can use the same code and simply replace every multiplication with a modular multiplication:

Note: If m is a prime number, we can speed up this procedure by using
xⁿ ᵐᵒᵈ⁽ᵐ⁻¹⁾ instead of xⁿ in the calculation. This is a direct result of Fermat’s little theorem.

Effective computation of Fibonacci numbers

Problem: Compute n-th Fibonacci number Fₙ.

Solution: See the Fibonacci Number article for additional information. We’ll merely go through the basics of the algorithm. Only the two previous Fibonacci numbers are required to calculate the next one, since Fₙ=Fₙ₋₁+Fₙ₋₂. This transformation can be described by a 2 × 2 matrix: the transition from Fᵢ and Fᵢ₊₁ to Fᵢ₊₁and Fᵢ₊₂. If this transformation were applied to the pair F₀ and F₁, it would result in F₁ and F₂. As a result, we can multiply this transformation matrix by n to find Fₙ in time complexity O. (log n).

Applying a permutation kk times

Problem: You are given a sequence of length nn. Apply to it a given permutation kk times.

Solution: Simply use binary exponentiation to increase the permutation to the k-th power, then apply it to the sequence. This gives you an O time complexity (n log k).

Note: By generating the permutation graph and considering each cycle separately, this task may be completed in linear time. After that, you may compute kk modulo the cycle’s size and obtain the end position for each integer in the cycle.