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'})