It was exciting working on the assignments of the course "Algorithms and Data structures II " this spring. As we kick started the first assignment we finished the first assignment so early, but for the problem of 'binary multiplication' we had many versions and I also had another fresh idea which is so efficient. As the deadline got closure I didn't tried out that idea.
The idea is inspired from Vethic Mathematics(Nikhilam Sutra-Nikhilam Navataścaramam Daśatah-subtract all from 9 and the last from 10) and the corresponding algorithm explained in [1]. The time complexity is really depends upon the ratio of zeros and ones of the smaller multiplicand unlike most of the other algorithms.
Before we go into actual problem let me briefly explain Nikhilam Sutra (Sutra means Formula in India). Let us multiply these two numbers 98 and 99. First step is to find the common base(power of 10 close the multiplicands) which is 100 here. This is how the sutra works:
98 - 2
99 - 1
-----------------
100-2-1 | 02
= 9702
-----------------
But it is easy to see this in simple algebra. For the base x the multiplicands A,B can be written as (x - a) and (x - b). Hence,
A*B = (x - a)*(x - b)
= x^2 - (a+b) *x + a*b = x(x-a-b) + a*b.
In the same way, if A,B are greater than base then
A*B = (x + a)*(x + b)
= x^2 + (a+b) *x + a*b
= x(x+a+b) + a*b
= x(A+b) + a*b
When the multiplicands are binary numbers the base x is of form 2^n. In the above formula multiplication of deficiencies from the base(a*b) is making us to think the possibility of recurrence in binary number system. Let us now multiply these 2 binary numbers recursively 111 and 111. Here base is 2^2 = 100
Base : 2^2 = 100 Base: 2 = 10
----------------------- -------------------------------------
111 - 11 11 - 1
+ * ==> + *
111 - 11 11 - 1
------------------------ -------------------------------------
100*(111+11)+ 1001 <== 10*(11+1) + 1 = 1000 + 1 = 1001
101000 + 1001
= 110001
-------------------------
Here is the python implementation:def binary_mult(a,b):
# Helper Primitive Operations
lenA = len(a)
lenB = len(b)
if lenA >= lenB:
maxPart = a
minLen = lenB
minPart = b[1:]
else:
maxPart = b
minLen = lenA
minPart = a[1:]
# Base Cases
if lenA == 1:
return b if a[0] == 1 else lenB*[0]
elif lenB == 1:
return a if b[0] == 1 else lenA*[0]
# Divide , conquer and combine
else:
cLeft = binary_add(maxPart,minPart)+[0]*(minLen-1)
aNew, bNew = new_parts(maxPart,minPart)
cRight = binary_mult(aNew, bNew)
c = binary_add(cLeft,cRight)
return c
As you can see above, the left most part of final product is given by cLeft which is simply the binary addition(x(A+b)). Then new_parts(maxPart,minPart) is responsible for subtracting the base from both of the multiplicands(as base is always of the form 10[00...], one can implement this subroutine more efficient than trivial subtraction and you can remove all front zeros which is the result of subtraction - ex: for 1100011 * 100010 Base 1: 100000 , Base 2 : 10. It implies that despite bit length if the multiplicands have many contiguous zeros we get the result so faster !!!). Then cRight is recursively calculate the deficiency multiplications(a*b). Finally c does return the result.
[1].A Generalized Recursive Algorithm for Binary Multiplication based on Vedic Mathematics
I would like to dedicate this article to my teachers Pierre, Joseph, Nikos here in Uppsala University who helped me all the way whenever I was in trouble. Thanks a lot TAs :)
[1].A Generalized Recursive Algorithm for Binary Multiplication based on Vedic Mathematics
