Lagrange interpolation pseudo-code

Lagrange interpolation fits the unique polynomial of degree ≤ n−1 through n points (xᵢ, yᵢ):

P(x) = Σ yᵢ · Lᵢ(x),     Lᵢ(x) = Π (x − xⱼ)/(xᵢ − xⱼ)     (j ≠ i)

Pseudo-code

START
  INPUT n                         // number of data points
  FOR i = 0 TO n−1
      INPUT x[i], y[i]
  END FOR
  INPUT xp                        // point where value is needed

  sum = 0
  FOR i = 0 TO n−1
      L = 1                       // Lagrange basis term Li(xp)
      FOR j = 0 TO n−1
          IF j ≠ i THEN
              L = L * (xp − x[j]) / (x[i] − x[j])
          END IF
      END FOR
      sum = sum + y[i] * L
  END FOR

  PRINT "Interpolated value at", xp, "=", sum
STOP

Notes

• The x values must be distinct (otherwise division by zero), but they need not be equally spaced or sorted.
• Two nested loops, so the time taken is O(n²); the value changes completely if a new point is added, so every term must be recomputed.
• Quick check: if xp equals some x[k], the term for i = k has L = 1 and all others have L = 0, so the output is y[k].

Equivalent C code

#include <stdio.h>
int main() {
    int n, i, j;
    float x[20], y[20], xp, sum = 0, L;
    printf("Enter n: ");           scanf("%d", &n);
    printf("Enter x and y:\n");
    for (i = 0; i < n; i++) scanf("%f %f", &x[i], &y[i]);
    printf("Enter xp: ");          scanf("%f", &xp);
    for (i = 0; i < n; i++) {
        L = 1;
        for (j = 0; j < n; j++)
            if (j != i) L *= (xp - x[j]) / (x[i] - x[j]);
        sum += y[i] * L;
    }
    printf("f(%.4f) = %.4f\n", xp, sum);
    return 0;
}