VBGood网站全文搜索 Google

搜索VBGood全站网页(全文搜索)

VB爱好者乐园(VBGood)

 找回密码
 立即注册
搜索
楼主: 八戒2

擂台第70期[考拉兹猜想]

[复制链接]
发表于 2011-4-1 23:32:16 | 显示全部楼层
这个怎么比较程序优劣呢?
回复 支持 反对

使用道具 举报

发表于 2011-4-3 13:34:07 | 显示全部楼层
回复 Igawk 的帖子
你直接给出那个会膨胀到1E+18的数让大伙验证就行了


OK,:)
[xxx@xxx collatz]$ icc -O3 -openmp collatz_1.cpp
[xxx@xxx collatz]$ ./a.out
Input max number:10000000000
done, time=15.760941s
max value=18144594937356598024, start=8528817511
[xxx@xxx collatz]$
回复 支持 反对

使用道具 举报

发表于 2011-4-3 23:54:27 | 显示全部楼层
本帖最后由 XOoo 于 2011-4-4 19:01 编辑

放假比较闲,我也写个玩玩。
算的最大数和acme_pjz的相同,8528817511,不过速度就差远了...

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复 支持 反对

使用道具 举报

发表于 2011-4-4 20:43:58 | 显示全部楼层
本帖最后由 Igawk 于 2011-4-4 21:02 编辑

没有测到完成,到30亿左右:

1)XOoo的程序比Pjz的快1/4.

2)XOoo的最大中间数显示被除以2



本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

点评

是对,因为你说过只要验证奇数,我就在处理奇数时顺手除了个2  发表于 2011-4-4 20:50
回复 支持 反对

使用道具 举报

发表于 2011-4-5 00:40:14 | 显示全部楼层
本帖最后由 XOoo 于 2011-4-5 00:40 编辑

我上面发的程序是老老实实地一个一个数地算的(虽然算奇数时顺手加了个\2)

我想,也许可以参考crc的算法,先对00~FF这些数建立一个运算表,表中每个条目记录一个“乘数”(*3*3*3...)和一个“加数”。
之后对某个数进行计算时,只需根据这个数的末8位查表,然后右移7位,乘上“乘数”,再加上“加数”,相当于一次处理了7位数据。
回复 支持 反对

使用道具 举报

发表于 2011-4-11 20:22:25 | 显示全部楼层
本帖最后由 sunfrank 于 2011-4-12 17:59 编辑

回复 八戒2 的帖子

把/2写成*0.5,可以提高效率cpu做除法不如乘法。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2011-4-14 11:03:13 | 显示全部楼层
过几天要出差,本期准备提前结束了,谢参加的发送源到到163那个邮箱,谢谢
回复 支持 反对

使用道具 举报

发表于 2011-4-14 18:17:57 | 显示全部楼层
本帖最后由 XOoo 于 2011-4-14 18:20 编辑

前几天有闲改了一下。马上补点注释,源码已发到邮箱
算法改了,因为:
* 定义(在2进制下讨论):X是任意n位的数, M是X经n次F()运算后得到结果.
  可以证明, 若M<X, 则所有以X为尾数的数, 经n次F()运算后得到的中间运算结果必定比原数小.
  如, 101>F(F(F(101))), 所以任意形如 XXX101 的数, 有XXX101>F(F(F(XXX101))).


本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复 支持 反对

使用道具 举报

发表于 2011-4-14 18:30:29 | 显示全部楼层
不过我C++ OpenMP版本已经升级了,原来100亿要10秒,现在只需要2秒了……
回复 支持 反对

使用道具 举报

发表于 2011-4-14 22:38:35 | 显示全部楼层
本帖最后由 acme_pjz 于 2011-4-14 22:41 编辑

回复 XOoo 的帖子

C++的2秒不是在我自己电脑上跑的,是在并行计算课程的服务器上跑的服务器是16核64位Linux,程序用了OpenMP实现并行化……必须承认C/C++优化肯定比VB6要好,C/C++自带64位整形类型,而且64位电脑直接支持CPU上64位整形运算,速度肯定不一般快……

我测试了一下你的程序,鉴定结论是并非按顺序算的,因为进度没到50%就出8xxxxxxxxx了……在我电脑上你最新的程序用时160秒……我刚才给我的程序加了一次N步优化,用时变成90秒了,缺点是不能统计最大数了……我的程序还是按顺序算,正在考虑要不要改成按剩余类来算(会快不少,因为外循环可以直接跳过剩余类)……

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

文字版|手机版|小黑屋|VBGood  

GMT+8, 2022-7-1 03:49

VB爱好者乐园(VBGood)
快速回复 返回顶部 返回列表