Binary Exponentiation This is a method to find ab in Olog b time complexity and is one of the most commonly used methods of exponentiation. The method is also useful for modular exponentiation, when the solution to ab  c is required. To calculate ab:  If b is even, then ab  a  ab  2  If b is odd, then ab  a  ab  1 Repeat until b  1 or b  0 For modular exponentiation, we use the fact that a  b  c  a  c  b  c  c Computes ab recursively, where a is the base and b is the exponent  binaryexprecursive3, 5 243  binaryexprecursive11, 13 34522712143931  binaryexprecursive1, 3 1  binaryexprecursive0, 5 0  binaryexprecursive3, 1 3  binaryexprecursive3, 0 1  binaryexprecursive1.5, 4 5.0625  binaryexprecursive3, 1 Traceback most recent call last: ... ValueError: Exponent must be a nonnegative integer Computes ab iteratively, where a is the base and b is the exponent  binaryexpiterative3, 5 243  binaryexpiterative11, 13 34522712143931  binaryexpiterative1, 3 1  binaryexpiterative0, 5 0  binaryexpiterative3, 1 3  binaryexpiterative3, 0 1  binaryexpiterative1.5, 4 5.0625  binaryexpiterative3, 1 Traceback most recent call last: ... ValueError: Exponent must be a nonnegative integer Computes ab  c recursively, where a is the base, b is the exponent, and c is the modulus  binaryexpmodrecursive3, 4, 5 1  binaryexpmodrecursive11, 13, 7 4  binaryexpmodrecursive1.5, 4, 3 2.0625  binaryexpmodrecursive7, 1, 10 Traceback most recent call last: ... ValueError: Exponent must be a nonnegative integer  binaryexpmodrecursive7, 13, 0 Traceback most recent call last: ... ValueError: Modulus must be a positive integer Computes ab  c iteratively, where a is the base, b is the exponent, and c is the modulus  binaryexpmoditerative3, 4, 5 1  binaryexpmoditerative11, 13, 7 4  binaryexpmoditerative1.5, 4, 3 2.0625  binaryexpmoditerative7, 1, 10 Traceback most recent call last: ... ValueError: Exponent must be a nonnegative integer  binaryexpmoditerative7, 13, 0 Traceback most recent call last: ... ValueError: Modulus must be a positive integer
def binary_exp_recursive(base: float, exponent: int) -> float:
    """
    Computes a^b recursively, where a is the base and b is the exponent

    >>> binary_exp_recursive(3, 5)
    243
    >>> binary_exp_recursive(11, 13)
    34522712143931
    >>> binary_exp_recursive(-1, 3)
    -1
    >>> binary_exp_recursive(0, 5)
    0
    >>> binary_exp_recursive(3, 1)
    3
    >>> binary_exp_recursive(3, 0)
    1
    >>> binary_exp_recursive(1.5, 4)
    5.0625
    >>> binary_exp_recursive(3, -1)
    Traceback (most recent call last):
        ...
    ValueError: Exponent must be a non-negative integer
    """
    if exponent < 0:
        raise ValueError("Exponent must be a non-negative integer")

    if exponent == 0:
        return 1

    if exponent % 2 == 1:
        return binary_exp_recursive(base, exponent - 1) * base

    b = binary_exp_recursive(base, exponent // 2)
    return b * b


def binary_exp_iterative(base: float, exponent: int) -> float:
    """
    Computes a^b iteratively, where a is the base and b is the exponent

    >>> binary_exp_iterative(3, 5)
    243
    >>> binary_exp_iterative(11, 13)
    34522712143931
    >>> binary_exp_iterative(-1, 3)
    -1
    >>> binary_exp_iterative(0, 5)
    0
    >>> binary_exp_iterative(3, 1)
    3
    >>> binary_exp_iterative(3, 0)
    1
    >>> binary_exp_iterative(1.5, 4)
    5.0625
    >>> binary_exp_iterative(3, -1)
    Traceback (most recent call last):
        ...
    ValueError: Exponent must be a non-negative integer
    """
    if exponent < 0:
        raise ValueError("Exponent must be a non-negative integer")

    res: int | float = 1
    while exponent > 0:
        if exponent & 1:
            res *= base

        base *= base
        exponent >>= 1

    return res


def binary_exp_mod_recursive(base: float, exponent: int, modulus: int) -> float:
    """
    Computes a^b % c recursively, where a is the base, b is the exponent, and c is the
    modulus

    >>> binary_exp_mod_recursive(3, 4, 5)
    1
    >>> binary_exp_mod_recursive(11, 13, 7)
    4
    >>> binary_exp_mod_recursive(1.5, 4, 3)
    2.0625
    >>> binary_exp_mod_recursive(7, -1, 10)
    Traceback (most recent call last):
        ...
    ValueError: Exponent must be a non-negative integer
    >>> binary_exp_mod_recursive(7, 13, 0)
    Traceback (most recent call last):
        ...
    ValueError: Modulus must be a positive integer
    """
    if exponent < 0:
        raise ValueError("Exponent must be a non-negative integer")
    if modulus <= 0:
        raise ValueError("Modulus must be a positive integer")

    if exponent == 0:
        return 1

    if exponent % 2 == 1:
        return (binary_exp_mod_recursive(base, exponent - 1, modulus) * base) % modulus

    r = binary_exp_mod_recursive(base, exponent // 2, modulus)
    return (r * r) % modulus


def binary_exp_mod_iterative(base: float, exponent: int, modulus: int) -> float:
    """
    Computes a^b % c iteratively, where a is the base, b is the exponent, and c is the
    modulus

    >>> binary_exp_mod_iterative(3, 4, 5)
    1
    >>> binary_exp_mod_iterative(11, 13, 7)
    4
    >>> binary_exp_mod_iterative(1.5, 4, 3)
    2.0625
    >>> binary_exp_mod_iterative(7, -1, 10)
    Traceback (most recent call last):
        ...
    ValueError: Exponent must be a non-negative integer
    >>> binary_exp_mod_iterative(7, 13, 0)
    Traceback (most recent call last):
        ...
    ValueError: Modulus must be a positive integer
    """
    if exponent < 0:
        raise ValueError("Exponent must be a non-negative integer")
    if modulus <= 0:
        raise ValueError("Modulus must be a positive integer")

    res: int | float = 1
    while exponent > 0:
        if exponent & 1:
            res = ((res % modulus) * (base % modulus)) % modulus

        base *= base
        exponent >>= 1

    return res


if __name__ == "__main__":
    from timeit import timeit

    a = 1269380576
    b = 374
    c = 34

    runs = 100_000
    print(
        timeit(
            f"binary_exp_recursive({a}, {b})",
            setup="from __main__ import binary_exp_recursive",
            number=runs,
        )
    )
    print(
        timeit(
            f"binary_exp_iterative({a}, {b})",
            setup="from __main__ import binary_exp_iterative",
            number=runs,
        )
    )
    print(
        timeit(
            f"binary_exp_mod_recursive({a}, {b}, {c})",
            setup="from __main__ import binary_exp_mod_recursive",
            number=runs,
        )
    )
    print(
        timeit(
            f"binary_exp_mod_iterative({a}, {b}, {c})",
            setup="from __main__ import binary_exp_mod_iterative",
            number=runs,
        )
    )
