Question

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

Short answer

Multiplication of $\mathit{10011011}\mathit{}\mathrm{and}\mathit{10111010}$is: 111000010011110

Step-by-step solution

Introduction

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.

Division of given binary numbers

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}$$

Multiplication using Divide-and-Conquer

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.