2
\$\begingroup\$

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:

enter image description here

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Not a full review, but bn(n) could be bn(n): return list(bin(n))[2:]. \$\endgroup\$ – Daniel Nov 29 '17 at 9:05
  • \$\begingroup\$ Thou not part of the algo, albeit a good tip for improving Python code. \$\endgroup\$ – MarkokraM Nov 29 '17 at 9:08
  • \$\begingroup\$ Can you maybe provide example how this code is supposed to be used? Because at the moment when I run your code, nothing happens \$\endgroup\$ – Ludisposed Nov 29 '17 at 9:36
  • \$\begingroup\$ In the last for loop you can remove if x not y and then you see print to work. At the moment print triggers only if algo doesnt return correct answer. Enough or still need to change the example? \$\endgroup\$ – MarkokraM Nov 29 '17 at 9:45
  • 1
    \$\begingroup\$ Note that you may not incorporate answers into your question, This is called answer invalidation (or comment invalidation in this particular case) and is frowned upon on CR. Best would be to change back your code to the original \$\endgroup\$ – Ludisposed Nov 29 '17 at 10:43
1
\$\begingroup\$

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)}")
\$\endgroup\$
  • \$\begingroup\$ Im actually using Python to transfer algo to different platform where Im limited to use very limited set of language constructors. Im not totally sure but stack based isnt possible there, only recursion. But I really need to consider this if good solution comes up. And you are right, I had to increase recursion limit to 10000 to get bigger numbers working. I fully understand naming conventions. But I also noticed that by simplest possible names some patterns of the code can be recognized visually from the structure itself which is kind of cool. So style indeed is important in many ways. \$\endgroup\$ – MarkokraM Nov 29 '17 at 11:07
  • \$\begingroup\$ @MarkokraMc What do you mean by "limited set of language constructors"? And why should a stack based solution not be possible? \$\endgroup\$ – Raimund Krämer Nov 29 '17 at 12:00
  • \$\begingroup\$ It means the DSL I'm using has short-circuit operators and list processing capabilities and that loops needs to be created by anonymous recursion, no side effects are allowed for example. This possibly limits using stack based approach? \$\endgroup\$ – MarkokraM Nov 29 '17 at 12:49
  • \$\begingroup\$ @MarkokraM Added alternative, and I don't quite understand what you mean? \$\endgroup\$ – Ludisposed Nov 29 '17 at 13:58
  • \$\begingroup\$ Using ´len´, ´max´, ´for´ list comprehension, ´mod´/´idiv´ functions, ´multiplication´, ´minus´, ´plus´, they all add a lot more language constructors than I was hoping. Could ´mod´/´idiv´ be replaced by booleans checks because in binary only 0 and 1 are expected operands? Anyway, I think I need to digest more with this and play around to see, how could I apply... \$\endgroup\$ – MarkokraM Nov 29 '17 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.