Translate pseudocode to python?

Question

I need some help translating this pseudocode to python, I made some questions in the code, would really enjoy some help :) The idea behind the code I do understand, a divide and conquer technique to binary multiplication.

How would you guys have written this in python?

def mult(A,B):

        n = len(A)
        if (n <= 1):
            return (A[0]*B[0])

        p = A[0:n/2]
        q = A[n/2:n]
        r = B[0:n/2]
        s = B[n/2:n]

        pr = mult(p,r)
        ps = mult(p,s)
        rq = mult(r,q)
        qs = mult(q,s)

        sum = ps + rq # no problem adding like this I guess

?

Okay, I don't know what this "in" does in the pseudocode aswell as "end". and the shift I suppose it's just to use the "<<" operator. Or maybe not in this case because it's a list, but it's simple to make a help function for that.

Answer 1

First, I don't think this is pseudocode at all, but rather code in a real language, probably one derived from (S)ML. If you knew what language it was it, it would be a lot easier to interpret it—instead of trying to guess what things like shift mean, you could look it up in the docs for that language.

---

That being said, there are a number of things you've clearly translated wrong.

---

First, you turned this:

if |A| ≤ 1

… into this:

n = len(A)
if (n == 1):

Besides adding in meaningless extra parentheses, you've broken the recursive base case of A being empty.

---

Next, par may just mean something like "you can do these in parallel if you want", so it may be OK to ignore it. On the other hand, given that you're taking this from lecture notes for a class in parallel algorithms and data structures, that thing you ignored may be the whole point. Obviously, in Python, you'd need to map it to something different—e.g., create a concurrent.futures.ProcessPoolExecutor, submit the four recursive calls, then wait for all four futures? (Although it's possible this is meant to be a late-as-possible-binding language, in which case you don't want to wait for the futures here, but rather change each expression that uses one of these values so that it waits on the future it needs, and submit those expressions to the executor as well.)

---

Anyway, you've translated the recursive calls to the function being defined into calls to some different function. All of these:

    pr = binary_mult(p,r)
    ps = binary_mult(p,s)
    rq = binary_mult(r,q)
    qs = binary_mult(q,s)

… need to be calling mult.

---

The let … in … end is effectively a way of saying that the first … is a bunch of local variables for the second …. You could translate that by, e.g., replacing the end with a del on each variable, but I think it's fine to ignore that as you have.

But you've left off the most important part, this bit:

shift(pr, n) + shift(sum, n/2) + qs

I'm not sure that last + is a +. It may be a different symbol, or a screenshot taken while a cursor was moving over a +, or a scan of a printout with a speck of dust on the +, or some other great example of why you should post text instead of pictures of text when you want help with the code in that text…

Anyway, you need to do whatever that is doing (and return the result). That's the key piece of the function; all the let … in stuff is just setup for this expression.

---

Going with your guesses as to what the functions mean, and my guesses as to the almost-SML syntax, ignoring the parallel bit, something like what you wrote is close to a direct translation:

def shift(A, n):
    # Taking a wild guess
    return A + [0 for _ in range(n)]

def mult(A, B):
    n = len(A)
    if n <= 1:
        return [A[0] * B[0]]
    else:
        p, q = A[:n//2], A[n//2:]
        r, s = B[:n//2], B[n//2:]
        pr, ps, rq, qs = mult(p, r), mult(p, s), mult(r, q), mult(q, s)
        sum = ps + rq
        return pr << n + sum << n//2 + qs

I'm willing to bet we've guessed at least one thing wrong. For example, maybe + is supposed to be element-wise addition rather than list concatenation. The only way to find out is to run it with some numbers and check the output. The only thing is, I don't even know what the inputs are supposed to be. Maybe big-endian place-value lists of binary digits? In that case, + has to be element addition with carry.

In fact, it's possible that these things are supposed to be usable simultaneously as numbers and as big-endian lists of bits. No built-in Python type works that way, but it's not too hard to build one… or to find one on PyPI. bitarray and bitstring look like plausible candidates.