*************************************(1)****************************************************

      假如需要计算n+16的阶乘，n+16接近10000，已经求得n!（共有m个单元），（每个单元用一个long数表示，表示1-100000000）
 
第一种算法（传统算法）
计算(n+1)!  需要  m次乘法，  m次加法(加法速度较快,可以不予考虑,下同)，m次求余（求本位)，m次除法(求进位），结果为m+1的单元
计算(n+2)!  需要  m+1次乘法，  m+1次求余，  m+1次除法,  结果为m+1个单元
计算(n+3)!  需要  m+1次乘法，  m+1次求余  ，m+1次除法  ，结果为m+2个单元
计算(n+4)!  需要  m+2次乘法，  m+2次求余  ，m+2次除法  ，结果为m+2个单元
计算(n+5)!  需要  m+2次乘法，  m+2次求余  ，m+2次除法  ，结果为m+3个单元
计算(n+6)!  ...
计算(n+7)!  ...
计算(n+8)!  ...
计算(n+9)!  ...
booth算法乘法例题讲解计算(n+10)!  ...
计算(n+11)!  ...
计算(n+12)!  ...
计算(n+13)!  ...
计算(n+14)!  需要  m+7次乘法，m+7次求余  ，m+7次除法  ，结果为m+7个单元
计算(n+15)!  需要  m+7次乘法，m+7次求余  ，m+7次除法  ，结果为m+8个单元
计算(n+16)!  需要  m+8次乘法，m+8次求余  ，m+8次除法  ，结果为m+8个单元
该算法的复杂度：共需:m+(m+8)+(m+1+m+7)*7=16m+64次乘法，16m+64次求余，16m+64次除法
 
第二种算法：
1.将n+1  与n+2  相乘,将n+3  与n+4  相乘,将n+5  与+15与n+16,得到8个数，仍然叫做n1,n2,n3,n4,n5,n6,n7,n8
2.  n1  与  n2相乘，结果叫做p2，结果为2个单元，需要1次乘法。
        p2  与  n3相乘，结果叫做p3，需要2次乘法，1次加法(加法速度快，下面省略），2次除法，2次求余
        p3  与  n4相乘，结果叫做p4，需要3次乘法，3次除法，3次求余
        p4  与  n4相乘，结果叫做p5，需要4次乘法，4次除法，4次求余
        p5  与  n6相乘，结果叫做p6，需要5次乘法，5次除法，5次求余
        p6  与  n7相乘，结果叫做p7，需要6次乘法，6次除法，6次求余
        p7  与  n8相乘，结果叫做p8，结果为8个单元，需要7次乘法，7次除法，7次求余
        这一过程的复杂度为（1+2+3+...+7)共计28次乘法，28次求余，28次除法。
3.将  n!（m个单元)  与p8(8个单元)相乘，需要m*8次乘法，m次除法，m次求余，（注意不是m*8次求余，m*8次除法,原因请大家思考)
该算法的复杂度为  8m次乘法，m次求余，m次除法。
假定求余运算和除法运算和乘法的复杂度相同，则第第一种算法需要48m+192次乘法，
而第2种运算需要10m+84次乘法，当m很大时，第二种算法的速度是第一种算法的4.8倍。
 
      第二种算法表明，在计算阶乘时，通常的方法（先计算出n的阶乘，再用一位数乘以多
位数的方法计算(n+1)的阶乘，再计算n+2的阶乘）不是最优的，更优化的算法是，计算出相邻的几个数的积（称之为部分积），用  部分积  乘以  部分积  的这种多位数  乘以  多位数的算法来计算。如果两个多位数均为n位，使用FFT算法可以将乘法运算的速度  由  n*n  提高  n*log2(n),当n很大时，FFT算法的速度大大快与常规算法。



#include  <math.h>
#include  <memory.h>
#include  <stdio.h>

#define  PI    3.14932384626433832795
#define  E 2.774713527
#define  TEN9    1000000000

typedef  unsigned  __int64  UINT64;
typedef  unsigned  long  DWORD;

int  calcResultLen(DWORD  n)
{
    return  log10(2*PI*(double)n)/2  +  n  *    log10((double)n/E)+2;
}
void  printfResult(DWORD  *buff,int  buffLen)
{
    DWORD  *p=buff;
    while  (  *p==0) p++;
    printf("\nn!=\n");
    for  (  int  i=0;i<buffLen;i++)
    {
    if  (i==0)
    printf("%9d ",p[i]);
    else
    printf("%09d ",p[i]);
    if  (i  %  8==7)
    printf("\n");
    }
    printf("\n");
}
void  calcFac(DWORD  *buff,  int  buffLen,DWORD  n)
{
    int    len=1;
    DWORD  carry,*p,*pEnd,*pBeg;
    unsigned  __int64  prod;

    memset(buff,0,  sizeof(DWORD)*buffLen);
    pBeg=buff+buffLen-1;
    *pBeg=1;
    for  (DWORD  i=2;i<=n;i++)
    {
    for  (p=pBeg,pEnd=p-len,carry=0;p>pEnd;p--)
    {
        prod=  (UINT64)(*p)  *  (UINT64)i  +  (UINT64)carry;
        *p=      prod  %  TEN9;
        carry=prod  /  TEN9;
    }
    if  (carry>0)
    {
        *(pBeg-len)=carry;
        len++;
    }
    }
}
int  main(int  argc,  char*  argv[])
{
    DWORD  n=1;
    printf("n=?");
    scanf("%d",&n);
    int  buffLen=(calcResultLen(n)+8)  /  9;
    DWORD  *buff=new  DWORD[buffLen];
    calcFac(buff,  buffLen,  n);
    printfResult(buff,buffLen);
    delete[]  buff;
    return  0;
}




**************************************(2)***************************************************
用数组的方法解决大数、巨数的阶乘结果越界的问题。
具体算法中有最朴实的乘法运算思想，请各位细细体味。
#include <stdio.h>
int main()
{
    int n; //阶乘大小
    printf("请输入n的大小:");
    scanf("%d",&n); //从键盘接收阶乘大小
    int a[200]; //确保保存最终运算结果的数组足够大
    int carry; //进位
    int digit = 1; //位数
    a[0] = 1; //将结果先初始化为1
    int temp; //阶乘的任一元素与临时结果的某位的乘积结果

    for(int i = 2; i <= n; ++i) //开始阶乘，阶乘元素从2开始依次“登场”
    {
        //按最基本的乘法运算思想来考虑，将临时结果的每位与阶乘元素相乘
        for(int j = 1, carry = 0; j <= digit; ++j)
        {
            //相应阶乘中的一项与当前所得临时结果的某位相乘（加上进位）
            temp = a[j-1] * i + carry;
            a[j-1] = temp % 10; //更新临时结果的位上信息
            carry = temp / 10; //看是否有进位
        }
        while(carry) //如果有进位
        {
            a[++digit-1] = carry % 10; //新加一位，添加信息。位数增1
            carry /= 10; //看还能不能进位
        }
    }
    printf("结果是:\n%d ! = ",n); //显示结果
    for(int i = digit; i >=1; --i)
    {
        printf("%d",a[i-1]);
    }
    return 0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。