Spent a lot of time to understand this logic in Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def karatsuba_multiplication(x : int, y : int) -> int:
    sx, sy = map(lambda x: '0' + str(x) if len(str(x)) % 2 != 0 else str(x), (x, y))
    return _karatsuba_multiplication(sx, sy, max(len(sx), len(sy)))

def _prepend_nils(string : str, amount_of_nils : int) -> str:
    return ('0' * amount_of_nils + string)

def _karatsuba_multiplication(x : str, y : str, n : int) -> int:
    x, y = map(lambda x: _prepend_nils(x, (n - len(x))), (x, y))

    if (n == 1):
        return (int(x) * int(y))

    mid = n // 2
    a, b = int(x[:mid]), int(x[mid:])
    c, d = int(y[:mid]), int(y[mid:])

    p = a + b
    q = c + d
    ac = _karatsuba_multiplication(str(a), str(c), max(len(str(a)), len(str(c))))
    bd = _karatsuba_multiplication(str(b), str(d), max(len(str(b)), len(str(d))))
    pq = _karatsuba_multiplication(str(p), str(q), max(len(str(p)), len(str(q))))
    adbc = pq - ac - bd
    return 10**n * ac + 10**(mid + n % 2) * adbc + bd