如何在JS/TS中从字符串生成多项式并遍历其系数？

需求 #

• 核心：从给定XY坐标点生成多项式，需支持遍历系数，可选支持任意点求值
• 背景：实现KZG承诺简易算法，需将多项式系数与对应幂次的SRS相乘
• 流程：
  1. 接收输入字符串
  2. 转换为XY坐标点
  3. 生成经过点的多项式
  4. 遍历多项式系数（当前瓶颈）
  5. （可选）指定点求值

现有问题 #

当前使用的拉格朗日插值仅能实现求值，无法直接提取系数。试过两个相关库均不满足需求：

• polynomial：无返回系数的内置方法，也无法处理拉格朗日形式的多项式以提取系数
• nerdamer-prime：虽可简化多项式，但不保证按x的幂次排序，难以提取对应系数，也无内置提取功能

解决方案：直接求解多项式系数 #

要直接获取多项式系数，最直观的方法是解线性方程组：n个点对应n-1次多项式 ( P(x) = a_0 + a_1x + ... + a_{n-1}x^{n-1} )，将每个点代入后得到n个线性方程，解方程组即可得到按幂次排列的系数数组。

TypeScript实现代码 #

type Point = { x: number; y: number };

// 解线性方程组得到多项式系数数组 [a0, a1, ..., a(n-1)]，对应 P(x) = a0 + a1x + ... + a(n-1)x^(n-1)
function getPolynomialCoefficients(points: Point[]): number[] {
  const n = points.length;
  // 构造增广矩阵：每行是 [x^0, x^1, ..., x^(n-1), y]
  const matrix: number[][] = points.map(({ x, y }) => {
    const row: number[] = [];
    for (let i = 0; i < n; i++) {
      row.push(Math.pow(x, i));
    }
    row.push(y);
    return row;
  });

  // 高斯消元法解方程组
  for (let col = 0; col < n; col++) {
    // 找主元行（取绝对值最大的行，避免精度误差）
    let pivotRow = col;
    for (let row = col; row < n; row++) {
      if (Math.abs(matrix[row][col]) > Math.abs(matrix[pivotRow][col])) {
        pivotRow = row;
      }
    }
    // 交换主元行与当前行
    [matrix[col], matrix[pivotRow]] = [matrix[pivotRow], matrix[col]];

    // 归一化主元行
    const pivotVal = matrix[col][col];
    for (let j = col; j <= n; j++) {
      matrix[col][j] /= pivotVal;
    }

    // 消去其他行的当前列
    for (let row = 0; row < n; row++) {
      if (row !== col && matrix[row][col] !== 0) {
        const factor = matrix[row][col];
        for (let j = col; j <= n; j++) {
          matrix[row][j] -= factor * matrix[col][j];
        }
      }
    }
  }

  // 提取系数（每行最后一个元素即为对应幂次的系数）
  return matrix.map(row => row[n]);
}

// 可选：用系数数组在指定点求值（霍纳法则优化效率）
function evaluatePolynomial(coefficients: number[], x: number): number {
  let result = 0;
  for (let i = coefficients.length - 1; i >= 0; i--) {
    result = result * x + coefficients[i];
  }
  return result;
}

使用示例 #

// 测试坐标点
const testPoints: Point[] = [
  { x: 0, y: 2 },
  { x: 1, y: 5 },
  { x: 2, y: 10 }
];

// 获取系数数组
const coeffs = getPolynomialCoefficients(testPoints);
console.log("多项式系数:", coeffs); // 输出 [2, 2, 1]，对应 P(x) = 2 + 2x + x²

// 求值测试
console.log("P(3) =", evaluatePolynomial(coeffs, 3)); // 输出 17

补充说明 #

• 系数数组按x的幂次从小到大排列，直接遍历即可与对应幂次的SRS相乘
• 高斯消元法时间复杂度为O(n³)，适合KZG场景中的小规模多项式；若需处理大规模点集，可改用牛顿插值法（O(n²)）优化
• 求值函数采用霍纳法则，比直接调用Math.pow效率更高

内容的提问来源于stack exchange，提问作者Nesh