Question

Use the divide-and-conquer integer multiplication algorithm to multiply the two binary integers 10011011 and 10111010.

Answer 1

Write

x=10011011 = 1001·24+ 1011≡xL·24+xRy=10111010 = 1011·24+ 1010≡

yL·24+yR

Then

xL+xR=1001 + 1011 = 10100yL+yR=1011 + 1010 = 10101(xL+xR)(yL+yR)=10100×10101 = 110100100xLyL=1001×1011 = 1100011xRyR=1011×1010 = 1101110xLyR+xRyL=(xL+xR)(yL+yR)-xLyL-xRyR=110100100-1100011-1101110 = 11010011

Therefore

xy=28xLyL+ 24(xLyR+xRyL) +xRyR=28·1100011 + 24·11010011 + 1101110=111000010011110