 |
COSC 4P41
Assignment 1
|
 |
Instructor: Michael
Winter, Office
J323, Office Hours: Tue & Wed, 10:00am - noon, email: [email protected]
Due: Sep 28 @ 1:00pm
Late: Sep 30 @ 1:00pm
Roots of a polynomial
An expression p(x) of the form an*xn+an-1*xn-1+...+a1*x+a0
is called
- an integer polynomial if a0,...,an are
integers,
- a normalized integer polynomial if a0,...,an-1
are integers and an=1,
- a rational polynomial if a0,...,an are
rational numbers.
A root r of a polynomial p(x) is a value so that p(r) = an*rn+an-1*rn-1+...+a1*r+a0=0.
The following theorem can be shown:
Theorem:
If p(x) is a normalized integer polynomial, and r is a rational root of
p(x) then r is an integer and r is a divider (positive or negative) of a0.
As an example for the theorem above consider the normalized integer
polynomial x4-4x3-348x2-288x+13824. A
rational root of this polynomial has to be an integer and within the
dividers of 13824, which are
±1, ±2, ±3, ±4, ±6, ±8, ±9, ±12, ±16, ±18, ±24, ±27, ±32, ±36, ±48,
±54, ±64, ±72, ±96, ±108, ±128, ±144, ±192, ±216, ±256, ±288, ±384,
±432, ±512, ±576, ±768, ±864, ±1152, ±1536, ±1728, ±2304, ±3456, ±4608,
±6912, ±13824.
It turns out (by testing) that -8 and 6 are the rational roots of p(x).
In this assignment normalized integer polynomials will be represented
by the Haskell type
type NormIntPolynomial = [Integer]
with the convention that the list stores the
coefficients a0,...,an-1 in this order, i.e., the
polynomial in the
example above is represented by the list [13824,-288,-348,-4].
Implement the
following functions:
- dividers :: Integer -> [Integer] computing the list
of (positive and negative) dividers of the parameter,
- valueNIP :: NormIntPolynomial -> Integer -> Integer
computing the value p(r) for the given normalized integer polynomial p
and the parameter r,
- rootsNIP :: NormIntPolynomial -> [Integer]>
computing the list of rational roots of a normalized integer polynomial (In the special case a0=0, and, hence, every number divides a0, you should compute the roots of the polynomial a1,...,an-1, which are together with 0 the roots of the original polynomial).
Let p(x)=an*xn+an-1*xn-1+...+a1*x+a0
be an arbitrary integer polynomial (not necessarily normalized). If we
multiply p(x) by ann-1
we get q(x)=(an*x)n+an-1*(an*x)n-1+(an-2*an)*(an*x)n-2+...+(a1*ann-2)*(an*x)+(a0*ann-1).
This polynomial can be consider as a normalized integer polynomial
q(y)=yn+an-1*yn-1+(an-2*an)*yn-2+...+(a1*ann-2)*y+(a0*ann-1)
by substituting y=an*x. Consequently, the rational roots of
p(x) are the roots of q(y) divided by an.
As an example consider the integer polynomial p(x)
= 12x4 - 4x3 - 29x2 - 2x + 8. If we
multiply this polynomial by 123 we get (12x)4 -
4(12x)3 - 348(12x)2 - 288(12x) + 13824 and hence
q(y) = y4 - 4y3 - 348y2 - 288y +
13824. So the rational roots of p(x) are the rational roots of q(y) (-8
and 6) divided by 12 giving
-2/3 and 1/2.
Integer polynomials will be represented by the Haskell type
type IntPolynomial = [Integer]
with the convention that the list stores the coefficients a0,...,an-1,an
in this order, i.e., the polynomial in the
example above is represented by the list [8,-2,-29,-4,12].
Implement the
following functions:
- toNIP :: IntPolynomial -> NormIntPolynomial
transforming an integer polynomial into an normalized integer
polynomial as described above,
- rootsIP :: IntPolynomial -> [Rational] computing the
list of rational roots of an integer polynomial.
A rational polynomial can be transformed into an equivalent integer
polynomial (with the same roots) by multiplying it by the least common
multiplier (lcm) of the dominators of a0,...,an.
As an example consider the rational polynomial p(x) = 2x4
- 2/3 x3 - 29/6 x2 - 1/3 x + 4/3. If we multiply
this polynomial by lcm(3,6) = 6 we get 12x4 - 4x3
- 29x2 - 2x + 8 so that p(x) has the rational roots -2/3 and
1/2.
Rational polynomials will be represented by the Haskell type
type RationalPolynomial = [Rational]
with the convention that the list stores the coefficients a0,...,an-1,an
in this order, i.e., the polynomial in the
example above is represented by the list [4 % 3,-1 % 3,-29 % 6,-2
% 3,2 % 1]. Implement the
following functions:
- toIP :: RationalPolynomial -> IntPolynomial
transforming a rational polynomial into an integer polynomial as
described above,
- rootsRP :: RationalPolynomial -> [Rational] computing
the list of rational roots of a rational polynomial.
COSC Home Page
COSC 4P41
Home Page
© M. Winter, 2009