pattern-solver

Polynomial Pattern Solver

I came up with this idea when working on my homework for a course. We had a question where we had to find the closed form for a recursive function. I ended up using a rough version of this algorithm to solve that question.


When I first came up with this, I thought I had stumbled on something new, but I was foolish to assume anything mathematic hasn't already been discovered and well researched. After I finished coding this, I googled it and turns out Newton basically already came up with this however many years ago. This was disappointing to find out, but at least I created a version on my own.


Implementation

This was coded in javascript and can be found here. There are 3 steps in this algorithm, which we'll go over now.


Find the degree of the polynomial

I'm not entirely sure why this works, but I came across a neat pattern useful in calculating the degree of a polynomial pattern. If you get the difference between each value in a list, and repeat this process on the values until you're left with a list of the same values, you'll find that the number of repetitions is equal to the degree of the polynomial pattern those values belong to.

// example pattern
 1 2 4 7 11     0th degree
  1 2 3 4       1st degree
   1 1 1        2nd degree (list is all same value, so pattern belongs to 2nd degree polynomial)


Create a template polynomial

Now that we have the degree of the polynomial, we can use a general form equation. For example, let's say that we were solving the equation of a polynomial with degree 2. We would know that the polynomial has to follow the form ax^2 + bx + c = y. Now we need to solve for a, b, c. This will come in the third step.


Find coefficients

With our template polynomial, we can substitute our coordinates into the template polynomial to find a, b, c. We do this for each coordinate in our input list, until we have N equations. We can then arrange these equations into a matrix, and solve it by RREFing it. The solutions to this matrix will be the coefficients for the polynomial equation that matches our input coordinates, and we are now finished. Note that in order for the matrix to have a unique solution, N has to be greater than the degree of the polynomial.

// example with same pattern
   a(1)^2 + b(1) + c = 1     >>    a +    b + c = 1    >>    [ 1 1 1 |  1]
   a(2)^2 + b(2) + c = 2     >>    4a +  2b + c = 2    >>    [ 4 2 1 |  2]
   a(3)^2 + b(3) + c = 4     >>    9a +  3b + c = 4    >>    [ 9 3 1 |  4]
   a(4)^2 + b(4) + c = 7     >>    16a + 4b + c = 7    >>    [16 4 1 |  7]
   a(5)^2 + b(5) + c = 11    >>    25a + 5b + c = 11   >>    [25 5 1 | 11]


For this project, as a bit of a sidetrack idea, I actually tried to code my own RREF solver. I got it working with a bunch of test inputs, and released it to NPM (the package name "rref" was already taken, so I cheekily called it "better-rref"). After a week of that being up and me working on this script, I found out my RREF solver doesn't handle fractions very well. I had taken precautions by using a Big Decimal library but somehow my process was still too inefficient, and I was getting rounding errors on tricky input numbers. Begrudgingly, I had to scrap my solver and use the "rref" package that already exists. I took down my solver from NPM because of the rounding errors that I can't be bothered to fix, but it's still available here for anyone that wants to take a look.


Observations

When I first created this algorithm, I was worried that the result it would give for a list of input coordinates might be one of many, like how if you're given two coordinates, there are infinite quadratic curves that can fit those two coordinates. However, the more I thought about it, I realized that fundamentally if you have enough coordinates, it will belong to a SINGLE polynomial equation of degree equal to the number of points minus one. If you have only 2 coordinate points, there will only be one line that those points belong to. If you have more than 2 points, and they all line up, there will still only be a single line equation that those points belong to. Likewise with any number of points, there will be a polynomial equation that is the ONLY match for them.


Limitations