import time
def mult(a: str, b: str) -> int:

    # Base case
    if len(a) == 1 or len(b) == 1:
        return int(a) * int(b)

    # Left and right halves of the number a as a string
    aLeft = a[: int(len(a) / 2)]
    aRight = a[int(len(a) / 2) :]

    # Left and right halves of the number b as a string
    bLeft = b[: int(len(b) / 2)]
    bRight = b[int(len(b) / 2) :]

    return (
        mult(aLeft, bLeft) * 10 ** (len(aRight) + len(bRight))
        + mult(aLeft, bRight) * 10 ** len(aRight)
        + mult(aRight, bLeft) * 10 ** len(bRight)
        + mult(aRight, bRight)
    )

# Test to confirm our algorithm at least appears to work
a = "123456789"
b = "987654321"
print(int(a) * int(b))
print(mult(a, b))

# Let's see how long it takes on average to use our mult algorithm!
for i in range(1000, 20000, 1000):
    avg = 0
    a = "9" * int(i / 100)
    trials = 100
    for _ in range(trials):
        t1 = time.time()
        mult(a, a)
        t2 = time.time()
        avg += t2 - t1
    print(avg / trials)