Question

Suppose you design an algorithm to multiply two n-bit integers x and y. The general multiplication technique takes T(n) = O(n2) time. For a more efficient algorithm, you first split each of x and y into their left and right halves, which are n=2 bits long. For example, if x = 100011012, then xL = 10002 and xR = 11012, and x = 24 xL + xR. Then the product of x and y can be re-written as the following: x y = 2n (xL yL) + 2n=2 (xL yR + xR yL) + (xR yR)

Answer 1

See Explaination

Step-by-step explanation:

a) Assume there are n nits each in x and y.SO we divide them into n/2 and n/2 bits.

x = xL * 2^{n/2} + xR

y = yL * 2^{n/2} + yR

x.y = 2^{n}.(xL.yL) + 2^{n/2}.(xL.yR + xR.yL) +(xR.yR)

If you see there are 4 multiplications of size n/2 and we took all other additions and subtractions as O(n).

So T(n) = 4*T(n/2) + O(n)

Now lets find run time using master theorem.

T(n) = a* T(n/b) + O(n^{d})

a = 4

b = 2

d = 1

if a > b^{d}

T(n) = O(n^v) where v is log a base b

In our case T(n) = O(n^v) v = 2

=> T(n) = O(n^{2})

The splittinng method is not benefecial if we solve by this way as the run time is same even if go by the naive approach

b)

x.y = 2^{n}.(xL.yL) + 2^{n/2}.((xL+xR).(yL+yR)-(xL.yL) - (xR.yR)) +(xR.yR)

Here we are doing only three multipliactions as we changed the term.

So T(n) = 3*T(n/2) + O(n)

a = 3

b = 2

d = 1

if a > b^{d}

T(n) = O(n^v) where v is log a base b

In our case T(n) = O(n^v) v = log 3 base 2

v = 1.584

So T(n) = O(n^{1.584})

As we can see this is better than O(n^{2}).Therefore this algorithm is better than the naive approach.