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 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 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 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 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
def binary_exp_recursive(base: float, exponent: int) -> float:
    
    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:
    
    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:
    
    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:
    
    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,
        )
    )