Katasuba fast multiplication

fibonacci.py

def karatsuba_fast_multiply(multiplier: int, multiplicand: int) -> int:
    """
    Karatsuba fast multiplication, published in 1962
    https://en.wikipedia.org/wiki/Karatsuba_algorithm

    Args:
        x ():
        y ():

    Returns: int

    >>> karatsuba_fast_multiply(2, 4)
    8
    >>> karatsuba_fast_multiply(135, 139)
    18765

    """
    if multiplier.bit_length() <= 1536 or multiplicand.bit_length() <= 1536:
        return multiplier * multiplicand

    else:
        n = max(multiplier.bit_length(), multiplicand.bit_length())
        half = (n + 32) // 64 * 32
        mask = (1 << half) - 1
        xlow = multiplier & mask
        ylow = multiplicand & mask
        xhigh = multiplier >> half
        yhigh = multiplicand >> half

        a = karatsuba_fast_multiply(xhigh, yhigh)
        b = karatsuba_fast_multiply(xlow + xhigh, ylow + yhigh)
        c = karatsuba_fast_multiply(xlow, ylow)
        d = b - a - c
        return (((a << half) + d) << half) + c