def multiply(x, y, n):
    """multiply two integers x and y, where n >= 0 is a power of 2,
       and is >= the maximum number of bits in x or y"""
       
    if n == 1:
        return x * y
    
    n_over_two = n//2 
        
    two_to_the_n_over_two = 1 << n_over_two # a right bit-shift

    # note: these 2 operations can be done by bit shifts and masking.
    xL, xR = x // two_to_the_n_over_two, x % two_to_the_n_over_two
    yL, yR = y // two_to_the_n_over_two, y % two_to_the_n_over_two
    
    p1 = multiply (xL, yL, n_over_two)
    p2 = multiply (xL, yR, n_over_two)
    p3 = multiply (xR, yL, n_over_two) 
    p4 = multiply (xR, yR, n_over_two)
    
    return (p1 << n) + ((p2 + p3) << n_over_two) + p4

print multiply((3000, 40000, 16))