# Lagrange Algorithm Implementation for Ocaml (help pls)

The task is to implement the function lagrange : (float * float) list → (float → float) that returns the interpolated polynomial L

i have been thinking about it for a while but i cant seem to write a correct implementation, any kind of help will be appriciated The usual answer is: write an incorrect implementation, and ask for help fixing it.
I’m assuming that you don’t need a particularly efficient implementation, so just implement the formula given above as it is.
I can give you a few tips though:

• Split the work into small parts, with a function for each small part. In your case, it looks like a good split would be a function for the term of the product, a function for `l_j`, and a function for `L`. But you can do it another way if you prefer.
• I’m assuming that the `(float * float) list` input corresponds to a list of points `(x_i, y_i)`. But lists aren’t very good for indexed access, so I would advise converting the input to one or several arrays at the beginning, and write code that only manipulates arrays.

If you don’t know how to write OCaml code at all, there are a few tutorials available, for example this page has various materials adapted for various contexts. Although it looks like you may have been given this assignment as part of a course on OCaml; in which case your teacher likely gave you some reference materials already.

2 Likes

Understandable, thank you very much

By the way, how could i iterate through that kind of term when two types of indexes are displayed? I mean for the product

If you look at the formula, you’ll notice that only `k` varies from one term of the product to another. The index `j` denotes which `l_j` you’re computing, it doesn’t change during the computation of the product.

If you actually had two different indices to iterate on, you would do it using nested loops:

``````for j = ... to ... do
for k = ... to ... do
...
done
done
``````

But that’s not the case here, you only need one loop for the product and one loop for the sum. (If you didn’t follow my suggestion about splitting the code into several functions, you could end up with the product loop nested inside the sum loop though).

Bit delayed but I took a stab at an implementation for the problem. This looks like a homework assignment so I won’t post my work but here’s an outline of how I approached it:

• A top-level function named `get_lagrange_interp` with the signature `(float * float) list -> float -> float`—this is the function you described
Inner values:
• An array `x_a` and an array `y_a` which have the same data as in the input `(float * float) list` but split up (as @vlaviron mentioned, arrays are faster than lists for indexed access)
• A function `basis_num` with the signature `int -> float -> float` which returns the value of a numerator term for a basis polynomial given its index (argument 1), evaluated at a certain x coordinate (argument 2)—i.e., the product of all (x - x_k) terms for a given l_j, calculated with some x.
• A function `basis_denom` with the signature `int -> float` which returns the value of a denominator term for a basis polynomial given its index (the only argument)—i.e., the product of all (x_j - x_k) terms for a given l_j.
• A function `l_j` with the signature `int -> float -> float` which returns the value of a basis polynomial given its index (argument 1) evaluated at a certain x coordinate (argument 2).

I was able to get a working result with this approach. If you’re looking to do this more functionally, I’d take a look at the standard library array functions, especially `Array.fold_left`. Good luck!