How do I multiply n linear polynomials together in python?

Question

I want to write some python code that finds the coefficients of the polynomial that comes from $(b_0z - a_0)*(b_1z - a_1)*...*(b_nz - a_n)$ when given two lists of $a_0, ..., a_n$ and $b_0, ..., b_n$.

I know that I need to multiply by the n brackets separately using recursion but I'm not getting the right outputs.

This is my attempt so far:

def p(a,b):
    p = [1 for j in range(len(a))]
    p[0] = -a[0]
    p[1] = b[0]
    for j in range(len(a)-1):
        p[j] = p[j-1] * b[j] - p[j] * a[j]
    return p

Answer 1

Your code isn't recursive at all. Two things you'll always find in a a recursive function: the base case, where the answer is known, and a recursive call, where the function calls itself, either directly or indirectly. Neither of these appear in your code.

The first question you should ask yourself, is how can you reduce this problem to a smaller one of the same kind? That's pretty simple in this case. If we have $n$ linear polynomials, assume that we multiply the first $n-1$ of them recursively, and then multiply the result by the last one.

Here is a possible implementation:

def product(a,b):
    assert len(a)==len(b)
    if len(a) == 1:
        return [b[0], -a[0]]
    p = product(a[:-1], b[:-1])
    z = [b[-1]*t for t in p] + [0]
    u = [0] + [-a[-1] * t for t in p]
    return [x+y for x,y in zip(z,u)]  

I hope this is clear to you, but if not, feel free to ask questions.

Answer 2

I think the array p should be initialized with 0s and not 1s.

But in the product formula, you have to make two loops.

We have

$\left(\sum_{j=0}^{n} p[j]x^j\right)\left(b[k]x-a[k]\right)$

$=\sum_{j=0}^{n} p[j]b[k]x^{j+1}-\sum_{j=0}^{n} p[j]a[k]x^{j}$

$=\sum_{j'=1}^{n+1} p[j'-1]b[k]x^{j'}-\sum_{j=0}^{n} p[j]a[k]x^{j}$

$=p[n]b[k] x^{n+1} + \left(\sum_{j=1}^{n} (p[j-1]b[k]-p[j]a[k])x^{j}\right)+p[0]a[k]$

So you must have one loop on k and another on j (in the non-recursive version)