Karatsuba 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(55561165165163231656, 4649494651616619847)
    258331340273014094289730553689748276632

    """
    # only use this method for very large values of x or y
    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

        x_low = x & mask
        y_low = y & mask
        x_high = x >> half
        y_high = y >> half

        high = karatsuba_fast_multiply(x_high, y_high)
        high_times_low = karatsuba_fast_multiply(x_low + x_high, y_low + y_high)
        low = karatsuba_fast_multiply(x_low, y_low)
        reduced = high_times_low - high - low
        return (((high << half) + reduced) << half) + c