CODEWITHSUNDEEP
pythonbinarymultiplicationdivide-and-conquer
Mr.Xyzed
Mr.Xyzed

Reputation: 43

Python Binary Multiplication. Divide and Conquer

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.

Upvotes: 1

Views: 2364

Answers (1)

Mr.Xyzed
Mr.Xyzed

Reputation: 43

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)

Upvotes: 1

Related Questions