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 |