BFE.devでのAI解答例 - JavaScript コーディング問題
128. BigDecimal 掛け算

解法:

この問題を、手で解くように解決することができます。

手で乗算する際、最も単純な方法は、掛けられる値に数値を掛けていくことです。 この問題においては、ここで文言を "行" として使用しています。 各行の右側に、それまでの行の結果を示す十進桁があります。

以下のステップに分けて手動で解き、それをコードに逆推できます。

Step 1: 値を右端に揃える

1 1 2 3 4 5 6 7 8 7 6 5 4 3 2 3 4 5 6 7 8 9 // > 被乗数
          *   1 2 3 4 5 6 7 8 8 7 6 5 4 3 2 3 4 5 6 // > 掛ける数
----------------------------------------------

Step 2: 各行の掛け算を行う

                        6 4 8 2 4 4 6 3 6 4        // 1: 9×6
                      7 4 0 8 7 0 3 7 7 2 4          // 2: 9×5 + 7×6
                    8 7 2 0 0 7 0 9 8 7 9            // 3: 9×4 + 7×5 + 2×6
                  9 9 8 7 6 1 1 7 3 1 8              // 4: 9×3 + 7×4 + 2×5 + 3×6
                1 2 0 4 4 4 3 3 9 9 8                // 5: 9×2 + 7×3 + 2×4 + 3×5 + 4×6
              1 2 6 2 6 2 0 5 3 5 5                  // 6: 9×1 + 7×2 + 2×3 + 3×4 + 4×5 + 5×6
----------------------------------------------
            1 3 8 6 9 8 3 6 7 3 2 0 5 3 0 9 9 2 4 4 2 7 8 4

Step 3: 手動で算出の結果を検証する

この方法は、しっかりと検証されたアルゴリズムです。 合計桁数が $m + n$ である場合、2つの数を乗算する際に実行される基本操作の数（つまり、何度掛け算を実行する必要があるか）は $O(mn)$ です。

最終的なコードは以下のようになります。

function multiply(num1, num2) {
  const isNegative = num1[0] === "-" && num2[0] === "-" ? false : num1[0] === "-" || num2[0] === "-"; // 符号の形式を確認する
  num1 = num1.replace("-", "");
  num2 = num2.replace("-", "");

  let result = new Array(num1.length + num2.length).fill(0); // 合計桁数がm + nである場合の配列を作成する

  // 掛け算を行う
  for (let i = num1.length - 1; i >= 0; i--) {
    for (let j = num2.length - 1; j >= 0; j--) { // 2つの数を乗算する中で基本操作の数の計算を行う
      let product = num1[i] * num2[j];
      let pos1 = i + j; // 結果が置かれる位置
      let pos2 = i + j + 1; // 掛ける位置

      let sum = product + result[pos2];

      result[pos1] += Math.floor(sum / 10); // 繰り上がり（桁上がり）を取得する。
      result[pos2] = sum % 10;
    }
  }

  // 配列の左端に連結して置く
  const resString = result.join("").replace(/^0+(?!\.|$)/, "");

  return isNegative ? "-" + resString : resString || "0";
}