快速幂和矩阵快速幂，求解斐波那契数列和泰波纳契数列

快速幂

a 的 n 次方，即 n 个 a 相乘- 如果 n 是偶数，可以拆分为 n / 2 的 a² 相乘

• 如果 n 是奇数，可以拆分为 n / 2 的 a² 相乘，再乘以 a

代码

const pow = (a, n) => {
  let r = 1
  while (n) {
    if (n & 1) r *= a 
    n >>= 1
    a *= a
  }
  return r
}

矩阵快速幂

斐波那契数列

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给定 n ，请计算 F(n) 。

代码

var fib = function(n) {
  return new Fibonacci(n).ans
};
class Fibonacci {
  constructor (n) {
    this.ans = n >= 1 ? this.pow([[1, 1], [1, 0]], n - 1)[0][0] : 0
  }

  pow (a, n)  {
    let r = [[1, 0], [0, 1]]
    while (n) {
      if (n & 1) r = this.multiply(r, a)
      n >>= 1
      a = this.multiply(a, a)
    }
    return r
  }

  multiply (a, b) { // a 与 b 都是 n * n 矩阵
    const n = a.length
    const r = Array.from({length: n}, _ => new Int32Array(n))
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        for (let k = 0; k < n; k++) {
          r[i][j] += a[i][k] * b[k][j]
        }
      }
    }
    return r
  }
}

泰波纳契数列

泰波那契序列 Tn 定义如下： T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2 给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

代码

var tribonacci = function(n) {
  return new Tribonacci(n).ans
};

class Tribonacci {
  constructor (n) {
    this.ans = this.pow([[1, 1, 1], [1, 0, 0], [0, 1, 0]], n)[0][2]
  }

  pow (a, n) {
    let r = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
    while (n) {
      if (n & 1) r = this.multiply(r, a)
      n >>= 1
      a = this.multiply(a, a)
    }
    return r
  }

  multiply (a, b) {
    const n = a.length
    const r = Array.from({length: n}, _ => new Int32Array(n))
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        for (let k = 0; k < n; k++) {
          r[i][j] += a[i][k] * b[k][j]
        }
      }
    }
    return r
  }
}