大きな数の文字列乗算
桁が増えた瞬間に、答えが静かに変わる
言語が用意している整数には上限があります。JavaScript の Number は、ある大きさを超えると 1 を足しても増えません。
JavaScript
console.log(9007199254740992 + 1); // 9007199254740992例外は出ません。黙って間違った値を返します。金額や識別子の計算でこれが起きると、原因を突き止めるまでにかなり時間を溶かします。上限を超える大きさを扱うなら、数として持つのをやめて、文字列のまま桁ごとに計算します。
どのマスに入るかは、掛けた 2 桁の位置で決まる
小学校の筆算をそのままなぞります。23 × 14 を、位ごとに分けて書き出します。
3 × 4 = 12— 一の位へ3 × 1 = 3— 十の位へ2 × 4 = 8— 十の位へ2 × 1 = 2— 百の位へ
規則が見えます。右から数えた位置どうしを足すと、答えのどの位に入るかが決まるのです。右から 0 番目と 0 番目を掛けた 12 は一の位へ。0 番目と 1 番目を掛けた 3 と 8 はどちらも十の位へ。1 番目と 1 番目を掛けた 2 は百の位へ。
だから答えを入れる箱は、2 つの数の桁数を足した数だけ用意しておけば足ります。それを超える位に値が入ることはありません。左から数えると位置が数の長さに依存してずれるので、必ず右から数えてください。
くり上がりは後回しでよい
上の例で、一の位の箱には 12 が入っています。1 桁に収まっていません。ここで慌てて直さなくても大丈夫です。すべて配り終えてから、右の箱から順に 10 で割った商を左へ渡していけば、最後には全部が 0 から 9 に収まります。
Python
d = [3, 12] # 左が十の位、右が一の位。まだ 10 以上が入っている
d[0] += d[1] // 10 # くり上がりを左へ
d[1] = d[1] % 10
print(d) # [4, 2] -> "42"23 × 14 で同じことをすると、一の位が 2 でくり上がりが 1、十の位が 3 + 8 + 1 = 12 なので 2 でくり上がりが 1、百の位が 2 + 1 = 3 となり、322 になります。筆算の答えと一致しました。
掛け算の回数は、2 つの数の桁数の積です。10 桁どうしなら 100 回。桁数が増えても手に負えなくなるほどではありません。位置の計算さえ合っていれば、桁がいくつあっても同じ手順で通ります。
添字を間違えたときは、画面をにらむより紙に書くほうが早く直せます。23 × 14 くらいの小さな例で、箱の並びと位の対応を書き出してみてください。
よくある間違い
箱の左端に残った 0 を消し忘れることです。23 × 14 の箱は 4 つ用意しますが答えは 3 桁なので、そのままだと "0322" になります。逆に消しすぎると、答えが 0 のときに何も残らず空の文字列になります。0 になる場合だけは別扱いにしてください。
要件
- 整数型 (int, Number, long, BigInteger 等) に直接変換せず、桁ごとに筆算する
- 戻り値は積を表す文字列。先頭に 0 が並ばないこと ("0" 単独は OK)
- 片方でも "0" なら結果は "0" を返す
入出力例
stringMultiply("12", "34") → "408"
stringMultiply("123", "456") → "56088"
stringMultiply("0", "12345") → "0"
stringMultiply("999", "999") → "998001"
stringMultiply("2", "3") → "6"
stringMultiply("10", "10") → "100"
stringMultiply("100", "0") → "0"ヒント
