Divide and Conquer

Given two binary strings that represent value of two integers, find the product of two strings. For example, if the first bit string is “1100” and second bit string is “1010”, output should be 120.

For simplicity, let the length of two strings be same and be n.

A Naive Approach is to follow the process we study in school. One by one take all bits of second number and multiply it with all bits of first number. Finally add all multiplications. This algorithm takes O(n^2) time.

product

Using Divide and Conquer, we can multiply two integers in less time complexity. We divide the given numbers in two halves. Let the given numbers be X and Y.

For simplicity let us assume that n is even

 

X =  Xl*2n/2 + Xr    [Xl and Xr contain leftmost and rightmost n/2 bits of X]
Y =  Yl*2n/2 + Yr    [Yl and Yr contain leftmost and rightmost n/2 bits of Y]

The product XY can be written as following.

XY = (Xl*2n/2 + Xr)(Yl*2n/2 + Yr)
   = 2n XlYl + 2n/2(XlYr + XrYl) + XrYr

   If we take a look at the above formula, there are four multiplications of size n/2, so we basically divided the problem of size n into for sub-problems of size n/2. But that doesn’t help because solution of recurrence T(n) = 4T(n/2) + O(n) is O(n^2). The tricky part of this algorithm is to change the middle two terms to some other form so that only one extra multiplication would be sufficient.

[ad type=”banner”]

The following is tricky expression for middle two terms.

XlYr + XrYl = (Xl + Xr)(Yl + Yr) - XlYl- XrYr

So the final value of XY becomes

XY = 2n XlYl + 2n/2 * [(Xl + Xr)(Yl + Yr) - XlYl - XrYr] + XrYr

With above trick, the recurrence becomes T(n) = 3T(n/2) + O(n) and solution of this recurrence is O(n1.59).

What if the lengths of input strings are different and are not even? To handle the different length case, we append 0’s in the beginning. To handle odd length, we put floor(n/2) bits in left half and ceil(n/2) bits in right half. So the expression for XY changes to following.

The above algorithm is called Karatsuba algorithm and it can be used for any base.

Following is C++ implementation of above algorithm.

