大きな数の階乗を求めるアルゴリズムとC++での実装方法

コンピュータ上では、変数はメモリ上の決まった領域に格納されます。しかし、そのメモリ領域のサイズは固定されているため、15! や 20! のような大きな値の階乗を求めようとすると、計算結果が変数の表現範囲を超えてしまい、誤った値が返されてしまいます。

このような巨大な数を正確に扱うには、結果を配列に格納する方法が有効です。配列の各要素に結果の各桁を1つずつ保存していきます。ただし、配列に対して直接数値を掛けることはできないため、配列内のすべての桁に対して、筆算と同じ要領で手動の掛け算処理を実行する必要があります。

入力と出力

入力:
大きな数: 50
出力:
指定された数の階乗:
30414093201713378043612608166064768844377641568960512000000000000

アルゴリズム

multiply(x, multiplicand)

入力: 掛ける数 x、および配列として表された大きな被乗数。

出力: 掛け算を実行した後の結果。

Begin
    carry := 0
    被乗数の各桁 i について繰り返し:
        prod := i * x + carry
        i := prod mod 10
        carry := prod / 10
    done

    carry ≠ 0 の間、繰り返し:
        被乗数配列の末尾に (carry mod 10) を挿入
        carry := carry / 10
    done
End

factorial(n)

入力: 数値 n。

出力: n の階乗を求める。

Begin
    結果用の配列を定義する。
    結果配列に 1 を挿入する。

    i := 2 から n まで繰り返し:
        multiply(i, result) を呼び出す
    done

    結果を反転させる
    result を返す
End

C++による実装例

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

void multiply(int x, vector<int>&multiplicand) {     // 被乗数に x を掛ける
    int carry = 0;                                   // 桁上がり（carry）を 0 で初期化
    vector<int>::iterator i;

    // 被乗数の全桁に x を掛ける
    for (i=multiplicand.begin(); i!=multiplicand.end(); i++) {
        int prod = (*i) * x + carry;
        *i = prod % 10;                              // 積の下一桁だけを格納
        carry = prod/10;                             // 残りの部分を桁上がりに加算
    }

    while (carry) {                                  // 桁上がりが残っている間
        multiplicand.push_back(carry%10);
        carry = carry/10;
    }
}

void factorial(int n) {
    vector<int> result;
    result.push_back(1);                             // 最初に結果として 1 を格納

    for (int i=2; i<=n; i++)
        multiply(i, result);                         // 1×2×3×……×n を計算

    cout << "Factorial of given number is: "<<endl;

    reverse(result.begin(), result.end());           // 結果の順序を反転

    vector<int>::iterator it;

    for(it = result.begin(); it != result.end(); it++)
        cout << *it;
}

int main() {
    factorial(50);
}

実行結果

Factorial of given number is:
30414093201713378043612608166064768844377641568960512000000000000

解説

この手法のポイントは以下の通りです。

• 桁ごとの管理: 各配列要素には 0〜9 の1桁のみを保存するため、どれほど大きな数でもオーバーフローせずに扱えます。
• 筆算と同じ原理: 通常の掛け算と同様に、下位の桁から順に計算し、桁上がり（carry）を次の桁へ引き継いでいきます。
• 逆順での格納: 計算の都合上、結果は下位桁から順に配列へ格納されるため、最終的な出力時には reverse() で順序を反転させて正しい並びにします。

50! のような65桁にも及ぶ巨大な階乗の値も、この方法なら標準の整数型では不可能な計算を正確に行うことができます。同様のアプローチは Python のような多倍長整数を標準でサポートしていない言語環境や、自前で多倍長演算を実装したい場合にも応用できます。