Multiplying polynomials using dictionaries in Python

Question

I want to multiply polynomials as a dictionary without the use of numpy and classes as easily as possible without using external libraries. Saw some posts about it on here but they either use lists, classes or numpy :/

A polynomial is represented by a dict mapping degree to coefficient. For instance:

{0: 7, 2: 5, 4: 3} represents 3x^4 + 5x^2 + 7.

I tried using the following code:

def mlpt(p1,p2):
    p1_times_p2 = {}
    for i in p1:
        erg_coeff = p1[i]
        erg_exp   = i
        for j in p2:
            erg_coeff = erg_coeff * p2[j]
            erg_exp   = erg_exp + j
        p1_times_p2[erg_exp] = erg_coeff
    for i in p2:
        erg_coeff = p2[i]
        erg_exp   = i
        for j in p1:
            erg_coeff = erg_coeff * p1[j]
            erg_exp   = erg_exp + j
        p1_times_p2[erg_exp] = erg_coeff
    return p1_times_p2

However, when I multiply two arbitrary polynomials, I don't seem to get the right result:

# (x^2)(x^2 + x) == x^4 + x^3

p1 = {2: 1}        # x^2
p2 = {1: 1, 2: 1}  # x^2 + x
print( mlpt(p1,p2) )

# EXPECTED OUT: {4: 1, 3: 1}
# ACTUAL OUT:   {5: 1, 3: 1, 4: 1} 

Does anyone have an idea how to fix it? Any help would be greatly appreciated!

Answer 1

Assuming your dicts are {exponent: coefficient}, a simple option would be to have two nested loops which populate the result dict:

def multiply(p1, p2):
    res = {}

    for e1, c1 in p1.items():
        for e2, c2 in p2.items():
            e = e1 + e2
            res[e] = res.get(e, 0) + c1 * c2

    return res

An exercise to the reader: adapt this to perform symbolic computations as in multiply({2:'a',1:'b'},{2:'c'})

Answer 2

A few issues with your code, from least important to most important:

Issue 1

Instead of:

for i in p1:
    erg_coeff = p1[i]
    erg_exp   = i
    ...

python encourages you to use the variables you want directly as loop variables:

for exp, coeff in p1.items():
    ....

In general when iterating on a dictionary d you can iterate over d.keys(), d.values() or d.items().

Issue 2

You are iterating twice over every pair of coeffs:

First you do

for i in p1:
    for j in p2:
        ...

and then you do

for j in p2:
    for i in p1:
        ...

so the work is done at least twice. This doesn't cause a wrong result directly, because when you write p1_times_p2[erg_exp] = erg_coeff you erase and overwrite any work that was done previously in that cell, but still, it is unneeded, inefficient and error-prone to iterate over everything twice. You should have only one set of nested loops in your code.

Issue 3

The main issue, and the one that directly causes the wrong result, is that when you do

erg_coeff = erg_coeff * p2[j]
erg_exp   = erg_exp + j

you are accumulating together some terms that don't correspond to the same exponent at all. Note how erg_exp changes but the previous value of erg_coeff is reused to compute the next value of erg_coeff. This means you're mixing together many coeffs that don't correspond to the correct exponent in the result. This means that in the result, your coeffs will be of the form p1[i] * p2[0] * p2[1] * p2[2] * p2[3] * ... which doesn't correspond to what you get mathematically when you multiply two polynomials.

Instead you should try to write your loop so that it reflects the mathematical formula:

result[k] = sum(p[i] * q[j] for i and j such that i+j == k)

Which in correct python becomes:

for k in range(max(p)+max(q)):
    result[k] = sum(p.get(i, 0) * q.get(k-i,0) for i in range(k+1))

Or written the other way around:

for i,pi in p.items():
    for j,qj in q.items():
        result[i+j] += pi * qj