Please provide full answer Thanks in advance The standard al

Please provide full answer. Thanks in advance!

The standard algorithm for multiplying two n-bit binary integers x and y costs Theta(n^2). A naive divide-and-conquer algorithm is to let x = 2^n/2 a + b and y = 2^n/2 c + d, then xy = (2^n/2 a + b)(2^n/2 c + d) = 2^n ac + 2^n/2(ad + bc) + bd The complexity is T(n) = 4T(n/2) + Theta(n) = Theta(n^2). There is no improvement to the standard algorithm. By observing that ad + bc = (a + b)(c + d) - (ac + bd), we can use only three multiplications. Describe this divide-and-conquer algorithm in a pseudocode. What is the complexity of the algorithm. Illustrate the algorithm for multiplying integers x = 10011011 and y = 10111010 (just show one level of the recursion).

Solution

Answer A)

function multiply(x, y)

Input: Positive integers x and y,

product n = max(size of x, size of y) if n = 1: return xy

xL, = left part of n/2 (left most [n/2] digit,

xR =right part of n/2 ( rightmost [n/2] bits of x

YL, = left part of n/2 (left most [n/2] digit,

YR =right part of n/2 ( rightmost [n/2] bits of y

P1 = multiply(xL, yL)

P2 = multiply(xR, yR)

P3 = multiply(xL + xR, yL + yR)

return P1 × 2 n + (P3 P1 P2) × 2 n/2 + P2

Answer b) T(n)=3T(n/2)+O(n)• T(n)

Answer c)

you can use karatsuba multiplication technique which uses 3 multiplication and addition

REcursive algorithm

first we write X =10^{n/2 _{a+b y = 10}n/2 c+d}

a,b,c,d are n/2 digits of X and Y

like a=1001 b=1011 c=1011 d=1010

X.Y = (10n/2  a+b ) . (10^{n/2 c+d})

= 10ⁿac + 10^n/2(ad+bc)+bd

but this include 4 multiplication

so recursive approach will be used for calculation this multiplication

1) recursively compute ac(1001* 1011 )= 1012011

2) recursively compute bd ( b=1011 *1010)=1021110

3) recursively compute (a+b)(c+d)= (1001+ 1011)*(1011 +1010)=4066252

here we will use gauss\'s formula

3) - 1) - 2) == ad+bc=(2033133)

so here we can come through only 3 recursive multiplication and addition

a b

x=1001 1011

c d
y=1011 1010

sub problem

x1=(1001*1010) // [a*c]

d1=(1011*1010) // [b*d]

e1= (a+c)*(b+d)-x1-d1

=(2012)*(2021)-x1-d1

NOw again we need to recurse

first subproblem will be

computing x1 (1001*1010)

subproblems:

a b

10 01

c d

10 10

so we will follow above formula agains

so now subproblem will be following

x2= 10*10=100

d2=01*10=10

e2=(10+01)(10+10)-x2-d2

=11(20)=220-x2-d2

so follow again recursively

Answer B)