刚刚试过用位运算取位,但发现了实现的过程中数据输出会出现问题,或者这个不适合用位运算实现,刚刚就是想到说了一下,看来还是要对数据取余输出的~

哦 看懂了 的确算法是一样的

我也弄了个简单的出来不过得出的结果却是16进制的,如果要转换成10进制那么要把那个大数看作一个整体转换才行,没有验证结果,(或者结果是错误的),当然效率也不怎么样了,就是简单弄个看看而已~

还有一个小优化的方案,就是在内循环开始之前跳过前导0直接从非0位开始判断,n!统计0的个数这个好弄吧~
要想更高效的或者只能直接用FFT之类的算法减少乘法运算量了,算是这样了~

PS:此代码有bug,把 a[count++]=0;改成a[count++]=GET_HIGH(a[j-1]);即可~具体可以看看80楼的代码
嗯,80楼的应该可以了~

#include<stdio.h>

#define GET_LOW( s )    \
    ((s)&0x0000ffff)
        
#define GET_HIGH( s )    \
    (((s)&0xffff0000)>>16)

unsigned fun( unsigned[],unsigned );

void print( const unsigned[],unsigned );

int main( void )
{
   unsigned a[3000];

   print(a,fun(a,1001));
        
    return 0;
}

unsigned fun( unsigned a[],unsigned len )
{
    unsigned i;
    unsigned j;
    unsigned count=3;
        
    a[1]=1;
    a[0]=0;
    a[2]=0;

 
    for (i=1;i!=len;++i)
    {
        for (j=1;j!=count;++j) 
            a[j]=GET_LOW(a[j])*i+GET_HIGH(a[j-1]);
        
        if (GET_HIGH(a[count-1]))
        {
            a[count++]=0;
        }
    }
    
    return count;
           
}

void print( const unsigned a[],unsigned len)
{
    while (--len)
        printf("%04x",GET_LOW(a[len]));
        
    puts("");
}

[此贴子已经被作者于2018-6-7 21:57编辑过]

二分法求乘幂的确可以优化,和我想到的一样~
所以说,100000!用9s可以理解吧~
而且我不觉得他的代码比较慢,要看看10000!或者更大的数效率如何才行,而我自己弄了个出来,不过是16进制的,效率也算是这样了

~

哈哈，这贴是我发的吗？酒后一贴都快成神贴了。

能出神贴，也不错了，俺现在正在整理一份资料，到时候也来一份哦。不过，还需要一些时间。

怎么就结贴了？非常想学习题主@童生的算法，肯定他算法有先进之处，否则不会发挑战帖的！
最近拜读了很多做大数阶乘的帖子，发现算法都差不多，不是使用10000进制的，就是使用100000进制的。我比较贪心，使用1000000进制，这样的代码最多只能做到4200的阶乘，刚好满足题意。通过与所有类似代码对比，我的代码都比他们的快那么一点，由于算法相同，并没有质的变化，比如“https://bbs.bccn.net/viewthread.php?tid=32009&highlight=%2Bkai”里@Knocker大神的代码在我电脑上求10000！用时840毫秒，我的790毫秒（双方都运行10次的平均耗时），仅此而已。题主是在此基础上发挑战帖的，肯定算法有质的变化！
我此前也提到的用64位做，经过实验，无论是自始至终使用64位，还是大部分时间32位计算，有进位时使用64位取进位，都不行，运行100次1000！都超过了1000ms。后来我使用了现在这个算法，这个算用了共用体数据结构，运算过程中只需要做一次按位乘法，不再需要做除法和取余数运算，经测试运算100次1000！由515ms提高到375ms，提高了140毫秒，算是有质的飞跃了。但这个算法有一个缺点：它纯粹是16进制运算，运算结果是一个超大的16进制数，为了显示结果，我专门写了个内存超大16进制数10进制显示的函数，1000的阶乘的结果16进制只有2136位，显示起来速度还可以，但显示超过万位的16进制数耗时不少。

用共用体我看看你的代码,似乎要涉及到大端小端的处理,不知道会不会因为电脑的端口模式不同而会产生不同的结果~

PS:个人感觉还是a&0x0000ffff和(a&0xffff0000)>>16比较直接~

[此贴子已经被作者于2018-6-5 07:57编辑过]

我也来一个

#include <stdio.h>
#include <time.h>
#include <sys/time.h>
char current[100] = "";
long int lTime = 0;
struct tm NowTime;
struct timeval st,et;

#define DebugInfo(fmt,args...)\
        lTime = time(NULL); \
        localtime_r(&lTime, &NowTime);\
        sprintf(current, "[%02d/%02d %02d:%02d:%02d]", NowTime.tm_mon+1, NowTime.tm_mday, \
        NowTime.tm_hour, NowTime.tm_min, NowTime.tm_sec);\
        printf("\033[33m%s %s %d -- " fmt "\033[0m\n", current,  __func__, __LINE__, ##args);

#define BEGIN gettimeofday(&st, NULL);
#define END gettimeofday(&et, NULL);
#define RESP ((et.tv_sec-st.tv_sec)*1000000 + et.tv_usec - st.tv_usec)
#define SIZE 3000           


int main(int argc, char** argv)
{
        int n,i,j,k,l;
        sscanf(argv[1],"%d", &n);
        int a[SIZE]={1,0};

        BEGIN
        for(i = 2; i <= n; i++)
        {

                //进位
                for(k = 0,j = 0; j < SIZE; j++)
                {
                        l = a[j]*i + k;
                        a[j] = l%10;
                        k = l/10;
                }
        }

        for(i = SIZE - 1; i >= 0; i--)
            if(a[i])
                break;

        for(j=i;j>=0;j--)
            printf("%d",a[j]);

        printf("\n");

        END
        DebugInfo("%ldus", RESP);

        return 0;
}

[此贴子已经被作者于2018-6-5 14:54编辑过]

物是人非