binary exponentiation 2 Algorithm

Binary exponentiation, also known as exponentiation by squaring, is an efficient algorithm for computing large powers of a number, modulo a given value, or more generally, for evaluating a power function. The algorithm is based on the observation that any positive integer exponent can be represented as a sum of powers of two, which can be computed by iteratively squaring the base and combining the squares with the corresponding powers of two. This approach significantly reduces the number of multiplications required for computing large powers, making it suitable for applications in cryptography, computer algebra systems, and other areas where fast exponentiation is essential. The binary exponentiation algorithm starts by representing the exponent as a binary number and iteratively computes the square of the base for each bit position in the binary representation of the exponent. For each bit position, if the corresponding bit in the exponent is 1, the current square is multiplied with the final result. The algorithm continues this process until all the bit positions are processed. By doing this, the algorithm effectively computes the product of the base raised to the power of each bit position with a 1 in the exponent. The efficiency of the algorithm comes from the fact that it requires only O(log n) multiplications, where n is the exponent, as opposed to the O(n) multiplications required by the naive method of successive multiplication.
"""
* Binary Exponentiation with Multiplication
* This is a method to find a*b in a time complexity of O(log b)
* This is one of the most commonly used methods of finding result of multiplication.
* Also useful in cases where solution to (a*b)%c is required,
* where a,b,c can be numbers over the computers calculation limits.
* Done using iteration, can also be done using recursion

* @author chinmoy159
* @version 1.0 dated 10/08/2017
"""


def b_expo(a, b):
    res = 0
    while b > 0:
        if b & 1:
            res += a

        a += a
        b >>= 1

    return res


def b_expo_mod(a, b, c):
    res = 0
    while b > 0:
        if b & 1:
            res = ((res % c) + (a % c)) % c

        a += a
        b >>= 1

    return res


"""
* Wondering how this method works !
* It's pretty simple.
* Let's say you need to calculate a ^ b
* RULE 1 : a * b = (a+a) * (b/2) ---- example : 4 * 4 = (4+4) * (4/2) = 8 * 2
* RULE 2 : IF b is ODD, then ---- a * b = a + (a * (b - 1)) :: where (b - 1) is even.
* Once b is even, repeat the process to get a * b
* Repeat the process till b = 1 OR b = 0, because a*1 = a AND a*0 = 0
*
* As far as the modulo is concerned,
* the fact : (a+b) % c = ((a%c) + (b%c)) % c
* Now apply RULE 1 OR 2, whichever is required.
"""

LANGUAGE:

DARK MODE: