This post was written as a follow-up on Hillel Wayne’s newsletter: You can cheat a test suite with a big enough polynomial [1] which you should definitely check first.
Indeed, his post refers to a well-known mathematical problem: interpolation. More specifically, he is interpolating using polynomials. It turns out there is a great tool for polynomial interpolation: Lagrange polynomial.
Lagrange interpolation
Given inputs and outputs , we want to build a polynomial such that .
The Lagrange interpolating polynomial is built as follows:
This way, it is clear that the property stands:
Okay, but how do we define as a polynomial?
Hopefully, we know the roots of this polynomial. And we also have some information on how to normalize it (). The following meets these two requirements1:
Thus, we can entirely compute our Lagrange interpolating polynomial! But, wait… Hillel’s newsletter was considering functions of multiple variables.
Higher dimensions
Using straightforward Lagrange interpolation
Given input vectors and output scalars2 , we want to build a polynomial such that . Beware, s are now vectors, so is a multivariate polynomial now. Using the idea of Lagrange interpolation, we can come up with:
Simple, right? …right?
The thing is we no longer have a polynomial. Alright, let’s apply a quick fix:
Ta-daaa! We somehow won, but at what cost? Well, now this is a multivariate polynomial, but we lost an important property along the way: this polynomial is not of minimal degree.
A more sophisticated Lagrange interpolation
Hopefully, we are not the first ones working on this problem: see the paper by Kamron Saniee [2] to do some clean work, which I won’t do today.
Experimental results
Now, time to code and compute some polynomials!
You can check the source code here. The code itself is ugly as hell, but it does work (and will be forgotten forever after this hopefully).
I used the same set of inputs as in Hillel’s post:
inputs = [(1, 2, 3), (4, 2, 2), (1, 1, 1), (3, 5, 4)]
outputs = [max(g) for g in inputs]
p = lagrange(inputs, outputs)
print(p.eval(inputs[0]))
# Should be 3, outputs 2.9999999999999254
print(p.eval(inputs[1]))
# Should be 4, outputs 3.9999999999998908
print(p.eval(inputs[2]))
# Should be 1, outputs 0.9999999999999887
print(p.eval(inputs[3]))
# Should be 5, outputs 4.999999999999659
print(p)
# This one I'm not writing here
Yeay! Apart from floating point errors, we’re good! So, we found a polynomial which appears to be equivalent to the max
function if looking only at this 4-test-long test suite.
What is this polynomial, you may ask?
The polynomial (click to unfold)
We are pretty far from minimal degree here. But this just adds more chaos to the gag I guess.
References
- [1] newsletter by Hillel Wayne: You can cheat a test suite with a big enough polynomial
- [2] Saniee, Kamron. (2008). A Simple Expression for Multivariate Lagrange Interpolation. SIAM Undergraduate Research Online. 1. 10.1137/08S010025.