| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 8877 人关注过本帖, 1 人收藏
标题:挑战C版所有人,1000!
只看楼主 加入收藏
lin5161678
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:35
帖 子:1103
专家分:3530
注 册:2011-12-3
收藏
得分:0 
以下是引用dzy123在2018-6-2 12:12:23的发言:

我计算一次要78毫秒,100次要3000多毫秒

我的截图计算100次是 116 ms

https://zh.
2018-06-02 12:18
xzlxzlxzl
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖北
等 级:贵宾
威 望:125
帖 子:1091
专家分:5825
注 册:2014-5-3
收藏
得分:0 
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-06-02 17:36
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 52楼 xzlxzlxzl
还以为运算结果有误,仔细看后厉害了

~

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


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-06-02 17:41
xzlxzlxzl
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖北
等 级:贵宾
威 望:125
帖 子:1091
专家分:5825
注 册:2014-5-3
收藏
得分:0 
回复 53楼 九转星河
开玩笑,这代码是我大二刚学c时,比较喜欢ACM,找到杭电ACM1042一次性刷过的,我对比了一些其他通过的人的数据(只看的到其他人的代码字符数、执行时间等等),我比这些人的代码量都少,执行速度偏上。
2018-06-02 17:55
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 54楼 xzlxzlxzl
我来说一下,其实个人感觉优化就是压位操作,看到那个51nod要求计算100000的阶乘,讨论说用fft分治或者是用ntt算法的,那些我了解过一下,就是数学跟不上,总之求n!算法复杂度可以优化成o(n*log(n)),嗯,有兴趣可以看看41楼那个网址,看到后我还是当什么都不知道好了~


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-06-02 18:07
xzlxzlxzl
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖北
等 级:贵宾
威 望:125
帖 子:1091
专家分:5825
注 册:2014-5-3
收藏
得分:0 
回复 55楼 九转星河
我也不懂什么FFT、NTT,看了那个里面的说计算100000的阶乘才9秒,有点不可思议,我用windows计算器算提示我要等待很长时间,然后的确等了好久,仍然没出结果,难道微软没有算法工程师嘛?我代码算10000的阶乘需要780毫秒。
2018-06-02 18:26
lin5161678
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:35
帖 子:1103
专家分:3530
注 册:2011-12-3
收藏
得分:0 
回复 52楼 xzlxzlxzl
是的 算法核心部分差不多是 1000000进制 可以减少很多次计算
不过进位操作有点区别
其实直接把进位加到下一个数据里面就可以 不用存放到高位
比如
38892244*1234
算法是
892244*1234 == 1101029096
029096存在最低位 1101加到后面的数据里面
后面就是
38*1234+1101 == 47993

组合起来
47993029096

https://zh.
2018-06-02 18:38
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 57楼 lin5161678
其实最大乘数就是1000,不会超过10个位,也就是说进位操作直接用位运算加上最后10个进位就可以了,连取余运算都不用 ,应该是这样吧~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-06-02 19:30
lin5161678
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:35
帖 子:1103
专家分:3530
注 册:2011-12-3
收藏
得分:0 
回复 58楼 九转星河
看不懂 没位运算呀?

https://zh.
2018-06-02 19:34
xzlxzlxzl
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖北
等 级:贵宾
威 望:125
帖 子:1091
专家分:5825
注 册:2014-5-3
收藏
得分:0 
回复 58楼 九转星河:我觉得你应该写一个才行,我52楼图片已经显示出求大阶乘的代码了,遮住的部分就两句,你不擅长填空么,以你的资质应该很轻松填对的。

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

刚才看了一位专门研究大数阶乘的大神的文章,大部分篇幅介绍如何快速得到非精确的大数阶乘,求1千万的非精确阶乘只需0.01秒,的确快,不过他随后附了一个求精确阶乘的,好慢啊,在我电脑上需要5828毫秒,比我的代码慢7倍~~~
文章链接:https://blog.
2018-06-02 20:12
快速回复:挑战C版所有人,1000!
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.111377 second(s), 9 queries.
Copyright©2004-2021, BCCN.NET, All Rights Reserved