Python Binary Multiplication. Divide and Conquer

Question

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: wikibooks algorithms UTSC paper (page 4)

Here is my Python code (3.5.2)

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) <= 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 <= 0:
        return A

    a_str = "".join([str(a) for a in A])

    bin_a = int(a_str, 2)
    bin_a = bin(bin_a << 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 <= 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)

The problematic test 1:

A = [1, 1, 1, 1]
B = [0, 1, 0, 0]
result: [1, 1, 1, 1, 0]
real result: [1, 1, 1, 1, 0, 0]

The problematic test 2:

A = [1, 1, 1, 1]
B = [0, 0, 0, 1]
result: [1, 1, 1, 1, 0, 0, 0]
real result: [1, 1, 1, 1]

Value trace for test 2:

              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]

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.

What have you done to diagnose the problem? I don't see any attempt to check which intermediate values might be incorrect, or to trace the execution flow. — Prune
– Prune, Commented Feb 15, 2018 at 19:55
Added, trace for Test 2. Actually, because this algorithm is recursive it has a lot of different values. I was using Debug but seems like the problem is in the algorithm itself. — Mr.Xyzed
– Mr.Xyzed, Commented Feb 15, 2018 at 20:17
As I assume this to be homework, I will not give you the solution but I'll give you this pointer: Consider MSB/LSB. Which bits are which? — JohanL
– JohanL, Commented Feb 15, 2018 at 20:43

Mr.Xyzed · Accepted Answer · 2018-02-16 15:15:50Z

1

Correct multiply function:

def multiply(A, B):
n = len(A)
half = n // 2

if n <= 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)

d = shift(d, n)
b = shift(b, half)

return add_n(a, b, d)

answered Feb 16, 2018 at 15:15

Mr.Xyzed

439 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

JohanL Over a year ago

I haven't checked your solution but I imagine it generates the correct result, however, it has very strange variable names, as xl and yl contains the high bits and xh and yh contains the low bits. I think a better solution would be to just change (in the original implementation) 'xl, xh = A[:half], A[half:]` to xh, xl = A[:half], A[half:] and the same for yl, yh and B. I.e., I have just reversed xl and xh.

Collectives™ on Stack Overflow

Python Binary Multiplication. Divide and Conquer

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related