import time

# This one will (probably) only work if a and b have the same number of digits, 
# admittedly I didn't really think about it...
def mult(a: str, b: str) -> int:
    # First, let's figure out if the result should be negative.
    # It should be negative if exactly one of the operands is negative.
    negative = False
    if a[0] == "-":
        a = a[1:]
        negative = True

    if b[0] == "-":
        b = b[1:]
        negative = not negative

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

    # 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) :]

    big = mult(aLeft, bLeft)
    small = mult(aRight, bRight)
    mid = mult(str(int(aLeft) - int(aRight)), str(int(bLeft) - int(bRight)))

    return (
        big * 10 ** (len(aRight) + len(bRight))
        + (big + small - mid) * 10 ** (len(bRight))
        + small
    ) * (-1 if negative else 1)


# 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)