The standard algorithm for multiplying two n-bit binary integers r and y costs t

Question

The standard algorithm for multiplying two n-bit binary integers r and y costs theta (n^2). A naive divide-and-conquer algorithm is to let x = 2^n/2a + b and y = 2^n/2c + d, then xy = (2^n/2a + b)(2^n/2c + 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).

Explanation / Answer

a)Given part: xy = 2^n(ac) + 2^(n/2)(ad + bc) + bd
if we replace ad + bc with our observation given in (a). which is ad + bc = (a + b)(c + d) - (ac + bd).
Our equation becomes.
xy = 2^n(ac) + 2^(n/2)( (a + b)(c + d) -(ac + bd) ) + bd
From the equation what we can infer is that we only need to do multiplication of 3 pairs instead of 4.
which are ac, bd and (a+b)(c+d).

Now lets impart this inference into our pseudocode.

Divide-and-conquer algorithm pseudocode.
function multiply(binaryNumber x, binaryNumber y)
lengthofx = x.length;
lengthofy = y.length;
commonlength = lengthofx;
if(lengthofx not-equal lengthofy)
//make equal by prefixing 0 bits to smaller number
if(lenghtofx < lengthofy)
commonlength = prefixbits(x,lengthofy) //make it to the length of y
else
commonlength = prefixbits(y,lengthofx) //make it to the length of x
  
if(commonlength == 0)
return 0;
if(commonlength == 1) //if binary number is of single bit
return x*y;

firstHalf = commonlength/2;
secondHalf = commonlength - firstHalf;

firstHalfBinaryx = x.substring(0,firstHalf)
secondHalfBinaryx = x.substring(firstHalf,secondHalf)

firstHalfBinaryy = y.substring(0,firstHalf)
secondHalfBinaryy = y.substring(firstHalf,secondHalf)

//Now recursively calculating the three products of input of n/2 length.
numberP1 = multiply(firstHalfBinaryx,firstHalfBinaryy)
numberP2 = multiply(secondHalfBinaryx,secondHalfBinaryy)
  
additionOfFirstAndSecondHalfx = addingBits(firstHalfBinaryx,secondHalfBinaryx)
additionOfFirstAndSecondHalfy = addingBits(firstHalfBinaryy,secondHalfBinaryy)

numberP3 = multiply(additionOfFirstAndSecondHalfx,additionOfFirstAndSecondHalfy)

//Now combining the three products
return numberP1*(1<<(2*secondHalf)) + (numberP3 - numberP2 - numberP1)*(1<<secondHalf) + numberP2

//Here "<<" mean we are shifting bits to create number 2^secondHalf in case of 1<<(2*secondHalf).

b) Time Complexity of the algorithm.
Time Complexity of naive algorithm given is
T(n) = 4T(n/2) + O(n) = O(n^2)
by xy = 2^n(ac) + 2^(n/2)(ad + bc) + bd

But after our small modification the equation becomes
xy = 2^n(ac) + 2^(n/2)( (a + b)(c + d) -(ac + bd) ) + bd

Here in algorithm we are doing multiplication 3 times instead of 4
So out Time complexity becomes
T(n) = 3T(n/2) + O(n) < O(n^2)
which less than earlier time complexity of naive algorithm.

c) x = 10011011 y = 10111010
They both are of equal length so no need to prefix them with bit zero.
Length of x and length of y both are not 0 or 1.

Lets create two halves of both numbers.
firstHalfx = 1001, secondHalfx = 1011
firstHalfy = 1011, secondHalfy = 1010

P1) multiply first firstHalfx with firstHalfy i.e 1001 * 1011
which comes out to be 99(1100011)

P2) Now multiply secondHalfx with scondHalfy i.e 1011 * 1010
which comes out to be 110(1101110)   

addition of FirstHalfx And SecondHalfx i.e 1001 + 1011
which is 10100

addition of FirstHalfx And SecondHalfx i.e 1011 + 1010
which is 10101

P3) Now multiplying both the addition result i.e 10100 * 10101
which comes out to be 420(110100100)

finally we have to perform this last step.
numberP1*(1<<(2*secondHalf)) + (numberP3 - numberP2 - numberP1)*(1<<secondHalf) + numberP2

where 1<<(2*secondHalf) is 2^8 = 256
and 1<<(secondHalf) is 2^4 = 16

Ans = 99*256 + (420-110-99)*16 + 110

Ans = 28830 (111000010011110)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.