我的截图计算100次是 116 ms

1000！执行100次耗时515毫秒，这是我这破电脑在反复优化后能达到的最佳效果了，在我原来ACM能通过的代码基础上做了三处优化：
1，原代码追求结果数据顺序存放，所以每计算一次做了一次左移，现在按照计算顺序存放，倒序显示，省略了左移操作
2，楼主只要求做1000的阶乘，而unsigned int 能完全有效表示到9位数，因此我用低6位数表示有效位，高4位数表示进位，扫描次数减少20多万次，但这样不能计算10000的阶乘，原代码为能计算10000的阶乘，是用低5位表示有效数，高5位表示进位的。
3，取进位需要做除法、取余数运算，据说这也比较耗时，因此用了比较操作，只有乘积大于999999时才取进位，减少做除法运算209万次。
也就这样了，待会准备使用INT_64的数据试试，INT_64可以有效表示19位十进制数，我可以用14位表示有效位，这样总循环次数只有1000*2567/14=183358次即可，应该会大大提速的。估计@lin5161678大神和我算法差不多，他之所以快，应该是电脑好。我上学时家里买的是惠普I5的学生机，大三时丢了，又不敢和家里说，只好省吃俭用花500淘的一个08年的二手惠普，也就是能做些日常应用，多开几个网页就卡半天

还以为运算结果有误,仔细看后厉害了

~

[此贴子已经被作者于2018-6-2 17:45编辑过]

开玩笑，这代码是我大二刚学c时，比较喜欢ACM，找到杭电ACM1042一次性刷过的，我对比了一些其他通过的人的数据（只看的到其他人的代码字符数、执行时间等等），我比这些人的代码量都少，执行速度偏上。

我来说一下,其实个人感觉优化就是压位操作,看到那个51nod要求计算100000的阶乘,讨论说用fft分治或者是用ntt算法的,那些我了解过一下,就是数学跟不上,总之求n!算法复杂度可以优化成o(n*log(n)),嗯,有兴趣可以看看41楼那个网址,看到后我还是当什么都不知道好了~

我也不懂什么FFT、NTT，看了那个里面的说计算100000的阶乘才9秒，有点不可思议，我用windows计算器算提示我要等待很长时间，然后的确等了好久，仍然没出结果，难道微软没有算法工程师嘛？我代码算10000的阶乘需要780毫秒。

是的 算法核心部分差不多是 1000000进制 可以减少很多次计算
不过进位操作有点区别
其实直接把进位加到下一个数据里面就可以 不用存放到高位
比如
38892244*1234
算法是
892244*1234 == 1101029096
029096存在最低位 1101加到后面的数据里面
后面就是
38*1234+1101 == 47993

组合起来
47993029096

其实最大乘数就是1000,不会超过10个位,也就是说进位操作直接用位运算加上最后10个进位就可以了,连取余运算都不用 ,应该是这样吧~

看不懂 没位运算呀?

回复 58楼 九转星河：我觉得你应该写一个才行，我52楼图片已经显示出求大阶乘的代码了，遮住的部分就两句，你不擅长填空么，以你的资质应该很轻松填对的。

回复 57楼 lin5161678：既是进位，当然是要加到下一位的，看了你的演示，思路完全一样。

刚才看了一位专门研究大数阶乘的大神的文章，大部分篇幅介绍如何快速得到非精确的大数阶乘，求1千万的非精确阶乘只需0.01秒，的确快，不过他随后附了一个求精确阶乘的，好慢啊，在我电脑上需要5828毫秒，比我的代码慢7倍~~~
文章链接：https://blog.