title: Python Binary Multiplication. Divide and Conquer
body: <p>I need to understand why my code gives wrong answers. The task is to create binary multiplication by divide and conquer method. I found some papers that describe this type of problem: 
  <a href="https://en.wikibooks.org/wiki/Algorithms/Divide_and_Conquer#Divide_and_Conquer_Multiplication" rel="nofollow noreferrer">wikibooks algorithms</a>
  <a href="http://www.utsc.utoronto.ca/~bretscher/b36/f13/lectures/w4.pdf" rel="nofollow noreferrer">UTSC paper (page 4)</a></p>
  
  <p>Here is my Python code (3.5.2)</p>
  
  <pre><code>def add(A, B):
      a_str = "".join([str(a) for a in A])
      b_str = "".join([str(b) for b in B])
  
      bin_a = int(a_str, 2)
      bin_b = int(b_str, 2)
  
      return [int(a) for a in str(bin(bin_a + bin_b))[2:]]
  
  
  def add_n(*args):
      if len(args) &lt;= 1:
          return args[0]
  
      bin_sum = [0]
      for num in args:
          bin_sum = add(bin_sum, num)
  
      return bin_sum
  
  
  def shift(A, n):
      if n &lt;= 0:
          return A
  
      a_str = "".join([str(a) for a in A])
  
      bin_a = int(a_str, 2)
      bin_a = bin(bin_a &lt;&lt; n)
      return [int(a) for a in str(bin_a)[2:]]
  
  
  def lfill(A, n):
      return [0] * (n - len(A)) + A
  
  
  def multiply(A, B):
      n = len(A)
      half = n // 2
  
      if n &lt;= 1:
          return [A[0] * B[0]]
  
      xl, xh = A[:half], A[half:]
      yl, yh = B[:half], B[half:]
  
      a = multiply(xh, yh)
      b = multiply(xh, yl)
      c = multiply(xl, yh)
      d = multiply(xl, yl)
  
      b = add(b, c)
      a = shift(a, n)
      b = shift(b, half)
  
      return add_n(a, b, d)
  </code></pre>
  
  <p>The problematic test 1:</p>
  
  <pre><code>A = [1, 1, 1, 1]
  B = [0, 1, 0, 0]
  result: [1, 1, 1, 1, 0]
  real result: [1, 1, 1, 1, 0, 0]
  </code></pre>
  
  <p>The problematic test 2:</p>
  
  <pre><code>A = [1, 1, 1, 1]
  B = [0, 0, 0, 1]
  result: [1, 1, 1, 1, 0, 0, 0]
  real result: [1, 1, 1, 1]
  </code></pre>
  
  <p>Value trace for test 2:</p>
  
  <pre><code>              n half
  Before Shift [2, 1]: a: [1] b:[1]
  After Shift:         a: [1, 0, 0] b:[1, 0]
  Before Shift [2, 1]: a: [0] b:[0]
  After Shift:         a: [0] b:[0]
  Before Shift [2, 1]: a: [1] b:[1]
  After Shift:         a: [1, 0, 0] b:[1, 0]
  Before Shift [2, 1]: a: [0] b:[0]
  After Shift:         a: [0] b:[0]
  Before Shift [4, 2]: a: [1, 1, 0] b:[1, 1, 0]
  After Shift:         a: [1, 1, 0, 0, 0, 0, 0] b:[1, 1, 0, 0, 0]
  </code></pre>
  
  <p>So, as you can see the problem is in the count of zero's, but from case to case it's different. This code doesn't work for all binaries which are unpaired length, but it's not a problem because it could be easily normalized.</p>