TL;DR: I need a way to create a polynomial from some given coordinates in a such a way to allow for iterating over its coefficients and optionally to even allow evaluating the polynomial at any given point
I am working on creating a crude algorithm in JavaScript/TypeScript for KZG commitments and one of the steps for this algorithm includes multiplying coefficients of the polynomial constructed for some given string with the Structured Reference String (SRS) raised to the appropriate power.
Anyway, that basically means I need to iterate over all of the coefficients of this newly constructed polynomial (at least that is what I think I need to do, I am open to suggestions here).
I am trying to achieve the following:
I am stuck at step 4).
I know how to construct a polynomial from a given string in JS/TS using Lagrange Interpolation, but I am having difficulties extracting its coefficients, which I need to be able to multiply them with SRS.
Below is my Lagrange Interpolation algorithm - note that it can solve 5) for me, but I do not see an obvious way to get the exact coefficients from it:
type Point = { x: number; y: number };
// The function basically reconstructs the whole Lagrange Polynomial each time
// it needs to evaluate it at some given point `newX`, which is a problem as
// there is no way to extract the coefficients.
function lagrangeInterpolation(points: Point[], newX: number) {
const n = points.length;
let newY = 0;
for (let i = 0; i < n; i++) {
let { x, y } = points[i];
let term = y;
for (let j = 0; j < n; j++) {
if (i !== j) {
let { x: xj } = points[j];
term = (term * (newX - xj)) / (x - xj);
}
}
newY = newY + term;
}
return newY;
}
Maybe another interpolation algorithm would allow to calculate the exact coefficients?
I could not find any JS libraries that solve this exact problem. The closest ones I could find were the following, but they are still not applicable to solving this problem:
You could use the matrix-based method described by @guest at Coefficients of Lagrange polynomials.
For that you'd need to have a function that calculates the determinant of a matrix. For this you could use the Gaussian elimination method.
Here is an implementation:
function determinant(mat) { // Gaussian elimination method
const n = mat.length;
let det = 1;
for (let r = 0; r < n; r++) {
let r2 = r;
while (!mat[r2][r]) {
r2++;
if (r2 >= mat.length) return 0;
}
const row = mat[r2];
if (r2 !== r) { // Swap rows
mat[r2] = mat[r];
mat[r] = row;
det = -det;
}
let div = row[r];
if (!div) return 0;
det *= div;
for (let c = r; c < n; c++) row[c] /= div;
for (let r2 = r+1; r2 < n; r2++) {
const row2 = mat[r2];
const mul = row2[r];
for (let c = r; c < n; c++) {
row2[c] -= mul * row[c];
}
}
}
return det;
}
// Similar to https://math.stackexchange.com/a/3253643/341715
function lagrangeInterpolationCoefficients(points) {
const lagrangeDet = (j) => determinant(points.map((_, i) =>
points.map(([a, b]) => i == j ? b : a ** i)
));
const denom = lagrangeDet(-1);
return points.map((_, j) => lagrangeDet(j) / denom);
}
const coefficientsToFunction = (coefficients) =>
x => coefficients.reduce((sum, coeff, i) => sum + coeff * x**i, 0);
// Simple (imperfect) rendering of the polynomial:
const coefficientsToString = (coefficients) =>
coefficients.map((coeff, i) => `${coeff}x^${i}`)
.reverse().join(" + ")
.replace(/x\^0|\^1\b|\b0x\^\d+/g, "")
.replaceAll("+ -", "- ");
// Demo
const points = [[0, -1], [1, 1], [3, 8], [4, 10]];
const coefficients = lagrangeInterpolationCoefficients(points);
console.log("f(x) =", coefficientsToString(coefficients));
const f = coefficientsToFunction(coefficients);
// Verify that the created function returns
// the correct results for the given points
for (const [x, y] of points) {
console.log({x, y, "f(x)": f(x)});
}