[pastacode lang=”cpp” manual=”%2F%2F%20C%2B%2B%20implementation%20of%20Karatsuba%20algorithm%20for%20bit%20string%20multiplication.%0A%23include%3Ciostream%3E%0A%23include%3Cstdio.h%3E%0A%20%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20FOLLOWING%20TWO%20FUNCTIONS%20ARE%20COPIED%20FROM%20http%3A%2F%2Fgoo.gl%2Fq0OhZ%0A%2F%2F%20Helper%20method%3A%20given%20two%20unequal%20sized%20bit%20strings%2C%20converts%20them%20to%0A%2F%2F%20same%20length%20by%20adding%20leading%200s%20in%20the%20smaller%20string.%20Returns%20the%0A%2F%2F%20the%20new%20length%0Aint%20makeEqualLength(string%20%26str1%2C%20string%20%26str2)%0A%7B%0A%20%20%20%20int%20len1%20%3D%20str1.size()%3B%0A%20%20%20%20int%20len2%20%3D%20str2.size()%3B%0A%20%20%20%20if%20(len1%20%3C%20len2)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%20%3B%20i%20%3C%20len2%20-%20len1%20%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20str1%20%3D%20’0’%20%2B%20str1%3B%0A%20%20%20%20%20%20%20%20return%20len2%3B%0A%20%20%20%20%7D%0A%20%20%20%20else%20if%20(len1%20%3E%20len2)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%20%3B%20i%20%3C%20len1%20-%20len2%20%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20str2%20%3D%20’0’%20%2B%20str2%3B%0A%20%20%20%20%7D%0A%20%20%20%20return%20len1%3B%20%2F%2F%20If%20len1%20%3E%3D%20len2%0A%7D%0A%20%0A%2F%2F%20The%20main%20function%20that%20adds%20two%20bit%20sequences%20and%20returns%20the%20addition%0Astring%20addBitStrings(%20string%20first%2C%20string%20second%20)%0A%7B%0A%20%20%20%20string%20result%3B%20%20%2F%2F%20To%20store%20the%20sum%20bits%0A%20%0A%20%20%20%20%2F%2F%20make%20the%20lengths%20same%20before%20adding%0A%20%20%20%20int%20length%20%3D%20makeEqualLength(first%2C%20second)%3B%0A%20%20%20%20int%20carry%20%3D%200%3B%20%20%2F%2F%20Initialize%20carry%0A%20%0A%20%20%20%20%2F%2F%20Add%20all%20bits%20one%20by%20one%0A%20%20%20%20for%20(int%20i%20%3D%20length-1%20%3B%20i%20%3E%3D%200%20%3B%20i–)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20firstBit%20%3D%20first.at(i)%20-%20’0’%3B%0A%20%20%20%20%20%20%20%20int%20secondBit%20%3D%20second.at(i)%20-%20’0’%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20boolean%20expression%20for%20sum%20of%203%20bits%0A%20%20%20%20%20%20%20%20int%20sum%20%3D%20(firstBit%20%5E%20secondBit%20%5E%20carry)%2B’0’%3B%0A%20%0A%20%20%20%20%20%20%20%20result%20%3D%20(char)sum%20%2B%20result%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20boolean%20expression%20for%203-bit%20addition%0A%20%20%20%20%20%20%20%20carry%20%3D%20(firstBit%26secondBit)%20%7C%20(secondBit%26carry)%20%7C%20(firstBit%26carry)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20if%20overflow%2C%20then%20add%20a%20leading%201%0A%20%20%20%20if%20(carry)%20%20result%20%3D%20’1’%20%2B%20result%3B%0A%20%0A%20%20%20%20return%20result%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20multiply%20single%20bits%20of%20strings%20a%20and%20b%0Aint%20multiplyiSingleBit(string%20a%2C%20string%20b)%0A%7B%20%20return%20(a%5B0%5D%20-%20’0′)*(b%5B0%5D%20-%20’0′)%3B%20%20%7D%0A%20%0A%2F%2F%20The%20main%20function%20that%20multiplies%20two%20bit%20strings%20X%20and%20Y%20and%20returns%0A%2F%2F%20result%20as%20long%20integer%0Along%20int%20multiply(string%20X%2C%20string%20Y)%0A%7B%0A%20%20%20%20%2F%2F%20Find%20the%20maximum%20of%20lengths%20of%20x%20and%20Y%20and%20make%20length%0A%20%20%20%20%2F%2F%20of%20smaller%20string%20same%20as%20that%20of%20larger%20string%0A%20%20%20%20int%20n%20%3D%20makeEqualLength(X%2C%20Y)%3B%0A%20%0A%20%20%20%20%2F%2F%20Base%20cases%0A%20%20%20%20if%20(n%20%3D%3D%200)%20return%200%3B%0A%20%20%20%20if%20(n%20%3D%3D%201)%20return%20multiplyiSingleBit(X%2C%20Y)%3B%0A%20%0A%20%20%20%20int%20fh%20%3D%20n%2F2%3B%20%20%20%2F%2F%20First%20half%20of%20string%2C%20floor(n%2F2)%0A%20%20%20%20int%20sh%20%3D%20(n-fh)%3B%20%2F%2F%20Second%20half%20of%20string%2C%20ceil(n%2F2)%0A%20%0A%20%20%20%20%2F%2F%20Find%20the%20first%20half%20and%20second%20half%20of%20first%20string.%0A%20%20%20%20%2F%2F%20Refer%20http%3A%2F%2Fgoo.gl%2FlLmgn%20for%20substr%20method%0A%20%20%20%20string%20Xl%20%3D%20X.substr(0%2C%20fh)%3B%0A%20%20%20%20string%20Xr%20%3D%20X.substr(fh%2C%20sh)%3B%0A%20%0A%20%20%20%20%2F%2F%20Find%20the%20first%20half%20and%20second%20half%20of%20second%20string%0A%20%20%20%20string%20Yl%20%3D%20Y.substr(0%2C%20fh)%3B%0A%20%20%20%20string%20Yr%20%3D%20Y.substr(fh%2C%20sh)%3B%0A%20%0A%20%20%20%20%2F%2F%20Recursively%20calculate%20the%20three%20products%20of%20inputs%20of%20size%20n%2F2%0A%20%20%20%20long%20int%20P1%20%3D%20multiply(Xl%2C%20Yl)%3B%0A%20%20%20%20long%20int%20P2%20%3D%20multiply(Xr%2C%20Yr)%3B%0A%20%20%20%20long%20int%20P3%20%3D%20multiply(addBitStrings(Xl%2C%20Xr)%2C%20addBitStrings(Yl%2C%20Yr))%3B%0A%20%0A%20%20%20%20%2F%2F%20Combine%20the%20three%20products%20to%20get%20the%20final%20result.%0A%20%20%20%20return%20P1*(1%3C%3C(2*sh))%20%2B%20(P3%20-%20P1%20-%20P2)*(1%3C%3Csh)%20%2B%20P2%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20aboev%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20printf%20(%22%25ld%5Cn%22%2C%20multiply(%221100%22%2C%20%221010%22))%3B%0A%20%20%20%20printf%20(%22%25ld%5Cn%22%2C%20multiply(%22110%22%2C%20%221010%22))%3B%0A%20%20%20%20printf%20(%22%25ld%5Cn%22%2C%20multiply(%2211%22%2C%20%221010%22))%3B%0A%20%20%20%20printf%20(%22%25ld%5Cn%22%2C%20multiply(%221%22%2C%20%221010%22))%3B%0A%20%20%20%20printf%20(%22%25ld%5Cn%22%2C%20multiply(%220%22%2C%20%221010%22))%3B%0A%20%20%20%20printf%20(%22%25ld%5Cn%22%2C%20multiply(%22111%22%2C%20%22111%22))%3B%0A%20%20%20%20printf%20(%22%25ld%5Cn%22%2C%20multiply(%2211%22%2C%20%2211%22))%3B%0A%7D” message=”C++ Programming” highlight=”” provider=”manual”/]

Output:

120
60
30
10
0
49
9

Time Complexity: Time complexity of the above solution is O(n1.59).

Time complexity of multiplication can be further improved using another Divide and Conquer algorithm, fast Fourier transform. We will soon be discussing fast Fourier transform as a separate post.

[ad type=”banner”]