基本的な階乗計算の実装

階乗は数学における基本的な演算であり、0以上の整数nに対してn!は1からnまでの全ての整数の積として定義される。本節では、C言語を用いて非負整数の階乗を計算するシンプルな関数の実装方法について解説する。

関数プロトコルは以下の通りである。

int CalculateFactorial(const int n);

この関数では、引数として渡された整数が0以上である場合にその階乗値を計算し、負の値が渡された場合は0を返す実装とする。

int CalculateFactorial(const int n) {
    if (n < 0) {
        return 0;
    }
    
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

この実装では、forループを用いて1からnまでの各整数について積算を行っている。計算結果が収まらないケースについては、別途対処が必要である。

大規模階乗計算における課題

前章の実装はnの値が小さい場合には有効であるが、nの値が100を超えるとlong long型でも結果を保持できなくなる。例えば、100!は158桁もの数値となり、通常の整数型では表現できない。

この問題に対処するため、配列を用いた多桁計算の技法を採用する。基本的な考え方は以下の通りである。

• 計算結果を文字列として配列に格納する
• 乗算処理では各桁ごとに計算を行い、桁上がりは別途管理する
• 最終的な出力では配列の各要素を連結して表示する

以下が具体的な実装例である。

void PrintFactorial(const int n) {
    if (n < 0) {
        printf("Invalid input");
        return;
    }
    
    int digits[2560] = {0};
    digits[0] = 1;
    int length = 1;
    
    for (int i = 2; i <= n; i++) {
        int carry = 0;
        for (int j = 0; j < length; j++) {
            int product = digits[j] * i + carry;
            digits[j] = product % 10;
            carry = product / 10;
        }
        while (carry > 0) {
            digits[length++] = carry % 10;
            carry /= 10;
        }
    }
    
    for (int i = length - 1; i >= 0; i--) {
        printf("%d", digits[i]);
    }
}

このアルゴリズムでは、計算結果を逆順で配列に格納することで、乗算処理における桁上がり処理を簡略化している。配列の各要素は0から9の値のみを保持するため、任意の大きな整数を表現することが可能となる。

アルゴリズムの計算量と最適化の余地

この実装の時間計算量はO(n×m)であり、nは入力値、mは結果の桁数に相当する。空間計算量は結果の桁数に比例する。n=1000程度であれば、実用的な実行時間で計算を完了することができる。

さらなる最適化としては、FFT（高速フーリエ変換）を用いた乗算算法の適用や、段数乘法による計算の効率化などが考えられる。これらは非常に大きなnに対して有効であるが、実装の複雑さも増大するため、用途に応じた選択が重要である。