Lista 2, Zadanie 10

by Jerry Sky

Problem

Mamy x=(1001)2y=(1011)2 x = (1001)_2\\ y = (1011)_2

Chcemy dostać x⋅yx \cdot y wykorzystując metodę „divide and conquer”.

Concept

Możemy podzielić liczby xx oraz yy na dwie części: x=2n2⋅xL+xRy=2n2⋅yL+yR x = 2^{\frac{n}{2}} \cdot x_L + x_R\\ y = 2^{\frac{n}{2}} \cdot y_L + y_R gdzie nn to liczba bitów, aL,aRa_L,a_R to lewa oraz prawa połowa część bitów liczby a∈{x,y}a \in \{x,y\}.

Wówczas mamy x⋅y=(2n2⋅xL+xR)⋅(2n2⋅yL+yR)==2n⋅xLyL+2n2⋅(xLyR+xRyL)+xRyR x \cdot y = (2^{\frac{n}{2}} \cdot x_L + x_R) \cdot (2^{\frac{n}{2}} \cdot y_L + y_R)=\\ = 2^n\cdot x_Ly_L + 2^{\frac{n}{2}}\cdot (x_Ly_R + x_Ry_L) + x_Ry_R

Wiemy, że xLyR=(xL+xR)(yL+yR)−xLyL−xRyR x_L y_R = (x_L + x_R)(y_L + y_R) - x_L y_L - x_R y_R więc będziemy wykonywać tylko 3 n2\frac{n}{2}-bitowe pod-problemy:

Rozwiązanie

n=4n=4

x=(1001)2=2n2⋅xL+xR=22⋅(10)2+(01)2y=(1011)2=2n2⋅yL+yR=22⋅(10)2+(11)2 x = (1001)_2 = 2^{\frac{n}{2}} \cdot x_L + x_R = 2^2 \cdot (10)_2 + (01)_2\\ y = (1011)_2 = 2^{\frac{n}{2}} \cdot y_L + y_R = 2^2 \cdot (10)_2 + (11)_2 Part1= xL⋅yL=(10)2⋅(10)2Part2= xR⋅yR=(01)2⋅(11)2Part3= (xL+xR)⋅(yL+yR)=(11)2⋅(101)2 \begin{aligned} \mathrm{Part}_1 =&~ x_L \cdot y_L =& (10)_2 &\cdot (10)_2\\ \mathrm{Part}_2 =&~ x_R \cdot y_R =& (01)_2 &\cdot (11)_2\\ \mathrm{Part}_3 =&~ (x_L + x_R)\cdot(y_L + y_R) =& (11)_2 &\cdot (101)_2 \end{aligned}

x⋅y=Part1⋅24+(Part3−Part1−Part2)⋅2n2+Part2 x \cdot y = \mathrm{Part}_1 \cdot 2^4 + (\mathrm{Part}_3 - \mathrm{Part}_1 - \mathrm{Part}_2) \cdot 2^{\frac{n}{2}} + \mathrm{Part}_2

Najpierw musimy rozwiązać jednak ∀i=1,2,3 Parti\forall_{i=1,2,3}~\mathrm{Part}_i.

Part1\mathrm{Part}_1:

Lokalne n=2n=2 Part1=(10)2⋅(10)2 \mathrm{Part}_1 = (10)_2 \cdot (10)_2 Taka sama sytuacja, więc x=21⋅(1)2+(0)2y=21⋅(1)2+(0)2 x = 2^1 \cdot (1)_2 + (0)_2\\ y = 2^1 \cdot (1)_2 + (0)_2 Tutaj mamy do czynienia z liczbami jedno-bitowymi, więc możemy już mnożyć: Part1,1= (1)2⋅(1)2=(1)2Part1,2= (0)2⋅(0)2=(0)2Part1,3= (1)2⋅(1)2=(1)2 \begin{aligned} \mathrm{Part}_{1,1} =&~ (1)_2 \cdot (1)_2 = (1)_2\\ \mathrm{Part}_{1,2} =&~ (0)_2 \cdot (0)_2 = (0)_2\\ \mathrm{Part}_{1,3} =&~ (1)_2 \cdot (1)_2 = (1)_2 \end{aligned} Więc Part1=Part1,1⋅22+(Part1,3−Part1,1−Part1,2)⋅21+Part1,2==22+0⋅21+0=22=(100)2 \mathrm{Part}_1 = \mathrm{Part}_{1,1} \cdot 2^2 + (\mathrm{Part}_{1,3} - \mathrm{Part}_{1,1} - \mathrm{Part}_{1,2}) \cdot 2^1 + \mathrm{Part}_{1,2} =\\ =2^2 + 0 \cdot 2^1 + 0 = 2^2 = (100)_2

Part2\mathrm{Part}_2 oraz Part3\mathrm{Part}_3

Analogicznie do Part1\mathrm{Part}_1.

W przypadku Part3\mathrm{Part}_3 mamy do czynienia z nieparzystą liczbą bitów. Wówczas bierzemy ⌈n2⌉\lceil\frac{n}{2}\rceil bądź ⌊n2⌋\lfloor\frac{n}{2}\rfloor gdzie n=max⁡{sizeof(x),sizeof(y)}n = \max\{\mathrm{sizeof}(x),\mathrm{sizeof}(y)\} przy dzieleniu liczb na części RR oraz LL.
Liczby x,yx,y tutaj to oczywiście (11)2(11)_2 oraz (101)2(101)_2 które się pojawiają w Part3\mathrm{Part}_3.

Scalanie rozwiązania

Mamy Part1=(100)2\mathrm{Part}_1 = (100)_2, Part2=(11)2\mathrm{Part}_2 = (11)_2, Part3=(1111)2\mathrm{Part}_3 = (1111)_2.

Zatem x⋅y=24⋅(100)2+(11112−1002−112)⋅22+(11)2==24⋅(100)2+22⋅(1000)2+(11)2==(1100011)2. x \cdot y = 2^4 \cdot (100)_2 + (1111_2 - 100_2 - 11_2) \cdot 2^2 + (11)_2=\\ = 2^4 \cdot (100)_2 + 2^2 \cdot (1000)_2 + (11)_2=\\ = (1100011)_2.