Python binary multiplication algorithm?

Question

I'm writing this python program to be able to understand how to implement the Multiplication algorithm. I've put together a 'master' copy of all my work and all of my instructions and what I've done in order to not have to waste time having 3-4 files to flip between. My question is to ask how do I get started on the shift_left function and the binary_multiplaction functions. I don't understand how to get started with it.

import unittest
import sys


def binary_addition( a, b ):
"""
Binary addition.

:param a: the first operand - a tuple of bits
:param b: the second operand - a tuple of bits
:type a: tuple
:type b: tuple
:return: the sum, as a tuple of bits
:rtype: tuple
"""

# first, ensure that the 2 arrays have the same number of bits,
# by filling in with 0s on the left of the shortest operand
diff = len(a)-len(b)

if diff > 0:
    # concatenating a tuple of size <diff> with tuple b (all elements are 0s)
    b = ((0,) * diff) + b   
elif diff < 0:
    # concatenating a tuple of size <-diff> with tuple a (all elements are 0s)
    a = ((0,) * (-diff)) + a 

c = 0
s = [0] * (len(a)+1)
for j in reversed(range(0,  len(a))):
        d = (a[j] + b[j] + c) // 2
        s[j+1] = (a[j] + b[j] + c) - 2*d
        c = d
s[0] = c

# removing unneeded 0s on the left
if s[0] == 0:
    s.remove(0)

return tuple(s)


def shift_left(a,n):
"""
Shift an array of bits to the L, by adding n 0s on the right.

#. construct a tuple of n elements, all 0s

#. concatenate it to the tuple that has been passed in

#. return the concatenation

:param a: a tuple of bits
:param n: the number of positions over which to shift
:type a: tuple
:return: if n > 0, the L-shifted array; otherwise, the original array; *if the first parameter (`a` ) is not of the `tuple` type, the function should handle it nicely and return an empty tuple. A test in the test suite below checks that this requirement has been met.*
:rtype: tuple
"""
#
return a + (0,) * n


def binary_multiplication(a, b):
"""
Multiply arrays of bits.

#. Initialize the cumulative sum of product (a tuple with 0 as its only element)

#. Go over the bits in `b` (the second multiplicand), in *reverse order*: if current bit is 1, add to the cumulative sum the operand `a`, L-shifted by 0 for rightmost bit, by 1 for bit k-1, by 2 for bit k-2, ...

#. return the cumulative sum

:param a: first multiplicand - an array of bits
:param b: second multiplicand - an array of bits
:type a: tuple
:type b: tuple
:return: an array of bits
:rtype: tuple
"""

#



class Multiplication_unittest( unittest.TestCase):


def test_binary_addition_1(self):
    self.assertEqual( binary_addition((1,0,1),(1,1,1,1)), (1,0,1,0,0))

def test_binary_addition_2(self):
    self.assertEqual( binary_addition((1,1,1,1),(1,0,1)), (1,0,1,0,0))

def test_binary_addition_3(self):
    self.assertEqual( binary_addition((1,0,1,1),(1,1,1,1)), (1,1,0,1,0))

def test_binary_addition_4(self):
    self.assertEqual( binary_addition((0,),(1,)), (1,))

def test_binary_addition_5(self):
    self.assertEqual( binary_addition((1,),(1,)), (1,0))

def test_binary_addition_6(self):
    self.assertEqual( binary_addition((0,),(0,)), (0,))


def test_shift_left_1(self):
    """ Trying to shift a value that is _not_ a tuple (ex. an integer) returns an empty tuple """
    self.assertEqual( shift_left( 5, 3 ), () )


def test_shift_left_2(self):
    """ Shifting by 0 places returns the array that has been passed in """
    self.assertEqual( shift_left((1,1), 0 ), (1,1) )


def test_shift_left_3(self):
    """ Shifting an empty tuple by 1 place return a tuple with 0 as a single element """
    self.assertEqual( shift_left((), 1 ), (0,) )


def test_shift_left_4(self):
    """ Shifting a 1-tuple (with 0 as the only element) by 1 place """
    self.assertEqual( shift_left((0,), 1 ), (0,0) )


def test_shift_left_5(self):
    """ Shifting a 1-tuple (with 1 as the only element) by 1 place """
    self.assertEqual( shift_left((1,), 1 ), (1,0) )


def test_shift_left_6(self):
    """ Shifting 110 (6) by 3 places returns 110000 (6x8=48) """
    self.assertEqual( shift_left((1,1,0), 3 ), (1,1,0,0,0,0) )


def test_multiplication_1(self):
    """ Short operands: 0 x 0 """
    self.assertEqual( binary_multiplication( (0,),(0,)), (0,))  

def test_multiplication_2(self):
    """ Short operands: 0 x 1 """
    self.assertEqual( binary_multiplication( (0,),(1,)), (0,))  

def test_multiplication_3(self):
    """ Short operands: 1 x 0 """
    self.assertEqual( binary_multiplication( (1,),(0,)), (0,))  

def test_multiplication_4(self):
    """ Short operands: 1 x 1 """
    self.assertEqual( binary_multiplication( (1,),(1,)), (1,))  

def test_multiplication_5(self):
    """ Short operands 2 x 1"""
    self.assertEqual( binary_multiplication( (1,0),(1,)), (1,0))  

def test_multiplication_6(self):
    """ Long operands """
    self.assertEqual( binary_multiplication( (1,0,1,1,1,1,0,1),(1,1,1,0,1,1,1,1)), (1,0,1,1,0,0,0,0,0,1,1,1,0,0,1,1))  

def test_multiplication_5(self):
    """ Operands of different sizes """
    self.assertEqual( binary_multiplication( (1,0,0,1,1),(1,1,1,0,1,1,1,1)), (1,0,0,0,1,1,0,1,1,1,1,0,1)) 




def main():
  unittest.main()

if __name__ == '__main__':
   main()

Answer 1

You were not far, and had already done the hard part of addition and shifting.

You still have an error in your test for shift_left because one of your tests require that shifting a non tuple returns an empty tuple, when it currently raises an exception. Here you can either say that the exception is normal and change your test, or explicitely test that the operand is a tuple

def shift_left(a,n):
    ...
    #
    if not isinstance(a, tuple): return ()
    return a + (0,) * n

Once this is done a multiplication is just multiply the product of operand1 by each digit of operand 2 shift the product (to the left) by the position of the digit and add all those products. As digits can only be 0 or 1, it just gives:

def binary_multiplication(a, b):
    ...
    # initialize a null tuple of same size as a for the final sum
    s = (0,) * len(a)
    # take a copy of a for the intermediary products
    m = a[:]
    for i in reversed(range(len(b))):
        if b[i] != 0:     # when digit is one, add the intermediary product
            s = binary_addition(s, m)
        m = shift_left(m, 1)  # shift one per digit in b
    return s

And your tests pass nicely...