binarymultiply.py

#from summa import summa
#from predecessor import predecessor

def bn(n):
  return list(reversed(list(map(lambda x: 1 if x == "1" else 0, "{0:b}".format(n)))))

def is_zero(n):
  return not n[1:] and not n[0]

def is_one(n):
  return not n[1:] and n[0]

#def multiply(m, n):
#  def _(b):
#    return [0] if is_zero(b) else summa(m, _(predecessor(b)))
#  return [0] if is_zero(m) or is_zero(n) else summa(m, _(predecessor(n)))

# multiplication
def multiply2(a, b):
  def _(c, d, f, g, e):
    if not b and not c:
      return g + (e if e[1] else e[:1])
    if c:
      A = 0 if (0 if (1 if c[0] and d else 0) == (e[1] if e else 0) else 1) == (f[0] if f else 0) else 1
      # x = [0, 0] or [1, 0] or [0, 1] or [1, 1]
      x = [A, 1 if ((e[1] if e else 0) or (f[0] if f else 0)) and c[0] and d or \
                   ((e[1] if e else 0) and (f[0] if f else 0)) and not c[0] and d else 0]
      #print(x, c, d, e, f, g)
      return _(c[1:], d, f[1:], (g + e[:1] if e else g), x)
    return g[:1] + _(a, b.pop(0), g[1:] + e, [], [])
  return [0] if is_zero(a) or is_zero(b) else \
           b if is_one(a) else \
           a if is_one(b) else _(a, b.pop(0), [], [], [])

for i in range(101):
  for j in range(101):
    x, y = bn(i*j), multiply2(bn(i), bn(j))
    if x != y:
      print("prod %s * %s = %s:" % (i, j, (i*j)), x, "->", y)