## Lagrange Interpolation

Sounds scary? Probably more than it should.

Lagrange Interpolation is a method to find an equation passing through a given set of points.

## Lagrange Interpolation Formula

Given a set of data points $( (x_0, y_0), (x_1, y_1), \dots, (x_n, y_n) )$, the goal is to find a polynomial $P(x)$ such that:

$$P(x_i) = y_i \quad \text{for each } i.$$

The Lagrange polynomial is expressed as:

$$P(x) = \sum_{i=0}^{n} y_i \cdot \ell_i(x)$$

where $\ell_i(x)$ are the Lagrange basis polynomials defined as:

$$\ell_i(x) = \prod_{\substack{0 \leq j \leq n \\ j \neq i}} \frac{x - x_j}{x_i - x_j}$$

This may seem like a lot of jargon if you're not from a mathematics background. I've added a simple Rust code that executes Lagrange Interpolation below.

## Example of how it is used in zkSnarks

Without going to much in depth of how zkSNARKS work(that is a topic for another day), there is a step which results in the formation of Rank One Constrained System(R1CS). If you don't know what this is, treat it as a black box for now.

R1CS looks like a set of vectors. The next step involves taking these vectors and producing polynomials from it. This form is called QAP(Quadratic Arithmetic Program). This is where **Lagrange Interpolation** comes in to save the day. It takes the points we get form the R1CS vector and transforms them to polynomials.

## Time to do some Math

Let us take some points: $$(0,0) ,(2,4), (4,16)$$
On using the Lagrange Interpolation formula:

$$P(x) = 0 \times \frac{(x - 2)}{(0 - 2)} \frac{(x - 4)}{(0 - 4)} + 4 \times \frac{(x - 0)}{(2 - 0)} \frac{(x - 4)}{(2 - 4)} + 16 \times \frac{(x - 0)}{(4 - 0)} \frac{(x - 2)}{(4 - 2)}$$

$$P(x) = 4 \times \frac{x^2 (x - 4)}{-2} + 16 \times \frac{x^4 (x- 2)}{2}$$

$$P(x) = -x(x - 4) + 2x(x - 2)$$

$$P(x) = -x^2 + 4x + 2x^2 - 4x$$

$$P(x) = x^2$$

We can confirm our result:
$$P(0) = 0 => (0,0)$$
$$P(2) = 4 => ((2,4)$$
$$P(4) = 16 => (4,16)$$


## Enough math, time for some code

This is a simple `Rust` script which uses `Lagrange Interpolation` to find the eqaution from a given set of points and find other values on that equation`

We'll be using the same Points as mentioned in the math example above.

fn lagrange_interpolation(x_values: &[f64], y_values: &[f64], x: f64) -> f64 {
    let n = x_values.len();
    let mut result = 0.0;

    for i in 0..n {
        let mut term = y_values[i];

        for j in 0..n {
            if i != j {
                term *= (x - x_values[j]) / (x_values[i] - x_values[j]);
            }
        }

        result += term;
    }

    result
}

fn main() {
    let x_values = vec![0.0, 2.0, 4.0];
    let y_values = vec![0.0, 4.0, 16.0];

    for x in 0..5 {
        let px = lagrange_interpolation(&x_values, &y_values, x as f64);
        println!("P({}) = {}", x, px);
    }
}

The resulting output on running `cargo.run`:

P(0) = 0
P(1) = 1
P(2) = 4
P(3) = 9
P(4) = 16