基于JavaScript矩阵实现计算百万项斐波那契数的优化困惑

我需要计算n大于100万的第n项斐波那契数，现有程序能运行但速度极慢。为优化性能，我新增了矩阵平方相关函数，但因数值过大，无法确定需要执行多少次矩阵平方操作。核心问题出在matrixSolution函数的循环次数判断上，目前无法确定正确的循环次数。

现有实现代码 #

function multiplyByResult(result, baseMatrix) {
  //[[0,1],[2,3]] [[0,1],[2,3 ]]
  return {
    0: baseMatrix[0] * result[0] + baseMatrix[1] * result[2],
    1: baseMatrix[0] * result[1] + baseMatrix[1] * result[3],
    2: baseMatrix[2] * result[0] + baseMatrix[3] * result[2],
    3: baseMatrix[2] * result[1] + baseMatrix[3] * result[3],
  };
}

function matrixSquare(matrix) {
  //[[0,1],[2,3]] [[0,1],[2,3 ]]
  return {
    0: matrix[0] * matrix[0] + matrix[1] * matrix[2],
    1: matrix[0] * matrix[1] + matrix[1] * matrix[3],
    2: matrix[2] * matrix[0] + matrix[3] * matrix[2],
    3: matrix[2] * matrix[1] + matrix[3] * matrix[3],
  };
}

function matrixMultiplication(baseMatrix, mulitplierMatrix) {
  //[[0],[2]]
  return {
    0:
      baseMatrix[0] * mulitplierMatrix[0] + baseMatrix[1] * mulitplierMatrix[2],
    2:
      baseMatrix[2] * mulitplierMatrix[0] + baseMatrix[3] * mulitplierMatrix[2],
  };
}

function matrixSolution(n) {
  // [[0,1],[1,1]]
  const baseMatrix = { 0: 0n, 1: 1n, 2: 1n, 3: 1n };
  //[[0],[1]]
  const mulitplierMatrix = { 0: 0n, 2: 1n };

  let result = matrixSquare(baseMatrix);

  if (n < 1000000)
    for (let i = 2; i < n; i++) {
      result = multiplyByResult(result, baseMatrix);
    }
  else {
    let count = 1;
    while (count < Math.log10(n)) {
      result = matrixSquare(result);
      count++;
    }
  }

  return matrixMultiplication(result, mulitplierMatrix);
}

function fib(n) {
  if (n === 0) return 0n;
  if (n < 2 && n > 0) return 1n;

  const count = n > 0 ? n : n * -1;
  const res = matrixSolution(count);

  if (n < 0 && n % 2 === 0) return res[0] * -1n;
  return res[0];
}

问题分析与修正方案 #

核心问题

原来的matrixSolution函数中，用Math.log10(n)决定矩阵平方次数完全错误——矩阵快速幂的核心是通过二进制分解指数n来决定何时平方、何时将矩阵乘入结果，而非基于对数的固定次数。此外，针对n<1e6的循环方案时间复杂度为O(n)，对于1e6级别的n依然很慢，完全没必要保留。

修正后的实现

我们需要实现标准的矩阵快速幂逻辑，时间复杂度为O(logn)，无论n是10还是1e7都能高效运行：

// 2x2矩阵乘法：matrixA * matrixB
function multiplyMatrix(matrixA, matrixB) {
  return {
    0: matrixA[0] * matrixB[0] + matrixA[1] * matrixB[2],
    1: matrixA[0] * matrixB[1] + matrixA[1] * matrixB[3],
    2: matrixA[2] * matrixB[0] + matrixA[3] * matrixB[2],
    3: matrixA[2] * matrixB[1] + matrixA[3] * matrixB[3],
  };
}

// 2x2矩阵平方
function matrixSquare(matrix) {
  return multiplyMatrix(matrix, matrix);
}

// 矩阵快速幂：计算matrix的power次方
function matrixPower(matrix, power) {
  // 初始化结果为单位矩阵（矩阵乘法的单位元，类似数字乘法中的1）
  let result = { 0: 1n, 1: 0n, 2: 0n, 3: 1n };
  let currentMatrix = { ...matrix };
  
  while (power > 0) {
    // 如果当前power的二进制最低位是1，将当前矩阵乘入结果
    if (power % 2 === 1) {
      result = multiplyMatrix(result, currentMatrix);
    }
    // 矩阵平方，power右移一位（相当于除以2）
    currentMatrix = matrixSquare(currentMatrix);
    power = Math.floor(power / 2);
  }
  
  return result;
}

function matrixSolution(n) {
  // 斐波那契递推对应的变换矩阵：[[0,1],[1,1]]
  const baseMatrix = { 0: 0n, 1: 1n, 2: 1n, 3: 1n };
  // 初始向量：[F(0), F(1)]^T = [0, 1]^T
  const multiplierMatrix = { 0: 0n, 2: 1n };
  
  // 计算baseMatrix的(n-1)次方，因为F(n) = baseMatrix^(n-1) * [F(0); F(1)]
  const poweredMatrix = matrixPower(baseMatrix, n - 1);
  
  // 矩阵乘向量
  return {
    0: poweredMatrix[0] * multiplierMatrix[0] + poweredMatrix[1] * multiplierMatrix[2],
    2: poweredMatrix[2] * multiplierMatrix[0] + poweredMatrix[3] * multiplierMatrix[2],
  };
}

function fib(n) {
  if (n === 0) return 0n;
  if (n > 0 && n < 2) return 1n;
  
  const absN = Math.abs(n);
  const res = matrixSolution(absN);
  
  // 负斐波那契数的规则：F(-n) = (-1)^(n+1) * F(n)
  if (n < 0) {
    return absN % 2 === 0 ? -res[0] : res[0];
  }
  
  return res[0];
}

关键说明

1. 矩阵快速幂逻辑：通过二进制分解指数，每次将指数除以2，矩阵平方；当指数为奇数时，将当前矩阵乘入结果。这样只需要O(logn)次矩阵乘法，对于n=1e6来说，只需要约20次操作，效率远超原有的循环方案。
2. 单位矩阵初始化：结果矩阵初始化为单位矩阵，确保第一次乘法时结果正确。
3. 统一处理所有n值：移除了原有的分支判断，无论n大小都用快速幂处理，代码更简洁且效率一致。
4. 负斐波那契数修正：原逻辑正确，补充注释明确规则，便于理解。

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