A polynomial is a mathematical function of the form
The highest-power exponent \(n\) is called the degree of the polynomial. For instance, \(p(x) = 7 x^{4} - 2\) is a polynomial of degree 4. A constant function like \(p(x) = 6\) is a polynomial of degree 0, a linear function like \(p(x) = 7x - 5\) is a polynomial of degree 1, and the unique zero polynomial \(p(x) = 0\) is defined to have degree \(-1\).
I have created a Polynomial class in the source file polynomial.scala. It provides a constructor that takes an array of integers (we only allow integer coefficients), with the first element being the constant coefficient, the second one being the linear coefficient, and so on.
You can compile the Polynomial class and then use it interactively:
> fsc polynomial.scala
> scala
Welcome to Scala version 2.9.1.final
scala> val p = new Polynomial(Array(1, 2, 0, 3))
p: Polynomial = 3 * X^3 + 2 * X + 1
scala> p.degree
res1: Int = 3
scala> for (i <- 0 to 6)
| println(p.coeff(i))
1
2
0
3
0
0
0
Note that it is okay to call p.coeff(i) with an index \(i\) that
is larger than the degree—the result is simply zero.
My class provides methods to add and multiply polynomials, and to compute powers of polynomials:
scala> val q = new Polynomial(Array(0, 1, 0, -1, 0, 1)) q: Polynomial = X^5 - X^3 + X scala> q + p res2: Polynomial = X^5 + 2 * X^3 + 3 * X + 1 scala> q - p res3: Polynomial = X^5 - 4 * X^3 - X - 1 scala> q * p res4: Polynomial = 3 * X^8 - X^6 + X^5 + X^4 - X^3 + 2 * X^2 + X scala> q^2 res5: Polynomial = X^10 - 2 * X^8 + 3 * X^6 - 2 * X^4 + X^2(If you are taking the course "Programming Principles", you should recognize the algorithm I use for computing the power of a polynomial.)
We can evaluate a polynomial for an arbitrary value of \(x\):
scala> p res6: Polynomial = 3 * X^3 + 2 * X + 1 scala> p(0) res7: Double = 1.0 scala> p(0.5) res8: Double = 2.375 scala> p(2.5) res9: Double = 52.875
Here is another nice trick: Using the keyword implicit, we can define a conversion from integers to Polynomial objects, and then write expressions like 3 * p - 5:
scala> 3 * p <console>:9: error: overloaded method * cannot be applied to (Polynomial) scala> implicit def intToPolynomial(n: Int): Polynomial = new Polynomial(Array(n)) intToPolynomial: (n: Int)Polynomial scala> 3 * p res10: Polynomial = 9 * X^3 + 6 * X + 3 scala> 3 * p - 5 res11: Polynomial = 9 * X^3 + 6 * X - 2
If we define X as the polynomial \(p(x) = x\), we can now build any polynomial we want using addition, subtraction, and powers. Be careful, however: In Scala, the priority of the ^ operator is lower than +, -, and *, so you have to use parentheses:
scala> val X = new Polynomial(Array(0, 1)) X: Polynomial = X scala> val r = 5 * (X^8) - (X^6) + 7 * (X^3) -1 r: Polynomial = 5 * X^8 - X^6 + 7 * X^3 - 1 scala> (X + 1)^8 res12: Polynomial = X^8 + 8 * X^7 + 28 * X^6 + 56 * X^5 + 70 * X^4 + 56 * X^3 + 28 * X^2 + 8 * X + 1
I have made a test suite checkpoly.scala that checks most methods of the Polynomial class. (You can read about ScalaTest test suites in the tutorial.)
> fsc polynomial.scala > fsc checkpoly.scala > scala org.scalatest.run PolynomialCheckSuite Run starting. Expected test count is: 6 PolynomialCheckSuite: - creating polynomials - addition and subtraction - multiplication and power - creating polynomials using X - evaluation - derivatives Run completed in 172 milliseconds. Total number of tests run: 6 Suites: completed 1, aborted 0 Tests: succeeded 6, failed 0, canceled 0, ignored 0, pending 0 All tests passed.
Your first task is to create a companion object to make it nicer to construct polynomials. Note that the ordering of arguments is from highest degree to lowest degree, as common in mathematics. (You only need to provide these constructors for degree zero to four.)
The Polynomial.linear function makes a linear polynomial of the form \(p(x) = a x + b\), and Polynomial.X should be predefined as the polynomial \(p(x) = x\).
scala> val X = Polynomial.X X: Polynomial = X scala> val p = Polynomial.linear(3, 5) p: Polynomial = 3 * X + 5 scala> val const = Polynomial(3) const: Polynomial = 3 scala> val lin = Polynomial(3, -7) lin: Polynomial = 3 * X - 7 scala> val quad = Polynomial(2, 3, -7) quad: Polynomial = 2 * X^2 + 3 * X - 7 scala> val cubic = Polynomial(-1, 2, 3, -7) cubic: Polynomial = -X^3 + 2 * X^2 + 3 * X - 7 scala> val p4 = Polynomial(9, -1, 2, 3, -7) p4: Polynomial = 9 * X^4 - X^3 + 2 * X^2 + 3 * X - 7Add tests to PolynomialCheckSuite for all new methods.
Add a method derivative to the Polynomial class, which returns a new polynomial representing the derivative of \(p\), like this:
scala> val r = 5 * (X^8) - (X^6) + 7 * (X^3) -1 r: Polynomial = 5 * X^8 - X^6 + 7 * X^3 - 1 scala> r.derivative res1: Polynomial = 40 * X^7 - 6 * X^5 + 21 * X^2 scala> r.derivative.derivative res2: Polynomial = 280 * X^6 - 30 * X^4 + 42 * X scala> r.derivative.derivative.derivative res3: Polynomial = 1680 * X^5 - 120 * X^3 + 42Add tests to PolynomialCheckSuite to test the derivative method.
If you have a look at the method apply which evaluates the polynomial for a given \(x\), you will find that it computes the power \(x^{i}\) for every term of the polynomial.
A better way to evaluate a polynomial is Horner's rule, which is as follows:
Add a division operator / to the Polynomial class. If p = q * r, then p/q must return the polynomial r. If \(p\) is not a multiple of \(r\), then the method should throw an ArithmeticException.
scala> val p = 5 * (X^8) - 7 * (X^5) - (X^4) + 4 * (X^2) - 1 p: Polynomial = 5 * X^8 - 7 * X^5 - X^4 + 4 * X^2 - 1 scala> val r = p / (X-1) r: Polynomial = 5 * X^7 + 5 * X^6 + 5 * X^5 - 2 * X^4 - 3 * X^3 - 3 * X^2 + X + 1 scala> r * (X-1) res1: Polynomial = 5 * X^8 - 7 * X^5 - X^4 + 4 * X^2 - 1
Add tests to PolynomialCheckSuite to test division.
Hint: You can divide polynomials exactly like you divide long integers by hand.
You need to submit both polynomials.scala and checkpoly.scala!