C++で文字列として表現された巨大な数を割り算する方法

このチュートリアルでは、文字列として表現された巨大な数を割り算する方法を学びます。

C++の標準的な整数型(long longなど)で扱えるのは、最大でも19桁程度までです。それを超える桁数の巨大な数を演算したい場合は、数値を文字列として保持し、桁ごとに処理する手法が必要になります。

ここでは、文字列形式で与えられた巨大な数と除数(割る数)を受け取り、商(割り算の結果)を求めるプログラムを作成します。基本的な考え方は私たちが普段行う筆算と同じです。まず与えられた数の先頭から、除数以上になる部分を探します。その部分を除数で割った商を結果に加え、余りに次の桁を付け足しながら、同じ処理を末尾まで繰り返していきます。

それでは、問題を解くための手順を確認していきましょう。

• 巨大な数(文字列)と除数を初期化します。

• 先頭の桁から読み込み、除数以上の値になる部分を抽出します。

• 前ステップで読み込んだ位置から数値の末尾まで、以下の処理を繰り返します。

  • 抽出した部分を除数で割り、その商を結果に追加します。

  • 余りを10倍して次の桁を加えた値を、新たな被除数として更新します。

• 結果が空(すべての桁が処理対象外だった場合)は「0」を返します。

• 最後に結果を出力します。

サンプルコード

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
string divideLargeNumber(string number, int divisor) {
    // 結果を格納する文字列
    string result;
    int index = 0;
    // 先頭から、除数以上になる部分を抽出する
    int dividend = number[index] - '0';
    while (dividend < divisor) {
        dividend = dividend * 10 + (number[++index] - '0');
    }
    // すべての桁が処理されるまで繰り返す
    while (number.size() > index) {
        result += (dividend / divisor) + '0';
        // 余りに次の桁を加えて被除数を更新する
        dividend = (dividend % divisor) * 10 + number[++index] - '0';
    }
    if (result.length() == 0) {
        return "0";
    }
    return result;
}
int main() {
    string large_number = "12345678901234567890";
    int divisor = 75;
    cout << divideLargeNumber(large_number, divisor) << endl;
    return 0;
}

出力

上記のプログラムを実行すると、次のような結果が得られます。

164609052016460905

解説

この例では、20桁の数「12345678901234567890」を75で割っています。実はこの数は、符号付き64ビット整数型の上限(約9.2×10^18)をすでに超えており、通常の整数型では正しく扱えません。本アルゴリズムを使えば、桁数に制限なく任意の大きさの数を処理できます。

計算量は桁数をNとするとO(N)で、非常に効率的です。また、各ステップでの余りは必ず除数より小さい値になるため、中間計算で値が巨大化することもありません。

まとめ

本記事では、文字列として表現された巨大な数を割り算する方法を解説しました。筆算と同じ要領で桁ごとに処理を進めることで、組み込みの整数型の限界を超える数値演算が可能になります。同様の考え方は、巨大な数の掛け算や剰余計算にも応用できるので、ぜひ覚えておきましょう。

本チュートリアルについて質問がある場合は、コメント欄でお知らせください。