大きな数の文字列乗算｜コードで実践

大きな数の文字列乗算

このレッスンで分かること

大きな数の演算は「筆算をなぞる + キャリーを忘れない」これだけ

計算量は O(m * n)

通常、プログラミング言語の整数型には上限があります

大きな数の文字列乗算とは

整数型では桁あふれする大きな数を「文字列のまま筆算」で乗算する。桁ごとに掛け算してキャリーを上げる古典問題。

通常、プログラミング言語の整数型には上限があります。Python は任意精度整数を扱えますが、JavaScript の Number は 2^53 - 1 で精度が崩れ、Java の int は 2^31 - 1 までです。それを超える 超大きな数 の掛け算をしたいときは、文字列のまま筆算する必要があります。これは多倍長演算 (big integer arithmetic) の基本パターンです。

面接や競技プログラミングでも頻出する古典問題で、「文字列を配列のように扱って桁ごとに処理する」感覚を養うのに最適です。

大きすぎる数は文字列に。桁ごとに筆算と同じ手順を踏めば、整数型の桁あふれを気にせず計算できる。

筆算のおさらい

小学校で習った筆算を思い出してみましょう。123 * 45 を計算するとき、

5 * 123 = 615
4 * 123 = 492 (1 桁左シフト)
615 + 4920 = 5535

このように、各桁同士を掛けて足し合わせます。プログラムでも同じことをします。文字列 num1 の i 番目と num2 の j 番目を掛けると、答えは i + j + 1 の位置に入ります (キャリーは i + j へ)。

アルゴリズムの概要

配列 result を len(num1) + len(num2) の長さで 0 初期化し、桁ごとに掛け算を蓄積します。

diagram (will load when visible)

図解付きの動き

例えば "12" * "34" を計算するなら次のように進みます。

配列 [0, 0, 0, 0]
i = 1, j = 1: 2 * 4 = 8、result[3] += 8 → [0, 0, 0, 8]
i = 1, j = 0: 2 * 3 = 6、result[2] += 6 → [0, 0, 6, 8]
i = 0, j = 1: 1 * 4 = 4、result[2] += 4 → [0, 0, 10, 8]、キャリー: result[1] += 1 → [0, 1, 0, 8]
i = 0, j = 0: 1 * 3 = 3、result[1] += 3 → [0, 4, 0, 8]

最後に先頭の 0 を取り除いて文字列化すると "408"。12 * 34 = 408 で正解です。

Python の実装

Python

def stringMultiply(num1, num2):
    if num1 == "0" or num2 == "0":
        return "0"
    m, n = len(num1), len(num2)
    result = [0] * (m + n)
    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            mul = int(num1[i]) * int(num2[j])
            p1, p2 = i + j, i + j + 1
            total = mul + result[p2]
            result[p2] = total % 10
            result[p1] += total // 10
    s = "".join(str(d) for d in result).lstrip("0")
    return s if s else "0"

int(num1[i]) で文字を数字に、% 10 と // 10 でキャリー処理。最後の lstrip("0") で先頭の 0 を取り除いています。

JavaScript の実装

JavaScript

function stringMultiply(num1, num2) {
  if (num1 === "0" || num2 === "0") return "0";
  const m = num1.length, n = num2.length;
  const result = new Array(m + n).fill(0);
  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      const mul = Number(num1[i]) * Number(num2[j]);
      const p1 = i + j, p2 = i + j + 1;
      const total = mul + result[p2];
      result[p2] = total % 10;
      result[p1] += Math.floor(total / 10);
    }
  }
  let s = result.join("").replace(/^0+/, "");
  return s === "" ? "0" : s;
}

計算量は O(m * n)。num1 と num2 の長さの積に比例します。

キャリーの扱い

result[p1] += total / 10 の時点で result[p1] が 10 を超えても問題ありません。なぜなら、次の i の反復で result[p1] を result[p2] に加算するときにまた % 10 と / 10 が走るためです。最終的には全桁が 0-9 に収まります。

大きな数の演算は「筆算をなぞる + キャリーを忘れない」これだけ。配列の添字を間違えないことが最大の壁。

添字をきれいに整理するには、紙にペンで桁の位置を書いて手を動かす。慣れるまでは紙が最強のデバッガ。

よくある間違い

1 つ目は 添字の +1 を間違えてキャリーの位置がずれるケースです。i + j と i + j + 1 を取り違えると最終結果が全然違ってきます。

2 つ目は 先頭の 0 を取り除き忘れる ケースです。"0123" のような戻り値になってしまいます。lstrip("0") や replace(/^0+/, "") で対応します。

3 つ目は 両方が "0" のときの早期 return を忘れることです。lstrip("0") で全部消えて空文字になります。

やってみよう

"123" * "456" を手計算と比較する。56088 になるはず。
"999" * "999" を計算する。998001 になる。これは int32 でも収まるが、"99999999999999" * "99999999999999" だと収まらない。
文字列のまま加算をする stringAdd も書いてみる (応用課題)。

よくある質問

Q. このトピックは実務でどう役立ちますか？

A. DB のクエリ最適化、API 設計、データ構造の選択など、設計判断の根拠になります。表面的にライブラリを使うだけでなく「なぜそれが速いのか」を理解できると、性能問題を未然に防げます。コーディング面接でも頻出のテーマです。

Q. 計算量はどう求めれば良いですか？

A. ループのネストごとに掛け算する、再帰なら漸化式から解く、というのが基本です。Big-O 表記は定数倍と低次の項を無視するため、n の指数（n²、n log n など）に注目してください。最悪・平均・最良の 3 つを意識すると説得力が増します。

Q. 覚えるべき定番アルゴリズムは何ですか？

A. 二分探索、クイックソート/マージソート、BFS/DFS、ダイクストラ、DP の基本問題（フィボナッチ・ナップサック）が必修です。これらを「白紙から書ける」状態にすると、応用問題が一気に解けるようになります。

次のレッスン

次は アナグラムグルーピング で、文字列をソートしてキー化し、アナグラム同士をグルーピングする手法を学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

文字列乗算の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. 文字列乗算とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

大きな数の文字列乗算