[Tutor] Multiplication of polynomials
Remco Gerlich
scarblac@pino.selwerd.nl
Sun, 29 Apr 2001 23:46:58 +0200
On 0, Julieta Rangel <julieta_rangel@hotmail.com> wrote:
*Please* set your email to sending plain text. I have to jump through some
hoops to get html mail into readable form. Not everyone uses Microsoft
products, even though they want you to believe so.
> <html><DIV>If I want to write a program that multiplies
> polynomials, just to show you how illiterate I am at computer
> programming, this is what I would do: I would need the user to enter the
> amount of polynomials that will be multiplying. Lets say the user
> wants to multiply two polynomials. Once the user enters the amount of
> polynomials that will be multiplying, the computer would have to ask the
> degree of the polynomials, say the first polynomial is of third degree and
> the second is a second degree polynomial (2x^3 + x^2 + 3x + 2) * (x^2 +
> 1)Once the person enters the degree of the polynomials, the computer would
> have to ask the coefficient of each of the terms of the polynomials,
> in this case the computer would have to ask the user to enter the
> coefficient of x^3, x^2, x, and c and then the coefficients of the
> second polynomial. Should I have the computer create two lists for
> each polynomial? In one list I would store all the coeffici! ents and
> in another the exponents of the expression.
Let's ignore the way the user gives his input at first. It's relatively
trivial, and there are many ways to do it.
No, two lists aren't necessary. Keep one list for the coefficients, and
you'll know from the length of that list which exponents the numbers belong
to. If you have a list, say, L=[1,2,3,4], then that should be for a 3rd degree
polynomial (len(L)-1), where L[0] is the coefficient of the 0-degree term,
ie the constant. It stands for 4x^3+3x^2+2x+1.
> I'm assuming that if I
> have two lists for each polynomial, I could do the operations
> required. Based on the polynomials I have, the lists of coefficients
> would look like (L1) [2,1,3,2] and (L2)[1,0,1] and my lists of exponents
> would look like (L 3) [3,2,1,0] and (L 4)[2,1,0]. I would then have the
> first element in L1 times each element in L2, so that I get list
> 5 [2,0,2]</DIV>
> <DIV>and 1st element in L3 + each element in L4, so that I get list 6
> [5,4,3]. Then I would have the 2nd element in L1 times each element in
> L2 so that I get another list [1,0,1] and also have the 2nd element in L3 +
> each element in L4, so that I get [4,3,2]. This would go on for each
> element and I would end up with 4 more lists [3,0,3], [3,2,1], [2,0,2],
> [2,1,0]. I would then take the numbers from my lists and have the
> computer write the coefficients along with the exponents: 2x^5 + 0x^4
> + 2x^3 + x^4 +0x^3+x^2+3x^3+0x^2 +3x+ 2x^2+0x+2. I would
> then have to get rid of those terms with zero coefficients and combine like
> terms. Is this crazy or what?
Make one function that adds two functions, by adding together their
coefficients. Then you can have the multiplication function generate the
polynomials that have to be added together.
> How could I accomplish this?
> Like I told you before, this is all new to me, but I'm really interested in
> finding out how this complex task can be accomplished in Python. Can
> you help?</DIV>
I'm going to explain how I would do this with OO (Object Oriented)
programming. You see, a polynomial here is a bit of data, with a nontrivial
representation (like your lists, but there may be other ways), and a bunch
of related functions (for adding them together, evaluating them, printing
them as a string, and so on). This kind of "rich data" usually means that
making an object is a good idea.
This is the first version:
class Polynomial:
def __init__(self, coefficients):
self.coefficients = coefficients
def degree(self):
return len(self.coefficients)-1
def coefficient(self, n):
# n is the degree of the term of which we need the coefficient
# it has to be an integer >= 0
if (type(n) != type(1)) or n < 0:
raise ValueError, "n has to be an integer >= 0"
if n >= len(self.coefficients):
# All coefficients greater than the ones in the list are 0
return 0
else:
return self.coefficients[n]
That's a simple first version. You could use it like this (suppose it is in
a file polynomial.py):
>>> import polynomial
>>> p = polynomial.Polynomial([1,2,3,4])
>>> p.degree()
3 # It's a third degree polynomial
>>> p.coefficient(3)
4 # coefficient of x^3 is 4
You'd want to add methods for turning it into a string, evaluating it,
adding them together and multiplying:
def __str__(self):
terms = []
for i in range(len(self.coefficients)):
if i == 0:
# If i == 0, the term is a constant
terms.append(str(self.coefficients[0]))
elif i == 1:
# If i == 1, it's simply coefficient*x
terms.append(str(self.coefficients[0])+"x")
else:
# Otherwise use the ^ thing
terms.append(str(self.coefficients[0])+"x^"+str(i))
terms.reverse() # Customary to list highest degree first
return "+".join(terms) # Put '+' between the terms
def eval(self, x):
result = 0L
for i in range(len(self.coefficients)):
result += self.coefficients[i]*(x**i)
return result
def add(self, other):
"""Return a new polynomial that is the sum of self and other"""
# The length of the needed list is the maximum of their two degrees,
# plus one.
length = max(self.degree(), other.degree()) + 1
# Initialize a list that length
result = [0] * length
# Fill it with the sums
for i in range(len(result)):
result[i] = self.coefficient(i) + other.coefficient(i)
# Construct new polynomial and return it
return Polynomial(result)
def multiply_single_term(self, coefficient, degree):
# First the simple form of multiplication: by a single term.
# If the polynomial is multiplied by, say, 4x^3, we added three
# zeroes to the beginning of the list of coefficients, and multiply
# the rest by 4.
# Construct a new polynomial that is a copy of this one
result = Polynomial(self.coefficients[:])
# Add zeroes
result.coefficients[0:0] = [0]*degree
# Multiply by coefficient
for i in range(len(result.coefficients)):
result.coefficients *= coefficient
return result
def multiply(self, other):
# Start with a zero polynomial, add to it self multiplied by each
# term of other. Return the result.
result = Polynomial([])
for term in range(other.degree()+1):
result=result.add(self.multiply_single_term(other.coefficient(term),
term))
return result
Hmm, this has become rather longer than I expected. No time left to explain
the details, argh. Ask about whatever is unclear, like what OO is and how to
use this....
(of course, nothing tested, as usual)
--
Remco Gerlich