Write a pseudo-code of the program (in binary representation).

Implement the program in Python code.

The improved algorithm is based on a more clever way to break up the product into partial sums. Let's assume we're in base-2 (it doesn't really matter), and start by writing x as x12n/2+x0. In other words, x1 corresponds to the "highorder" n/2 bits, and x0 corresponds to the "low-order" n/2 bits. Similarly, we write y=y12n/2+y0. Thus, we have xy=(x12n/2+x0)(y12n/2+y0)=x1y12n+(x1y0+x0y1)2n/2+x0y0