karatsuba

karatsuba.py

def karatsuba(x: int, y: int) -> int:
    # get Length of variable
    x_str, y_str = str(x), str(y)
    x_len, y_len = len(x_str), len(y_str)

    # Initialize
    if x_len == 1 or y_len == 1:
        return x * y

    # Divide
    m = min(x_len, y_len) // 2
    a, b = int(x_str[:-m]), int(x_str[-m:])
    c, d = int(y_str[:-m]), int(y_str[-m:])

    # Conquer
    ac = karatsuba(a, c)
    bd = karatsuba(b, d)
    ad_bc = karatsuba(a + b, c + d) - ac - bd

    # Combine
    return 10 ** (2 * m) * ac + 10 ** m * ad_bc + bd