C語言階乘求和：計算 1! + 2! + ... + 20! 的溢出陷阱與高精度解法

C語言階乘求和：計算 1! + 2! + ... + 20! 的溢出陷阱與高精度解法

階乘增長極快：13! = 6,227,020,800 > 2³¹-1 (int 最大值)，21! > 2⁶³-1 (long long 最大值)。原始碼使用 `float` 導致精度嚴重丟失，本文提供正確的整數高精度實現。

原始碼問題分析

// 原始碼
float s=0, t=1;
for (n=1; n<=20; n++) {
    t = t * n;  // float 精度只有 ~7 位有效數字
    s = s + t;
}
printf("%f\n", s);  // 輸出 2561327455189073900.000000 (尾部全 0，精度已失真)

嚴重缺陷：`float` 只有 23 位尾數 (約 7 位十進制有效數字)，20! ≈ 2.43×10¹⁸ 需要 19 位十進制數字，**完全無法精確表示**。

正確解法一：unsigned long long (64 位無號，支援至 20!)

#include <stdio.h>
#include <inttypes.h>  // PRIu64 格式巨集

int main() {
    unsigned long long sum = 0;
    unsigned long long fact = 1;
    
    for (int n = 1; n <= 20; n++) {
        fact *= n;      // 20! = 2,432,902,008,176,640,000 < 2⁶⁴-1
        sum += fact;
    }
    
    printf("Sum = %llu\n", sum);           // 2561327494111820313
    printf("Sum = %" PRIu64 "\n", sum);    // 可移植寫法
    return 0;
}

執行結果 (精確值)

Sum = 2561327494111820313

驗證各項階乘值

解法二：任意精度大整數 (突破 20! 限制)

// 簡易大整數：十進制陣列，每位存 4 位數字 (base 10000)
#define BASE 10000
#define MAX_DIGITS 100  // 足夠存 100! 以上

typedef struct {
    int digits[MAX_DIGITS];
    int len;
} BigInt;

void bigint_init(BigInt *a) { a->len = 1; a->digits[0] = 0; }
void bigint_set(BigInt *a, int val) { 
    a->len = 0; 
    while (val) { a->digits[a->len++] = val % BASE; val /= BASE; }
    if (a->len == 0) a->len = 1;
}

void bigint_add(BigInt *res, const BigInt *a, const BigInt *b) {
    int carry = 0, maxlen = a->len > b->len ? a->len : b->len;
    for (int i = 0; i < maxlen || carry; i++) {
        int sum = carry;
        if (i < a->len) sum += a->digits[i];
        if (i < b->len) sum += b->digits[i];
        res->digits[i] = sum % BASE;
        carry = sum / BASE;
    }
    res->len = maxlen + (carry ? 1 : 0);
}

void bigint_mul_int(BigInt *res, const BigInt *a, int m) {
    long long carry = 0;
    for (int i = 0; i < a->len || carry; i++) {
        long long prod = carry;
        if (i < a->len) prod += (long long)a->digits[i] * m;
        res->digits[i] = prod % BASE;
        carry = prod / BASE;
    }
    res->len = a->len;
    while (carry) { res->digits[res->len++] = carry % BASE; carry /= BASE; }
}

void bigint_print(const BigInt *a) {
    printf("%d", a->digits[a->len - 1]);
    for (int i = a->len - 2; i >= 0; i--) printf("%04d", a->digits[i]);
    printf("\n");
}

int main() {
    BigInt sum, fact, tmp;
    bigint_init(&sum); bigint_set(&sum, 0);
    bigint_init(&fact); bigint_set(&fact, 1);
    
    for (int n = 1; n <= 100; n++) {  // 可算到 100! 甚至更大
        bigint_mul_int(&tmp, &fact, n);
        fact = tmp;
        bigint_add(&tmp, &sum, &fact);
        sum = tmp;
    }
    
    printf("1!+...+100! = ");
    bigint_print(&sum);
    return 0;
}

解法三：GMP 庫 (工業級任意精度)

// 需安裝 libgmp-dev
#include 

int main() {
    mpz_t sum, fact;
    mpz_init_set_ui(sum, 0);
    mpz_init_set_ui(fact, 1);
    
    for (int n = 1; n <= 1000; n++) {
        mpz_mul_ui(fact, fact, n);
        mpz_add(sum, sum, fact);
    }
    
    gmp_printf("Sum = %Zd\n", sum);
    mpz_clear(sum); mpz_clear(fact);
    return 0;
}

浮點數 vs 整數精度對比

總結

**階乘求和必須用整數型別**。20! 以內用 `unsigned long long` 完美精確；超出 20! 需自行實現大整數或使用 GMP 庫。**絕不可用 float/double 進行整數精確計算**。正確答案：**2,561,327,494,111,820,313**。