Rational Polynomial Interpolation Explanation

In this task you'll be given a set of N points (x1,y1),…,(xN,yN) with distinct xi values and your task is to interpolate a polynomial through these points. If you know what Lagrange interpolation is you can skip this section.

The goal of a polynomial interpolation is to construct the (unique) polynomial p(x) with degree N-1 (for higher degrees there are infinite solutions) for which p(xi) = yi for all i = 1…N. One way to do so is to construct N Lagrange basis polynomials and form a linear combination. Such a basis polynomial is defined as follows:

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;

As you can see if you evaluate li at the points x1,…,xi-1
,xi+1,…
,xN it is 0 by construction and 1 for xi, multiplying by yi will only change the value at xi and set it to yi. Now having N such polynomials that are 0 in every point except one we can simply add them up and get the desired result. So the final solution would be:

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;

Challenge


the input will consist of N data points in any reasonable format (list of tuples, Points, a set etc.)
the coordinates will all be of integer value
the output will be a polynomial in any reasonable format: list of coefficients, Polynomial object etc.
the output has to be exact - meaning that some solutions will have rational coefficients
formatting doesn't matter (2/2 instead of 1 or 1 % 2 for 1/2 etc.) as long as it's reasonable
you won't have to handle invalid inputs (for example empty inputs or input where x coordinates are repeated)


Testcases

These examples list the coefficients in decreasing order (for example [1,0,0] corresponds to the polynomial x2):

[(0,42)] -&gt; [42]
[(0,3),(-18,9),(0,17)] -&gt; undefined (you don't have to handle such cases)
[(-1,1),(0,0),(1,1)] -&gt; [1,0,0]
[(101,-42),(0,12),(-84,3),(1,12)] -&gt; [-4911/222351500, -10116/3269875, 692799/222351500, 12]
Pari/GP, 14 bytes

polinterpolate


Takes two lists [x1, ..., xn] and [y1, ..., yn] as input. Outputs a polynomial.

Try it online!



Pari/GP, 37 bytes, without built-in

f(x,y)=y/matrix(#x,#x,i,j,x[j]^(i-1))


Takes two lists [x1, ..., xn] and [y1, ..., yn] as input. Outputs a list of coefficients.

Try it online!