无心人 发表于 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

:lol

一个月内是看不到的了
你有强力的机器么
只要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 哪个更快?:Q:

这个问题似乎很难用 SIMD 加速,难点主要在于有进位问题,想必大家已深有体会。http://www.emath.ac.cn/image/bbs/smiley/34.gif

无心人 发表于 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 编辑 ]
页: 1 2 3 4 5 6 7 8 [9] 10 11 12 13 14 15 16 17 18
查看完整版本: 平方数数字和