[JS] 거듭 제곱

1. 빠른 거듭 제곱

/**
 * @param {number} base
 * @param {number} exp
 * @returns {number}
 */
function fastPow(base, exp) {
  let res = 1;

  while (exp) {
    if (exp & 1) res *= base;

    base *= base;
    exp >>= 1;
  }

  return res;
}

2. 행렬의 거듭 제곱

/**
 * @param {number[][]} a 
 * @param {number[][]} b 
 * @returns {number[][]}
 */
function matrixMutiply(a, b) {
  const rl = a.length;
  const cl = b[0].length;
  const res = [...Array(rl)].map(() => Array(cl).fill(0));

  a.forEach((row, i) =>
    row.forEach((val1, j) =>
      b[j].forEach((val2, z) => {
        res[i][z] = res[i][z] + val1 * val2;
      })
    )
  );

  return res;
}

/**
 * @param {number[][]} matrix 
 * @param {number} exp 
 * @returns 
 */
function matrixPow(matrix, exp) {
  let base = matrix;
  let res = undefined;

  while (exp) {
    if (exp & 1) res = res ? matrixMutiply(res, base) : base;

    base = matrixMutiply(base, base);
    exp >>= 1;
  }

  return res;
}