# 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:

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:

## 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)] -> 
[(0,3),(-18,9),(0,17)] -> undefined (you don't have to handle such cases)
[(-1,1),(0,0),(1,1)] -> [1,0,0]
[(101,-42),(0,12),(-84,3),(1,12)] -> [-4911/222351500, -10116/3269875, 692799/222351500, 12]

• – ბიმო Dec 21 '17 at 12:01

# 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!

# Enlist, 25 bytes

Ḣ‡ḟ¹‡,€-÷_Ḣ¥€§æc/§₱W€\$↙·Ṫ


Try it online!

Monadic link takes an array of length 2 (e.g., [[101,0,-84,1],[-42,12,3,12]]) as input. The first element of the array is list of x value, the second is list of y value. Output as list of coefficient in increasing degree.

Because @HyperNeutrino forgot to wrap numbers in rational wrapper if it is evaluated in list, (Try it online!) the argument must be hardcoded in the code.

The ↙ is necessary because HyperNeutrino make some mistake in implementing · I don't know (or is this a feature? Not sure)

Equivalent Mathematica code:

Expand[ Table[
Times @@ ((z - #)/(xi - #) & /@ DeleteCases[x, xi])
, {xi, x}] . y]


Try it online!

where x and y are list of coordinates. This prints the polynomial.

What Enlist have for this challenge:

• Built in rational number support
• Convolution æc (my feature request)
• If you need a rational number version of Jelly, M might be worth a shot – caird coinheringaahing Dec 23 '17 at 0:47