Q: Integer polynomial interpolation (or fast select case) Let x in {10, 37, 96, 104} set.
Let f(x) a "select case" function:
int f1(int x) {
    switch(x) {
    case 10: return 3;
    case 37: return 1;
    case 96: return 0;
    case 104: return 1;
    }
    assert(...);
}

Then, we can avoid conditional jumps writing f(x) as a "integer polynomial" like
int f2(int x) {
    // P(x) = (x - 70)^2 / 1000
    int q = x - 70;
    return (q * q) >> 10;
}

In some cases (still including mul operations) would f2 better than f1 (eg. large conditional evaluations).
Are there methods to find P(x) from a switch injection?
Thank you very much!

A: I suggest you start reading the Wikipedia page about  Polynomial Interpolation, if you do not know how to calculate the interpolation polynomial.
Note, that not all calculation methods are suitable for practical application, because of numerical issues (e.g. divisions in the Lagrange version). I am confident that you shold be able to find a libary providing this functionality. Note that the construction will take some time too, hence this makes only sence if your function will be called quite frequently.
Be aware that integer function values and integer points of support do not imply integer coefficients for your polynomial! Thus, in the general case, you will require O(n) floating point operations, and finally a round toward the nearest integer. It may depend on your input wether the interpolation method is reliable and faster than the approach using switch.
Further, I want to propose a differnt solution, assuming that n is rather large. Why dont you put your entries (the pairs (10,3), (37,1), (96,0), (104,1) for your example) inside a serchtree (e.g. std::map in C++ or SortedDictionary in C#)? Thus, your query cost would reduce from linear to O(log n)!
