平方数数字和

无心人 · 发表于 2008-7-11 13:05:36

刚测试的
170后一个结果要240亿以上的筛选
呵呵
上次停在181了
不知道这次能越过181么
估计181以上要过千亿的筛选了

mathe · 发表于 2008-7-11 13:05:50

我觉得对于充分大的数据，应该是会出现0的

无心人 · 发表于 2008-7-11 13:20:42

一个月内是看不到的了
你有强力的机器么
只要1000个亿的运算速度
64位的CPU
512G的内存
那样估计运算一个星期能接近到10^32

无心人 · 发表于 2008-7-11 14:39:14

过了181了
但已经搜索了7个双字的数据了
还没新的数据出现

无心人 · 发表于 2008-7-11 16:47:32

184 057997787999988988979689
187 059668999996988999989969

184和181距离达到了25个多双字
就是说搜索了超过一千个亿的数字的平方
呵呵
恐怖阿

Current: 085297744596832966672384
最后搜索到上面的位置
被我复制Ctrl-C给搞停止了
哈哈
windows下的习惯阿

已经接近了10^23了
呵呵

无心人 · 发表于 2008-7-11 17:00:53

另外
考虑是否以10^6为进位单位
可节约点加法时间
再辅助以SSE2汇编
我想能否增加到原来的搜索速度的两倍呢？
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
不过如果以字为单位，10000为进制
10^32内数字正好是8个字
符合一个128 SSE寄存器的要求
一个加法就搞定了
呵呵

gxqcn · 发表于 2008-7-11 18:45:22

提高速度可以加大每个 LIMB 的位数，比如从当前的4位，提高为6位、8位，甚至更高；
但所需的 table[] 的 size 就相应的迅速增加，
根据先前的经验（比如分段筛素数），太大的数组不利于 CPU cache 的使用，应避免。

反过来，table[] 的 size 缩减也可通过改变数据类型解决，
比如从当前的 UINT32 改为 BYTE，
即便为后者，亦可使每个 LIMB 最大甚至达到64bit，因为 $9 xx log_10(2^64) < 9 xx 20 < 256$。
但是，在32bit OS中，DWORD 与 BYTE 哪个更快？

这个问题似乎很难用 SIMD 加速，难点主要在于有进位问题，想必大家已深有体会。

无心人 · 发表于 2008-7-11 19:10:26

目前x86 CPU
双字快于字节，字节快于字

gxqcn · 发表于 2008-7-14 08:12:05

这是 72# 代码，从上周六下午5:00起运行到今天早上7:30止的输出结果（历时38.5h，强行中断）：

00:00:00.000 X = 1 S = 1
00:00:00.000 X = 4 S = 4
00:00:00.000 X = 9 S = 9
00:00:00.000 X = 7 S = 16
00:00:00.000 X = 13 S = 49
00:00:00.000 X = 10 S = 64
00:00:00.000 X = 16 S = 169
00:00:00.000 X = 19 S = 289
00:00:00.000 X = 18 S = 576
00:00:00.000 X = 22 S = 1849
00:00:00.000 X = 27 S = 3969
00:00:00.000 X = 25 S = 4489
00:00:00.000 X = 31 S = 6889

****** Searched all perfect squares less then 10^4 ******

00:00:00.000 X = 28 S = 17956
00:00:00.000 X = 34 S = 27889
00:00:00.000 X = 36 S = 69696
00:00:00.000 X = 40 S = 97969
00:00:00.000 X = 37 S = 98596
00:00:00.000 X = 43 S = 499849
00:00:00.000 X = 46 S = 698896
00:00:00.000 X = 45 S = 1887876
00:00:00.000 X = 49 S = 2778889
00:00:00.000 X = 52 S = 4999696
00:00:00.000 X = 54 S = 9696996
00:00:00.000 X = 55 S = 19998784
00:00:00.000 X = 58 S = 46689889
00:00:00.000 X = 61 S = 66699889
00:00:00.000 X = 63 S = 79869969

****** Searched all perfect squares less then 10^8 ******

