Karatsubaのアルゴリズムを使った高速な整数乗算

まず、Karatsubaのアルゴリズムの基本的な考え方を説明します。大きな整数AとBを乗算する場合、それぞれを2つの部分に分割します。例えば、AをA1とA0に、BをB1とB0に分割します。ここで、A1とB1はAとBの上位の桁、A0とB0は下位の桁となります。

次に、以下の3つの計算を行います。

A1 * B1: 上位桁同士の乗算
A0 * B0: 下位桁同士の乗算
(A1 + A0) * (B1 + B0): 上位桁と下位桁を足した値同士の乗算

これらの計算結果を組み合わせて最終的な乗算結果を得ます。

このアルゴリズムを実装するために、以下にC++のコード例を示します。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string karatsubaMultiply(const string& num1, const string& num2) {
    int n = max(num1.size(), num2.size());

    if (n == 0) {
        return "0";
    }

    if (n == 1) {
        int val = (num1[0] - '0') * (num2[0] - '0');
        return to_string(val);
    }

    int half = n / 2;
    string a = num1.substr(0, num1.size() - half);
    string b = num1.substr(num1.size() - half);
    string c = num2.substr(0, num2.size() - half);
    string d = num2.substr(num2.size() - half);

    string ac = karatsubaMultiply(a, c);
    string bd = karatsubaMultiply(b, d);
    string adbc = karatsubaMultiply(to_string(stoi(a) + stoi(b)), to_string(stoi(c) + stoi(d))) - ac - bd;

    string result = ac;
    result.append(half * 2, '0');
    result = result + adbc;
    result = result + bd;

    return result;
}
int main() {
    string num1 = "12345";
    string num2 = "6789";

    string result = karatsubaMultiply(num1, num2);

    cout << "Result: " << result << endl;

    return 0;
}

このコードでは、karatsubaMultiply関数がKaratsubaのアルゴリズムを実装しています。この関数は2つの整数を文字列として受け取り、乗算結果を文字列として返します。main関数では、例として2つの整数を与えて乗算結果を表示しています。

このようにKaratsubaのアルゴリズムを使うと、通常の乗算アルゴリズムよりも高速に大きな整数の乗算を行うことができます。