【C++】文字列として表現された大きな数同士の乗算を実装する方法

文字列形式で与えられた2つの大きな数値を乗算する方法を解説します。この問題を解く鍵となるのは、「前回の桁同士の乗算結果」と「繰り上がり(carry)」を保持しながら計算を進めるという考え方です。前の桁の乗算結果と繰り上がりを活用することで、次の桁の積を効率的に求めることができます。

まずは具体例を見てみましょう。

入力

15
2

出力

30

アルゴリズム

• 2つの数値を文字列として初期化します。

• 長さが「1つ目の数値の長さ + 2つ目の数値の長さ」である結果格納用の文字列を初期化します。

• 1つ目の数値を末尾から先頭に向かって走査します。

  • 2つ目の数値も末尾から先頭に向かって走査します。

    • 2つの桁を掛け合わせ、対応する位置に既に格納されている値(前回の計算結果)を加算します。

    • その位置の値を新しい結果で更新します。

    • 繰り上がりは、結果文字列の1つ前のインデックスに加算して保存します。

• 結果の各要素に文字 '0' を加算し、数値を文字に変換します。

• 先頭の余分なゼロを取り除いた状態で結果を返します。

実装

以下は、上記のアルゴリズムをC++で実装したコードです。

#include <bits/stdc++.h>
using namespace std;
string multiplyTwoNumbers(string num1, string num2) {
   if (num1 == "0" || num2 == "0") {
      return "0";
   }
   string product(num1.size() + num2.size(), 0);
   for (int i = num1.size() - 1; i >= 0; i--) {
      for (int j = num2.size() - 1; j >= 0; j--) {
            int n = (num1[i] - '0') * (num2[j] - '0') + product[i + j + 1];
            product[i + j + 1] = n % 10;
            product[i + j] += n / 10;
      }
   }
   for (int i = 0; i < product.size(); i++) {
      product[i] += '0';
   }
   if (product[0] == '0') {
      return product.substr(1);
   }
   return product;
}
int main() {
   string num1 = "34";
   string num2 = "57";
   if((num1.at(0) == '-' || num2.at(0) == '-') && (num1.at(0) != '-' || num2.at(0) != '-')) {
      cout << "-";
   }
   if(num1.at(0) == '-') {
      num1 = num1.substr(1);
   }
   if(num2.at(0) == '-') {
      num2 = num2.substr(1);
   }
   cout << multiplyTwoNumbers(num1, num2) << endl;
   return 0;
}

出力

上記のコードを実行すると、次の結果が得られます。

1938