平方数数字和

无心人

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

mathe

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

无心人

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

无心人

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

无心人

184 057997787999988988979689 187 059668999996988999989969 184和181距离达到了25个多双字 就是说搜索了超过一千个亿的数字的平方 呵呵 恐怖阿 Current: 085297744596832966672384 最后搜索到上面的位置 被我复制Ctrl-C给搞停止了 哈哈 windows下的习惯阿 已经接近了10^23了 呵呵

无心人

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

gxqcn

提高速度可以加大每个 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 加速，难点主要在于有进位问题，想必大家已深有体会。

无心人

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

gxqcn

这是 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# 代码还可进一步优化，比如采用将循环展开，用函数指针切换技术。

无心人

哈哈 你没保存状态阿 多运行的8小时你也不知道 运行到哪里了阿 我是每隔2^32就输出一次当前平方的 这个问题 我觉得应该这么做 一旦遇到结果 就打开文件写进去 再马上关闭，省得文件内容丢失 然后每隔一个阶段，再写一个状态到其他文件 另外，程序增加读状态功能 启动后自动读状态 呵呵 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 另外，不知道linux如何计时和输出？呵呵 GxQ老想知道我的运算时间是多少，嘿嘿 [ 本帖最后由 无心人 于 2008-7-14 08:25 编辑 ]