Skip to main content

Binary Exponentiation Algorithm – Explained with Practical Examples

Sahil MahapatraOctober 15, 2024About 6 minPythonArticle(s)blogfreecodecamp.orgpypythonalgorithms

Binary Exponentiation Algorithm – Explained with Practical Examples 관련

Python > Article(s)

Article(s)

Binary Exponentiation Algorithm – Explained with Practical Examples
Binary exponentiation, also known as exponentiation by squaring, is a powerful algorithm used to efficiently calculate large powers of numbers. This technique is particularly useful in various fields of computer science, including cryptography, compe...

Binary exponentiation, also known as exponentiation by squaring, is a powerful algorithm used to efficiently calculate large powers of numbers. This technique is particularly useful in various fields of computer science, including cryptography, competitive programming, and computer graphics.

In this article, we'll explore the concept of binary exponentiation, understand how it works, and implement it in code.


What is Binary Exponentiation?

Binary exponentiation is a method to compute an (a raised to the power of n) using only multiplications, instead of the naïve O(n) multiplications.

This significant improvement in efficiency makes it possible to calculate extremely large powers quickly, even when dealing with modular arithmetic.


How Binary Exponentiation Works

The key idea behind binary exponentiation is to break down the exponent into its binary representation and use the properties of exponents to simplify the calculation.

Let's break it down step by step:

  1. Convert the exponent n to its binary representation.
  2. Initialize the result as 1 and the base as a.
  3. Iterate through each bit of the binary representation of n from right to left:
    • (a). If the current bit is 1, multiply the result by the current base.
    • (b). Square the base (multiply it by itself).
  4. Return the final result.

For example, let's calculate 3133^{13}:

  1. Convert 1313 to binary: 1310=1101213_{10}=1101_{2}
  2. Initialize result =1= 1, base =3= 3
  3. Iterate through the bits:
    • Bit 11: result =1×3=3=1\times3=3, base =3×3=9=3\times3=9
    • Bit 00: result =3=3, base =9×9=81=9\times9=81
    • Bit 11: result =3×81=243=3\times81=243, base =81×81=6561=81\times81=6561
    • Bit 11: result =243×6561=1,594,323=243\times6561=1,594,323

Thus, 313=1,594,323313=1,594,323.


Why Binary Exponentiation is Efficient

The efficiency of binary exponentiation comes from two main factors:

  1. Reduced number of multiplications: Instead of performing n-1 multiplications as in the naïve approach, we only perform O(logn) multiplications. This is because we're essentially breaking down the problem into smaller subproblems based on the binary representation of the exponent.
  2. Reuse of previous calculations: By squaring the base at each step, we're reusing the results of previous calculations, which significantly reduces the overall number of operations needed.

To illustrate this efficiency, consider calculating a1000000. The naïve approach would require 999,999 multiplications, while binary exponentiation would only require about 20 multiplications (as log2⁡(1000000)≈20).


Algorithm Implementation

Let's implement the binary exponentiation algorithm in Python:

def binary_exponentiation(base, exponent):
    result = 1
    while exponent > 0:
        # If the current bit is 1, multiply the result by the current base
        if exponent & 1:
            result *= base
        # Square the base
        base *= base
        # Move to the next bit
        exponent >>= 1
    return result

# Example usage
print(binary_exponentiation(3, 13))  # Output: 1594323

Let's break down the algorithm:

  1. We initialize result to 11, which is the identity for multiplication.
  2. We use a while loop to iterate until the exponent becomes 00.
  3. We check if the least significant bit of the exponent is 11 using the bitwise AND operator &. If it is, we multiply the result by the current base.
  4. We square the base by multiplying it by itself.
  5. We use the right shift operator >>= to move to the next bit of the exponent.
  6. Finally, we return the result.

Time Complexity Analysis

The time complexity of binary exponentiation is O(logn)O\left(\log{}{n}\right), where n is the exponent. This is because:

  1. The number of bits in the binary representation of n is log2n+1\lfloor\log_{2}{⁡n}\rfloor+1.
  2. We perform at most two multiplications per bit (one for squaring the base, and potentially one for updating the result).

Therefore, the total number of multiplications is at most 2(log2n+1)2(\lfloor\log_{2}{⁡n}\rfloor+1), which simplifies to O(logn)O\left(\log⁡{n}\right).


Example Problems and Solutions

Let's look at some algorithmic problems that you can solve efficiently using binary exponentiation, along with detailed explanations of the solutions and how we arrived at using binary exponentiation.

Problem 1: Modular Exponentiation

Problem

Calculate 31000000mod10000000073^{1000000}\text{mod}1000000007.

This problem would be impossible to solve with naïve exponentiation due to the huge result, but modular binary exponentiation makes it tractable by keeping all intermediate results manageable.

Problem 2: Matrix Exponentiation

Problem

Given a 2x2 matrix A, calculate An where n=1000000n = 1000000.

This matrix exponentiation technique is particularly powerful for solving linear recurrence relations in logarithmic time, as demonstrated here with the Fibonacci sequence.


Practice Problems

Here are some problems for you to solve using binary exponentiation:

1. Modular Exponentiation

Calculate 71234567mod100000000971234567\:\text{mod}\:1000000009.

Hint

Use the mod_binary_exponentiation function from Problem 1 in the examples.

2. Last Digit

Find the last digit of .

Hint

Observe the pattern of last digits of powers of 2 and use binary exponentiation with modulo 10.

3. Power Tower

Calculate the last 33 digits of 22202^{2^{20}}.

Hint

Use the property of modular arithmetic that abmodm=abmodϕ(m)modma^{b}\:\text{mod}\:m=a^{b\:\text{mod}\:\phi(m)}\:\text{mod}\:m where ϕ\phi is Euler's totient function. You'll need to calculate 220modϕ(1000)2^{20}\:\text{mod}\:\phi(1000) first.

4. Matrix Chains

Given a 2x2 matrix A=[1234]A=\begin{bmatrix}1 & 2 \\ 3 & 4\end{bmatrix}, calculate the last two digits of the sum of all elements in A1000000A^{1000000}.

Hint

Use matrix exponentiation as in Problem 2 from the examples, but only keep track of the last two digits of each element. You'll need to sum the elements after the final exponentiation.

5. Fibonacci Sequence

Find the 1000000th Fibonacci number modulo 1000000007.

Hint

Use the matrix form of the Fibonacci sequence [1110]\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix} and apply matrix exponentiation as shown in Problem 2 of the examples.


Conclusion

Binary exponentiation is a powerful technique that can be applied to a wide range of problems involving large exponents. As we've seen in the example and practice problems, it's particularly useful in modular arithmetic, matrix operations, and solving recurrence relations.

By practicing these problems, you'll gain a deeper understanding of how to apply binary exponentiation in various scenarios. Remember, the key is to recognize when a problem involves raising something to a large power, whether it's a number, a matrix, or even a more complex structure.

If you found this explanation of Binary Exponentiation algorithm helpful, you might also enjoy more in-depth programming tutorials and concepts I cover on my blog.

Binary Exponentiation Algorithm – Explained with Practical Examples

Binary exponentiation, also known as exponentiation by squaring, is a powerful algorithm used to efficiently calculate large powers of numbers. This technique is particularly useful in various fields of computer science, including cryptography, compe...