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

XOoo · 发表于 2011-4-1 23:32:16

这个怎么比较程序优劣呢？

acme_pjz · 发表于 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]$

XOoo · 发表于 2011-4-3 23:54:27

本帖最后由 XOoo 于 2011-4-4 19:01 编辑

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

Igawk · 发表于 2011-4-4 20:43:58

本帖最后由 Igawk 于 2011-4-4 21:02 编辑

没有测到完成，到30亿左右：

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

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

XOoo · 发表于 2011-4-5 00:40:14

本帖最后由 XOoo 于 2011-4-5 00:40 编辑

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

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

sunfrank · 发表于 2011-4-11 20:22:25

本帖最后由 sunfrank 于 2011-4-12 17:59 编辑

回复八戒2 的帖子

把/2写成*0.5，可以提高效率cpu做除法不如乘法。

八戒2 · 发表于 2011-4-14 11:03:13

过几天要出差，本期准备提前结束了，谢参加的发送源到到163那个邮箱，谢谢

XOoo · 发表于 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))).

acme_pjz · 发表于 2011-4-14 18:30:29

不过我C++ OpenMP版本已经升级了，原来100亿要10秒，现在只需要2秒了

……

acme_pjz · 发表于 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秒了，缺点是不能统计最大数了

……我的程序还是按顺序算，正在考虑要不要改成按剩余类来算（会快不少，因为外循环可以直接跳过剩余类）……

		自动登录	找回密码
密码			立即注册

VBGood网站全文搜索

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

本帖子中包含更多资源

本帖子中包含更多资源

点评

本帖子中包含更多资源

本帖子中包含更多资源