title: Python binary multiplication algorithm?
body: <p>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.</p>
  
  <pre><code>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 &gt; 0:
      # concatenating a tuple of size &lt;diff&gt; with tuple b (all elements are 0s)
      b = ((0,) * diff) + b   
  elif diff &lt; 0:
      # concatenating a tuple of size &lt;-diff&gt; 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 &gt; 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()
  </code></pre>