Binary Multiplication - Can we do it better?

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.

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