Multiplying binary numbers digit by digit and carry method in Python

Question

I have two numbers encoded in a reversed list of digits. First I made multiplication in "Peano" way:

#from summa import summa
#from predecessor import predecessor

#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)))

but my intention is to find out, if carry method presented below is more efficient.

While the algo itself should work, I need some assistance, if the middle part of it could be optimized. At the moment it looks overly complex, but I haven't find a way to simplify it. Of course it could be an unavoidable effect of the way I have chosen to carry and pass parameters, but if someone could either confirm the case or do some optimization suggestions, I'd greatly appreciate it.

# encode int to binary list
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]

# 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:
            # clumsy part is the formation of A and x
            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), [], [], [])
# test cases
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)

Please note the comment: "clumsy part is the formation of A and x" which is due to required optimization.

The last double for loop iterates numbers from 0 to 100 and multiplies them, which is for checking that algo works correctly.

Note, that I can do only simple comparison, boolean checks and list cut/concat operations on the algo.

Addition

In the simple sample output:

print(multiply2(bn(10), bn(10)), bn(10*10))

both lists should be same.

Also

This algo is based on the schema presented below, althought the one below is using base ten numbers, but carrying logic is same in the right part of the spreadsheet:

Left part is the common multiplication shema learnt in the elementary schools and one really could to repeated additions as on my commented "Peano" example. But my intuition says multiply2 method is faster until we really want to go to the Fast Fourier transform algorithms.

Answer 1

Python style

Style is important! Will you be able to read this code after a few months? I have a really hard time understanding this at first sight.

• Use a if __name__ == '__main__'
• Use built-ins like this bn(n): return list(map(int, bin(n)[:1:-1]))] as suggested by @Coal_ with some changes to reverse the bin representation and change it a an integer
• Use indentation of 4 spaces, this will make your code alot more readable. Currently you have mixed 4 indent with 2 indent, my eyes don't like this :)
• Use more descriptive names, _(c, d, e, f, g) what do they mean? It is not clear for a Code reviewer.
• Don't try to shorten lines as much as possible. For instance,

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), [], [], [])

This is short I agree, but not really nice to read or discriptive what it does at first sight.

if is_zero(a) or is_zero(b):
    return [0]    
elif is_one(a):
    return b
elif is_one(b):
    return a    
else:
    ....

Reads alot better in my opinion.

I would suggest to read up on PEP which has alot of nice pointers for Python style.

Algo

This should be possible without recursion, when I choose a big value you will get an error:

print(multiply2(bn(100000000000), bn(100000000000)), bn(100000000000*100000000000))
RecursionError: maximum recursion depth exceeded in comparison

You could avoid this by increasing the recursion depth but this is more of a hack then a solution.

How about a stack based approach to avoid the recursion?

---

Alternative approach

Using a stack based approach

def bn(n):
    return list(map(int, bin(n)[:1:-1]))

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

def add_lists(first, second):
    n = max(len(first), len(second))
    first += [0] * (n - len(first))
    second += [0] * (n - len(second))
    return [first[i] + second[i] for i in range(n)]

def carry_over(first_num, second_num):
    stack, overflow = [], 0
    for i in range(len(second_num)):
        if second_num[i] == 1:
            stack = add_lists(stack, [0] * i + first_num)

    for i in range(len(stack)):
        stack[i] += overflow
        overflow = stack[i] // 2
        stack[i] %= 2

    while overflow > 0:
        stack.append(overflow % 2)
        overflow //= 2

    return stack

def multiply2(first_num, second_num):    
    if is_zero(first_num) or is_zero(second_num):
        return [0]  
    else:
        return carry_over(first_num, second_num)

if __name__ == "__main__":
    # test cases
    for i in range(101):
        for j in range(101):
            print(f"{multiply2(bn(i), bn(j))}, {bn(i*j)}")