Re: [Tutor] Multiplication of polynomials
by Sheila King other posts by this author
Apr 29 2001 1:26PM messages near this date
Re: [Tutor] Multiplication of polynomials
|
[Tutor] popen
Juliet,
PLEASE set your mail settings, to compose in plain text.
On Sun, 29 Apr 2001 13:48:34 -0500, "Julieta Rangel"
<julieta_rangel@[...].com> wrote about [Tutor] Multiplication of
polynomials:
:<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. Let
s say the user wants to multiply two polynomials. Once the user enters the amount of p
olynomials that will be multiplying, the computer would have to ask the degree of the polyno
mials, 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?&nb
sp; In one list I would store all the coefficients
:and in another the exponents of the expression.
This is a worthy problem. I might suggest, first implementing polynomial
addition, rather than multiplication. Do the addition first, and once you've
got that, try multiplication. Another worthy problem, is evaluating a single
polynomial for a given value of x. Well, maybe that one is a bit easy. Still,
worthy trying for a new, non-programmer.
As to your problem, you really don't need to store the exponents of the
polynomial in a second list. You could infer the exponent from the placement
of the polynomial's coefficient in the list.
For example, you could store
2x^4+x^2-3x+5 as
[2, 0, 1, -3, 5]
or, you might want to store it in reverse order, as
[5, -3, 1, 0, 2]
The advantage of the second representation is that, if
coeff = [5, -3, 1, 0, 2]
then coeff[4]
refers to the coefficient of the x^4 term, and
coeff[1] refers to the coefficient of the x^1 term, and so on.
You should store zeros for the coefficients equal to zero.
Really, you might want to make a class called Polynomial and give it methods
like ValueAtX and Add and Multiply.
: 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 li
ke (L 3) [3,2,1,0] and (L 4)[2,1,0]. I would then have the first element in L1 times ea
ch 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 hav
e 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? How could I accomplish this? Like I told yo
u before, this is all new to me, but I'm really interested in finding out how this complex t
ask can be accomplished in Python. Can you help?</DIV>
In order to multiply two polynomials, you would need to take each coefficient
in the one list and multiply it be each coefficient in the other list.
So, your suggested problem
(2x^3 + x^2 + 3x + 2) * (x^2 + 1)
might look like this:
p1 = [2, 3, 1, 2]
p2 = [1, 0, 1]
I would note, that since you are multiplying a 3rd degree polynomial by a 2nd
degree one, that your result should be fifth degree. You could find this out
by doing
len(p1)-1 added to len(p2)-1
then create a new list to store the results of your multiplication. Give it
length of 5 and initialize all spots to zero. Let's call this new list for the
result, p3.
Now create a loop to go through each element of p1.
Start with p1[0] and multiply it by p2[0] and add the result to p3[0].
Now multiply p1[0] with p2[1] and add the result to p3[1].
Now multiply p1[0] with p2[2] and add the result to p3[2].
All done with p1[0]. Now the loop moves to p1[1].
Multiply p1[1] with p2[0] and add the result to p3[1].
Now multiply p1[1] with p2[1] and add the result to p3[2].
Now multiply p1[1] with p2[2] and add the result to p3[3].
Note, that the indices indicate the exponent on your variable. So, p1[1] is an
x^1 coefficient and p2[2] is an x^2 coefficient, so the result needs to be an
x^3 coefficient, so add that result to p3[3].
Proceed on to p1[2] and p1[3] in the same manner. So, you have a loop on p1,
and inside that loop is another loop that iterates over all the indices in p2.
I hope this is helpful.
--
Sheila King
http://www.thinkspot.net/sheila/
http://www.k12groups.org/
_______________________________________________
Tutor maillist - Tutor@[...].org
http://mail.python.org/mailman/listinfo/tutor
Thread:
Julieta Rangel
Remco Gerlich
Benoit Dupire
Sheila King
|
