Efficient Integer Interpolation

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.

-
Can you clarify what you mean faster than Lagrange? It seems quite straightforward to write out the polynomial representation. Do you mean that, if we were given $x_i=i$, then we should simply have written down $f(x) = x$ directly, instead of numerous multiplcations? –  Calvin Lin Dec 29 '12 at 14:41
I mean, computationally efficient way. Like $O(n)$. But Lagrange is $O(nlog^2n)$, and even this with Fourier transforms (taken from cs.iastate.edu/~cs577/handouts/interpolate.pdf) –  Troy McClure Dec 29 '12 at 14:43
The fastest way is the pointwise definition $f(x_i) := i$. You need to be more specific; do you ned a polynomial answer? A smooth, increasing function? Are you trying to write a computer program to compute the function $x_i \to i$ (and only care about those input values)? If the latter, then your question is probably best asked on a programming site, but the standard answer would be "use a hash table". –  Hurkyl Dec 29 '12 at 15:09
it should be a smooth function, its purpose will be to interpolate for $x$ that does not appear in the sample set, but does not break its bounds (i.e. bigger than the minimum and smaller than the maximum). my question is purely mathematical, I'm composing an article about a new algorithm –  Troy McClure Dec 29 '12 at 15:12

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.

-