Lagrange Algorithm Implementation for Ocaml (help pls)

Learning
1

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

image

2

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
3

Understandable, thank you very much

4

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

5

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

6

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!