Question: Use the divide-and-conquer integer multiplication algorithm to multiply the two binary integers $\mathit{10011011}\mathit{}\mathbf{and}\mathbf{}\mathit{10111010}$ and .

This keep dividing and conquering is different technique tackles an issue by:

1. This keep dividing and conquering is different technique tackles an issue by:

2. Solving these sub-problems in a recursive manner

3. Combining their responses in an appropriate manner.

The main work being composed of three parts: splitting issues into sub-problems, solving sub-problems outright at the very end of the recursion, and gluing together partial answers. The algorithm's basic recursive structure holds them all together and coordinates them.

Divide and conquer multiplication:

Apply and consider $$\begin{gathered} X\mathit{=}\mathit{10011011} \\ Y\mathit{=}\mathit{10111010} \end{gathered}$$

$$\begin{gathered} P\mathit{1}\mathit{}\mathit{=}\mathit{}multiply\mathit{}\mathit{(}\mathit{}X\mathit{1}\mathit{}\mathit{,}\mathit{}Y\mathit{1}\mathit{)} \\ P\mathit{2}\mathit{}\mathit{=}\mathit{}multiply\mathit{}\mathit{(}\mathit{}Xr\mathit{}\mathit{,}\mathit{}Yr\mathit{)} \\ P\mathit{3}\mathit{}\mathit{=}\mathit{}multiply\mathit{}\mathit{(}\mathit{}X\mathit{1}\mathit{}\mathit{+}\mathit{}Xr\mathit{}\mathit{,}\mathit{}Y\mathit{1}\mathit{}\mathit{+}\mathit{}Yr\mathit{)} \\ X\mathit{}\mathit{*}\mathit{}Y\mathit{}\mathit{=}\mathit{}P\mathit{1}\mathit{}\mathit{*}\mathit{}\left(2^n\right)\mathit{}\mathit{+}\mathit{}\left(P3-P2-P1\right)\mathit{}\mathit{*}\mathit{}\left(2^{\mathrm{4}}\right)\mathit{}\mathit{+}\mathit{}P\mathit{2} \end{gathered}$$

Here, given binary number divided into two ( N / 2 )

$$\begin{gathered} X\mathit{1}\mathit{}\mathit{=}\mathit{}\mathit{1001}\mathit{}\mathit{,}\mathit{}Y\mathit{1}\mathit{}\mathit{=}\mathit{}\mathit{1011}\mathit{}\mathit{,}\mathit{}Xr\mathit{}\mathit{=}\mathit{}\mathit{1011}\mathit{}\mathit{,}\mathit{}Yr\mathit{}\mathit{=}\mathit{}\mathit{1010} \\ X\mathit{1}\mathit{}\mathit{+}\mathit{}Xr\mathit{}\mathit{=}\mathit{}\mathit{1001}\mathit{}\mathit{+}\mathit{}\mathit{1011}\mathit{}\mathit{=}\mathit{}\mathit{10100} \\ Y\mathit{1}\mathit{}\mathit{+}\mathit{}Yr\mathit{}\mathit{=}\mathit{}\mathit{1011}\mathit{}\mathit{+}\mathit{}\mathit{1010}\mathit{}\mathit{=}\mathit{}\mathit{10101} \\ \mathrm{X}1*\mathrm{Y}1=1100011\mathrm{call}\mathrm{it}\mathrm{is}\mathrm{P}1 \end{gathered}$$

Find Xr * Yr recursively we get,

Xr * Yr = 1011 * 1010 = 1101110 calling it as P2

Find $\left(\mathrm{X}1+\mathrm{Xr}\right)\mathrm{x}\left(\mathrm{Y}1+\mathrm{Yr}\right)$recursively we are get,

$\left(\mathrm{X}1+\mathrm{Xr}\right)\mathrm{x}\left(\mathrm{Y}1+\mathrm{Yr}\right)=110100100$

Counting of P3 - P2 - P1

P3 - P2 - P1 = 110100100 - 1101110 - 1100011

=11010011

Finally here we can get last answer:

$$\begin{gathered} \mathrm{P}1*\left(2^{\mathrm{n}}\right)+\left(\mathrm{P}3-\mathrm{P}2-\mathrm{P}1\right)*\left(2^4\right)+\mathrm{P}2 \\ =1100011*100000000+11010011*00010000+1101110 \\ =110001100000000+110100110000+1101110 \\ =0111000010011110 \\ 10011011*10111010=111000010011110 \end{gathered}$$

This is the required answer.