00:00:00.000 X = 64 S = 277788889
00:00:00.000 X = 67 S = 478996996
00:00:00.000 X = 70 S = 876988996
00:00:00.001 X = 73 S = 1749999889
00:00:00.001 X = 72 S = 3679999569
00:00:00.001 X = 76 S = 5599977889
00:00:00.002 X = 79 S = 7998976969
00:00:00.002 X = 81 S = 8998988769
00:00:00.003 X = 82 S = 17999978896
00:00:00.004 X = 85 S = 36799899889
00:00:00.007 X = 88 S = 88998998929
00:00:00.013 X = 90 S = 297889998849
00:00:00.013 X = 91 S = 299879997769
00:00:00.023 X = 94 S = 897977978689
00:00:00.023 X = 97 S = 975979998889

****** Searched all perfect squares less then 10^12 ******

00:00:00.045 X = 100 S = 2699997789889
00:00:00.056 X = 99 S = 3957779999889
00:00:00.094 X = 103 S = 9879498789889
00:00:00.094 X = 106 S = 9998768898889
00:00:00.174 X = 108 S = 29998985899689
00:00:00.303 X = 109 S = 85986989688889
00:00:00.324 X = 112 S = 97888999968769
00:00:00.643 X = 115 S = 386999898769969
00:00:00.680 X = 117 S = 429998989997889
00:00:00.793 X = 118 S = 578889999977689
00:00:00.991 X = 121 S = 898999897988929
00:00:01.446 X = 124 S = 1959999889996996
00:00:01.947 X = 127 S = 3699998989898689
00:00:02.648 X = 126 S = 6788999798879769
00:00:03.409 X = 130 S = 9895699989899689

****** Searched all perfect squares less then 10^16 ******

00:00:07.295 X = 133 S = 38896878989988889
00:00:07.305 X = 136 S = 38999699989995889
00:00:09.770 X = 135 S = 67699789959899889
00:00:16.520 X = 139 S = 188997899869998769
00:00:20.123 X = 142 S = 279869897899999969
00:00:26.869 X = 144 S = 498999778899898896
00:00:37.941 X = 148 S = 989879999979599689
00:00:52.302 X = 145 S = 1877896979979898969
00:01:32.808 X = 153 S = 5899989587897999889
00:01:40.930 X = 151 S = 6979497898999879969
00:01:54.009 X = 154 S = 8899988895999696889
00:03:25.862 X = 157 S = 28979978999958969889
00:05:39.988 X = 160 S = 78897999969769888996
00:05:59.087 X = 162 S = 87989899898866889889

****** Searched all perfect squares less then 10^20 ******

00:09:29.659 X = 163 S = 199989299899788979969
00:14:49.937 X = 166 S = 449998999899988698769
00:20:04.779 X = 171 S = 789899899796987988996
00:22:27.659 X = 169 S = 969988797999759789889
00:44:30.277 X = 172 S = 3599979999987777888889
00:52:09.701 X = 175 S = 4899976999986989889796
01:10:51.428 X = 178 S = 8889998799995887887889
01:14:53.205 X = 180 S = 9899698989999989958489
01:41:50.523 X = 181 S = 17989999975899879969889
03:07:21.670 X = 184 S = 57997787999988988979689
03:10:10.325 X = 187 S = 59668999996988999989969
06:53:10.902 X = 189 S = 289959998978968689899889
10:25:03.810 X = 190 S = 649969889997895999999489
11:56:20.077 X = 193 S = 857799969779899989969889

****** Searched all perfect squares less then 10^24 ******

17:18:44.406 X = 196 S = 1679898987989978888999689
27:16:36.456 X = 198 S = 3899689979989899957996996
30:49:37.180 X = 199 S = 4899999899498984599899889

其中，运行出无心人之前的最大结果 X=187，耗时为：3h10m10.325s

其实，72# 代码还可进一步优化，比如采用将循环展开，用函数指针切换技术。

无心人 · 发表于 2008-7-14 08:19:28

哈哈

你没保存状态阿
多运行的8小时你也不知道
运行到哪里了阿

我是每隔2^32就输出一次当前平方的

这个问题
我觉得应该这么做
一旦遇到结果
就打开文件写进去
再马上关闭，省得文件内容丢失

然后每隔一个阶段，再写一个状态到其他文件
另外，程序增加读状态功能

启动后自动读状态
呵呵

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
另外，不知道linux如何计时和输出？呵呵
GxQ老想知道我的运算时间是多少，嘿嘿

[ 本帖最后由无心人于 2008-7-14 08:25 编辑 ]

账号		自动登录	找回密码
密码			欢迎注册

[擂台] 平方数数字和