What interpolation to choose for 1 million points?

Question

Mathematics

It is necessary to construct a function by points and then analyze it. There can be up to several million points. What interpolation is better to choose in terms of efficiency and speed of finding the function value at a certain point in the program? Lagrange interpolation is not suitable, because there, the degree of f-ii increases with an increase in the number of points.
While considering interpolation using the Fourier expansion.
Maybe there are some other types of interpolation that are more suitable for my task?

Answer 1

With so many points, a linear one is enough for you.
In general, cubic splines are usually used for interpolation.
Well, or if you roughly imagine the type of function, you can pull a lot of parametric fit.

Answer 2

Cubic splines - I think it will be optimal.
There, the search is linearly done:

//*************************************************************************/
//Подсчет значения интерполянты в заданной точке
//*************************************************************************/
double Interpolate(double x)
{
  //double result;
  int i=0;

  while (KnotArray[i].x < x)
    i++;
  i--;
  return Coef[i][0] + Coef[i][1]*(x-KnotArray[i].x) + Coef[i][2]*powf((x-KnotArray[i].x),2) + Coef[i][3]*powf((x-KnotArray[i].x),3); 

}