def multiply(x, y, n):
    """multiply two integers x and y, where n >= 0
       is a power of 2, and as large as 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

    
    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
    # note that these two operations could be done by bit shifts and masking.
    
    p1 = multiply (xL,    yL,    n_over_two)
    p2 = multiply (xL+xR, yL+yR, n_over_two)
    p3 = multiply (xR,    yR,    n_over_two) 
    
    
    return (p1 << n) + ((p2 - p3 - p1) << n_over_two) + p3
    

print (multiply(1000, 1000, 16))