How can I create functions that handle polynomials?

Question

I have these problems about polynomials and I've spent about 4 hours on this, but I just can't get it. I'm new to Python and programming and I've tried working it out on paper, but I just don't know.

1. Write and test a Python function negate(p) that negates the polynomial represented by the list of its coeffeicients p and returns a new polynomial (represented as a list). In other words, write a function that makes the list of numbers negative.

2. Write a Python function eval_polynomial(p, x) that returns the value of P(x), where P is the polynomial represented by the list of its coefficients p. For example, eval_polynomial([1, 0, 3], 2) should return 1*2^2 + 0*2 + 3 = 7. Use a single while loop.

3. Write and test a function multiply_by_one_term(p, a, k) that multiplies a given polynomial p, represented by a list of coefficients, by ax^k and returns the product as a new list.

I would really appreciate it if someone could help me.

Solution 1

I'd recommend using numpy.poly1d and numpy.polymul, where the coefficients are a0*x2 + a1*x + a2.

For example, to represent 3*x**2 + 2*x + 1:

p1 = numpy.poly1d([3,2,1])

And with the resulting poly1d object you can operate using *, / and so on...:

print(p1*p1)
#   4      3      2
#9 x + 12 x + 10 x + 4 x + 1

If you want to build your own functions, assuming that p contains the coefficients in order: a0 + a1*x + a2*x**2 + ...:

def eval_polynomial(p,x):
    return sum((a*x**i for i,a in enumerate(p)))

def multiply_by_one_term(p, a, k):
    return [0]*k + [a*i for i in p]

Note

My evaluate function uses exponentials, which can be avoided with Horner's rule, as posted in another answer, which is available in Numpy's polyval function

Solution 2

Please use Horner's Method instead!

For polynomials, you should consider Horner's Method. Its main feature is that computing a polynomial of order N requires only N multiplies and N additions -- no exponentials:

def eval_polynomial(P, x):
    '''
    Compute polynomial P(x) where P is a vector of coefficients, highest
    order coefficient at P[0].  Uses Horner's Method.
    '''
    result = 0
    for coeff in P:
        result = x * result + coeff
    return result

>>> eval_poly([1, 0, 3], 2)
7

You can work through it by hand, or follow the link to see how it works.

Comments

[confusedstudent]

I don't have enough reputation yet, but would vote you up. I actually understood the logic behind your solutions.

[Saullo G. P. Castro]

@confusedstudent great that you understood this logic

[Saullo G. P. Castro]

Nice solution to evaluate the polynomials, could use Numpy's polyval though

[fearless_fool]

numpy is great, but the OP was to write a function. And there are many cases where you'd like to evaluate a polynomial without dragging in all of numpy.

[fearless_fool]

This solution, while clear in its approach, is notably inefficient. Please consider using horner's rule to avoid calling an exponential in each iteration. I suppose I should post that as an answer.