A calculator for polynomials

In this project we build a new type with useful operators.

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.kt. It provides a constructor that takes a variable number of arguments for the coefficients (we only allow integer coefficients), with the first element being the constant coefficient, the second one being the linear coefficient, and so on. There is also a constructor that takes these coefficients as an array.

You can compile the Polynomial class and then use it interactively:

$ kt polynomial.kt
$ ktc
Welcome to Kotlin version 1.0.4 (JRE 1.8.0_91)
Type :help for help, :quit for quit
>>> val p = Polynomial(1, 2, 0, 3)
>>> p.degree()
3
>>> p
3 * X^3 + 2 * X + 1
>>> for (i in 0 .. 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:

>>> val q = Polynomial(0, 1, 0, -1, 0, 1)
>>> q
X^5 - X^3 + X
>>> q + p
X^5 + 2 * X^3 + 3 * X + 1
>>> q - p
X^5 - 4 * X^3 - X - 1
>>> q * p
3 * X^8 - X^6 + X^5 + X^4 - X^3 + 2 * X^2 + X
>>> q.pow(2)
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\):

>>> p
3 * X^3 + 2 * X + 1
>>> p(0.0)
1.0
>>> p(0.5)
2.375
>>> p(2.5)
52.875

Here is another nice trick: I have defined an extension function for the type Int to define multiplications of integers and polynomials, so we can write expressions like 3 * p - 5:

>>> 3 * p
9 * X^3 + 6 * X + 3
>>> 3 * p - 5
9 * X^3 + 6 * X - 2

I have also predefined X as the polynomial \(p(x) = x\), we can now build any polynomial we want using addition, subtraction, and powers:

>>> val r = 5 * X.pow(8) - X.pow(6) + 7 * X.pow(3) - 1
>>> r
5 * X^8 - X^6 + 7 * X^3 - 1
>>> (X+1).pow(8)
X^8 + 8 * X^7 + 28 * X^6 + 56 * X^5 + 70 * X^4 + 56 * X^3 + 28 * X^2 + 8 * X + 1

Polynomial test suite

I have made a test suite polytest.kt that checks most methods of the Polynomial class. (You can read about unit testing in the tutorial.)

$ ktc polytest.kt 
$ kttest PolynomialTest
JUnit version 4.12
.......
Time: 0.024

OK (7 tests)

Derivatives

Your first task is to add a method derivative to the Polynomial class, which returns a new polynomial representing the derivative of \(p\). Start by adding this line to the class Polynomial to declare the new method:

  fun derivative(): Polynomial = TODO()

By using the function TODO, I have declared the method but postponed its implementation. Now uncomment the tests in the derivatives section of polytest.kt.

Compile both files again and run the test suite:

$ ktc polynomial.kt 
$ ktc polytest.kt 
$ kttest PolynomialTest
JUnit version 4.12
.......E
Time: 0.027
There was 1 failure:
1) derivatives(PolynomialTest)
kotlin.NotImplementedError: An operation is not implemented.
	at Polynomial.derivative(polynomial.kt:108)
	at PolynomialTest.derivatives(polytest.kt:93)

FAILURES!!!
Tests run: 7,  Failures: 1

Not surprisingly, the derivatives tests fail. Implement the derivatives method until all tests pass. Does the test suite test all the cases? If not, add more tests to the derivatives section.

Here are some examples:

>>> val r = 5 * X.pow(8) - X.pow(6) + 7 * X.pow(3) - 1
>>> r.derivative()
40 * X^7 - 6 * X^5 + 21 * X^2
>>> r.derivative().derivative()
280 * X^6 - 30 * X^4 + 42 * X
>>> r.derivative().derivative().derivative()
1680 * X^5 - 120 * X^3 + 42

Horner's rule

If you have a look at the method invoke 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:

Change the invoke method to use Horner's rule.

Polynomial division

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.

>>> val r = 3 * X.pow(4) - 7 * X.pow(2) - X + 7
>>> val q = 8 * X.pow(3) - 4 * X - 9
>>> val p = r * q
>>> p
24 * X^7 - 68 * X^5 - 35 * X^4 + 84 * X^3 + 67 * X^2 - 19 * X - 63
>>> p / q
3 * X^4 - 7 * X^2 - X + 7
>>> p / r
8 * X^3 - 4 * X - 9

Add a section to polytest.kt to test polynomial division.

Hint: You can divide polynomials exactly like you divide long integers by hand.

You need to submit both polynomials.kt and polytest.kt!