文字列掛け算アルゴリズムの詳細解析

🎯 アルゴリズム概要

このアルゴリズムは筆算の掛け算を模倣して、文字列として表現された大きな数の掛け算を実現します。

入力検証
→
配列初期化
→
桁ごと掛け算
→
繰り上がり処理
→
文字列変換

📊 具体例での動作解析：123 × 456

Step 1: 初期化

num1 = "123" (長さ 3), num2 = "456" (長さ 3)

結果配列サイズ: 3 + 3 = 6

Step 2: 配列のインデックス構造

0
1
2
3
4
5

result[0] result[1] result[2] result[3] result[4] result[5]

初期値: [0, 0, 0, 0, 0, 0]

Step 3: 筆算の掛け算処理

1 2 3
× 4 5 6
─────────

各桁の掛け算とインデックス計算:

i=2, j=2: 3×6=18 → p1=4, p2=5 → result[5]=8, result[4]=1 i=2, j=1: 3×5=15 → p1=3, p2=4 → sum=15+1=16 → result[4]=6, result[3]=1 i=2, j=0: 3×4=12 → p1=2, p2=3 → sum=12+1=13 → result[3]=3, result[2]=1 i=1, j=2: 2×6=12 → p1=3, p2=4 → sum=12+6=18 → result[4]=8, result[3]=4 i=1, j=1: 2×5=10 → p1=2, p2=3 → sum=10+4=14 → result[3]=4, result[2]=2 i=1, j=0: 2×4=8 → p1=1, p2=2 → sum=8+2=10 → result[2]=0, result[1]=1 i=0, j=2: 1×6=6 → p1=2, p2=3 → sum=6+4=10 → result[3]=0, result[2]=1 i=0, j=1: 1×5=5 → p1=1, p2=2 → sum=5+1=6 → result[2]=6, result[1]=1 i=0, j=0: 1×4=4 → p1=0, p2=1 → sum=4+1=5 → result[1]=5, result[0]=0

Step 4: 最終結果配列

0
5
6
0
8
8

先頭の0を除去: "56088"

🔍 詳細な処理フロー

1. 特殊ケース処理

if (num1 === "0" || num2 === "0") { return "0"; // 早期終了でパフォーマンス向上 }

2. インデックス計算ロジック

重要: 筆算での桁の位置を配列インデックスにマッピング

p1 = i + j // 上位桁（繰り上がり先） p2 = i + j + 1 // 下位桁（現在の結果） 例: i=1, j=2 の場合 p1 = 1 + 2 = 3 p2 = 1 + 2 + 1 = 4

3. 繰り上がり処理

const sum = mul + result[p2]; // 現在の値に加算 result[p2] = sum % 10; // 1桁のみ保持 result[p1] += Math.floor(sum / 10); // 繰り上がりを加算

⚡ パフォーマンス分析

計算量

時間計算量: O(m × n)
空間計算量: O(m + n)

最適化ポイント:

🎮 インタラクティブデモ

実際に試してみましょう！

×

🔧 TypeScript実装の利点

型安全性による利点: