大数阶乘

以前有道作业是大数阶乘,重新捡起来实现一下,已经完全理解了该怎么做,实现细节也明白了.

一会用记事本手工写一个试试.

为了做这个题， 还总结了一个斯特林公式取对数估算n!输出结果字符串字符数量的经验公式 ^_^

/// @file src_n_factorial.cpp
/// @brief 算n!的实现

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <conio.h>
#include <memory.h>
#include <time.h>

#ifndef WORD
#define WORD unsigned short
#endif

void calcFact(size_t n); ///< 算n!
size_t getFactNCharCnt(size_t n); ///< 估算n!结果字符数

int main(int argc,char* argv[]) {
    size_t n = 0;
    clock_t tmBegin = 0;
    clock_t tmEnd = 0;

    while (1) {
        printf("nplease input n to fact:");
        scanf("%u",&n);
        
        if (0 == n)
            break;
        
        printf("ncalcFact(%u) = ",n);
        tmBegin = clock();
        calcFact(n);
        tmEnd = clock();
        printf("cost time = %dSn",(tmEnd - tmBegin) / CLOCKS_PER_SEC);
    }

    /// 已经验证过了,和Windows计算器的n!(n最大3248)比对过
    /// 如果UI上显示不下,可以用 my.exe > d:txt 来运行程序
    /** run result
    
      please input n to fact:100
      
        calcFact(100) = 9332621544394415268169923885626670049071596826438162146859296389
        52175999932299156089414639761565182862536979208272237582511852109168640000000000
        00000000000000
        nResultCharCnt = 160
        cost time = 0S
        
      please input n to fact:0
          
      END,press any key to quit
    */

    printf("nEND,press any key to quitn");
    _getch();
    return 0;
}

void calcFact(size_t n) {
    size_t nArySize = getFactNCharCnt(n); ///< n!结果占用的字符数量
    size_t nIndex = 0;
    size_t nMul = 0;
    size_t nSum = 0;
    size_t nUnitMax = 10000; ///< 一个运算单位中能放的最大数.
    size_t nResultCharCnt = 0;
    WORD wCarry = 0;
    WORD* pAry = NULL;
    WORD* pTail = NULL;
    WORD* pHead = NULL;
    WORD* pCur = NULL;
    bool bFirstPrint = true;

    nArySize = (nArySize - (nArySize % sizeof(WORD))) / sizeof(WORD) + 1;
    pAry = (WORD*)malloc(nArySize * sizeof(WORD));
    if (NULL == pAry)
        return;

    memset(pAry,nArySize * sizeof(WORD));

    /// 预置了被乘数为1,新的乘数从2到n
    *(pAry + nArySize - 1) = 1;
    for (nIndex = 2,pTail = pHead = (pAry + nArySize - 1);
        nIndex <= n;
        nIndex++) {
            /// 用新的乘数从低位字节到高位字节,一直乘到有进位的最高被乘数字节.
            /// 每次的乘积都加上进位
            for (pCur = pTail; pCur >= pHead; pCur--) {
                nMul = nIndex * (*pCur) + wCarry;
                *pCur = nMul % nUnitMax;
                wCarry = (nMul - *pCur) / nUnitMax;
            }

            /// 连续累加进位到高字节
            while (wCarry > 0) {
                pHead--;
                nSum = (*pHead) + wCarry;
                (*pHead) = nSum % nUnitMax;
                wCarry = (nSum - *(pHead)) / nUnitMax;
            }
    }

    /// 找到第一个不为0的元素位置
    pHead = pAry;
    while (pHead <= pTail) {
        if (0 == *pHead)
            pHead++;
        else
            break;
    }

    while (pHead <= pTail) {
        if (bFirstPrint) {
            bFirstPrint = false;
            nResultCharCnt = pTail - pHead + 1;
            printf("%d",*pHead); ///< 不打印起始数字的开始0字符
        }
        else 
            printf("%4.4d",*pHead); ///< 打印0

        pHead++;
    }

    printf("n");

    /// n!结果字符串,一共打印出来多少字符
    printf("nResultCharCnt = %dn",nResultCharCnt * sizeof(WORD) * 2);

    free(pAry);
}

size_t getFactNCharCnt(size_t n) {
    double N = (double)n;
    const double E = 2.71828;
    return (size_t)(N * (log10(N) - log10(E)) + 4);
}