C 語言大數階乘實作：陣列模擬高精度運算詳解

編輯：關於C語言

問題背景

標準 C 語言整數型別 (long long 64 位元) 最大僅能表示 20! (≈2.4×10¹⁸)。對於 100!、1000! 甚至更大的階乘，必須實作高精度算術 (Big Integer)。本文採用十進位陣列模擬手算乘法，逐位相乘並處理進位，可計算任意大小的階乘 (受限於陣列長度與記憶體)。

核心演算法邏輯

陣列表示：a[0] 不用，a[1] 存個位，a[2] 存十位……a[len] 存最高位。
初始化：a[1] = 1，其餘為 0，長度 len = 1 (代表數值 1)。
迭代相乘：對 i = 2 .. m，將當前陣列代表的大整數乘以 i。
- 對每一位 j = 1 .. len：tmp = a[j] * i + carry
- 當前位更新：a[j] = tmp % 10
- 進位更新：carry = tmp / 10
- 若最高位產生進位 (j == len && carry != 0)，len++ 擴展陣列。
輸出：從 a[len] 逆序列印至 a[1]。

完整可編譯代碼

#include <stdio.h>
#include <stdlib.h>

void BigFactorial(int m)
{
    // 估算所需位數：log10(m!) ≈ m*log10(m/e) + 0.5*log10(2πm)
    // 1000! 約 2568 位，50000 足夠應付 10000! 以內
    static int a[50000] = {0, 1};  // 靜態避免棧溢位，a[1]=1 其餘 0
    int i, j, carry, tmp, len = 1;

    for (i = 2; i <= m; i++) {
        carry = 0;
        for (j = 1; j <= len; j++) {
            tmp = a[j] * i + carry;
            a[j] = tmp % 10;
            carry = tmp / 10;
        }
        while (carry > 0) {  // 處理多位進位 (如 99*100 產生兩位進位)
            a[++len] = carry % 10;
            carry /= 10;
        }
    }

    for (i = len; i >= 1; i--) putchar('0' + a[i]);
    putchar('\n');
}

int main(void)
{
    int n;
    printf("輸入非負整數 n (建議 ≤ 10000)：");
    if (scanf("%d", &n) != 1 || n < 0) return 1;
    BigFactorial(n);
    return 0;
}

關鍵細節優化

1. 陣列大小估算

使用斯特靈公式預估位數：digits ≈ m * (log10(m) - log10(e)) + 0.5 * log10(2 * M_PI * m) + 1。程式中固定 50000 可支援 ~15000!，若需更大請動態分配 (malloc)。

2. 進位處理修正

原始代碼 if (j==len&&carry!=0) len++; 僅處理單位進位。當 carry ≥ 10 時 (例如大數乘大數)，需用 while (carry) { a[++len] = carry % 10; carry /= 10; } 循環展開所有進位位。

3. 輸出效率

逐字元 putchar 比 printf("%d", a[i]) 更快，避免格式化開銷。亦可先組裝字串再一次 fwrite 輸出。

4. 基數優化 (進階)

若以 10⁴ (10000) 或 10⁹ 為基數 (每個 int 存 4 或 9 位十進位)，可大幅減少迴圈次數與記憶體，但輸出時需補零格式化 (%04d 或 %09d)。

執行範例

$ ./factorial
輸入非負整數 n (建議 ≤ 10000)：100
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

複雜度分析

時間：O(m² × log m) — 外層 m 次，內層平均位數 O(m log m)。
空間：O(m log m) 位元，約 m * log10(m/e) 位十進位數字。

常見錯誤與除錯

現象	原因	修正
結果前導出現 0	陣列未正確初始化或 `len` 計算錯誤	確認 `a[1]=1`，其餘 0；`len` 隨最高非零位更新
大數乘法結果錯誤	進位處理僅單位	改用 `while(carry)` 循環展開
段錯誤	陣列大小不足導致越界	依公式預估或動態 `realloc` 擴展