Efficient Integer Interpolation

Question

Let $n\in\mathbb N$. Let $\{{x_i\}}_{i=1}^{n}$ be $n$ positive real numbers. Can one think of a fast way to construct a function $f$ such that $f(x_i)=i$?

(i.e. $f$ maps $\{{x_i\}}_{i=1}^{n}$ to ${1,2,3,...,n}$. At least a way faster than Lagrange, Newton or Trigonometric-Lagrange interpolation)

Note: you can assume that $\{{x_i\}}_{i=1}^{n}$ is increasing.

Answer 1

A simple and fast function would be the function $f(y)$ as defined by

• Do a binary search on the list of $x$'s to find the $i$ such that $x_i \leq y \leq x_{i+1}$
• Return $i + \frac{y - x_i}{x_{i+1} - x_i}$

This won't be differentiable at each $x_i$. Similar ideas can be used to make differentiable functions, twice differentiable functions, or even infinitely differentiable functions: just replace the linear function with something suitable.

The function

$$ g(x) = \begin{cases} 0 & x \leq 0 \\ e^{-1/x^2} & x > 0 \end{cases} $$

is a classic building block if you really need infinitely differentiable.

Answer 2

Since you seem to be trying to do a reverse lookup on your values, I would be wary of any function that needs irrational or even non-integer coefficients. Computer roundoff will make it uncertain whether you are actually at one of your values because you will not get a true integer as a result. If you just want to know which two values you are between then that may be enough.

A single function which accounts for all your values is also likely to not have other desirable properties for interpolation, such as relatively smooth derivatives or even monotonicity. Unless this is a one-time setup and you can spend a lot of time inspecting the properties of the resulting function, I would stick with piecewise functions to interpolate on.