Karatsuba Multiplication with Bitwise operators for memory efficiency

karatsuba.py

def karatsuba(x, y):
    if x < 16 or y < 16:
        return x * y

    max_len = max(x.bit_length(), y.bit_length()) // 2
    bitwise_filter = (1 << max_len) - 1

    a, b = x >> max_len, x & bitwise_filter
    c, d = y >> max_len, y & bitwise_filter

    ac = karatsuba(a, c)
    bd = karatsuba(b, d)
    abcd = karatsuba(a+b, c+d) - ac - bd

    return (((ac << max_len) + abcd) << max_len) + bd