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

-

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.

-
thanks. indeed, this question comes from a theoretical framework, by investigating some Gram matrices over Cameron Martin space. this will become one stage in a learning algorithm – Troy McClure Dec 29 '12 at 15:08