数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 编程擂台 › 平方数数字和
1 ...67891011121314... 18下一页
返回列表 发新帖
楼主: mathe

[擂台] 平方数数字和

[复制链接]
gxqcn
发表于 2008-7-14 08:27:20 | 显示全部楼层
原帖由 无心人 于 2008-7-14 08:19 发表 哈哈 你没保存状态阿 多运行的8小时你也不知道 运行到哪里了阿 我是每隔2^32就输出一次当前平方的
我没有服务器，不打算继续算下去，所以就没打算输出中间的状态。 其实这个算法计算量规模是容易估算的，当时我就知道 LIMBS 可大于 6，但不需超过 7。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2008-7-14 08:29:09 | 显示全部楼层
28位是可达到的 32位是遥远的
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2008-7-14 08:49:07 | 显示全部楼层
0.000000 1 0001 0.000129 4 0004 0.000145 9 0009 0.000154 7 0016 0.000163 13 0049 0.000171 10 0064 0.000180 16 0169 0.000189 19 0289 0.000198 18 0576 0.000207 22 1849 0.000217 27 3969 0.000226 25 4489 0.000235 31 6889 0.000246 28 00017956 0.000256 34 00027889 0.000267 36 00069696 0.000278 40 00097969 0.000287 37 00098596 0.000303 43 00499849 0.000315 46 00698896 0.000334 45 01887876 0.000349 49 02778889 0.000368 52 04999696 0.000390 54 09696996 0.000423 55 19998784 0.000468 58 46689889 0.000498 61 66699889 0.000521 63 79869969 0.000672 64 000277788889 0.000870 67 000478996996 0.001167 70 000876988996 0.001618 73 001749999889 0.002303 72 003679999569 0.002822 76 005599977889 0.003697 79 007998976969 0.003832 81 008998988769 0.004998 82 017999978896 0.006259 85 036799899889 0.008983 88 088998998929 0.024296 90 297889998849 0.024491 91 299879997769 0.071820 94 897977978689 0.072875 97 975979998889 0.108861 100 0002699997789889 0.118461 99 0003957779999889 0.240214 103 0009879498789889 0.240772 106 0009998768898889 0.409552 108 0029998985899689 0.690780 109 0085986989688889 0.785017 112 0097888999968769 1.331215 115 0386999898769969 1.434825 117 0429998989997889 1.657168 118 0578889999977689 1.983984 121 0898999897988929 2.869437 124 1959999889996996 3.850002 127 3699998989898689 5.131660 126 6788999798879769 6.460858 130 9895699989899689 12.925727 133 00038896878989988889 12.961732 136 00038999699989995889 16.786534 135 00067699789959899889 27.896467 139 00188997899869998769 33.394664 142 00279869897899999969 43.629142 144 00498999778899898896 61.863666 148 00989879999979599689 85.523343 145 01877896979979898969 156.117377 153 05899989587897999889 167.352661 151 06979497898999879969 呵呵，修改的GxQ的代码，时间在数量级上和他一样 但我是P4 2.0 CPU / 1280M /Ubuntu 8.04 机器慢些
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
 楼主| 发表于 2008-7-14 09:21:41 | 显示全部楼层
原帖由 无心人 于 2008-7-14 08:19 发表 ... 另外，不知道linux如何计时和输出？呵呵 GxQ老想知道我的运算时间是多少，嘿嘿
Linux里面C代码可以调用clock()命令比较精确的计算当前程序运行的时间. 而输出很简单呀,你可以重定向输出结果到一个文件里面就可以了(在代码中每次输出后面最好添加一个fflush(stdout)) 而如果只需要统计整个程序的运行时间,在命令行对使用命令前面添加time命令就可以了,如 \$time ./your_prog.out input_parameter_list
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2008-7-14 10:00:48 | 显示全部楼层
呵呵，找到一个gettimeofday调用，是微秒级的精度 挺好用的 另外，刚下载了intel c++ 10.1.017 优化后，速度提升特明显
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
发表于 2008-7-14 10:02:49 | 显示全部楼层

我的终极优化的代码

实现了我先前的一些想法，在计算 X = 162 时，已比 72# 的快了 50%！
推荐
  1. #include < stdlib.h >
  2. #include < stdio.h >
  4. #include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h" // 公共接口
  6. #pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
  7. #pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
  10. #define TEN_POW2 100UL
  11. #define TEN_POW4 10000UL
  13. #define LIMBS 5
  15. UINT32 m, s;
  17. #ifdef __INTEL_COMPILER
  18. # undef LIMBS
  19. # define LIMBS 8
  20. __declspec(align(16))
  21. #endif
  22. UINT32 pool[ TEN_POW4 + LIMBS * 39 ];
  24. #define table(x) pool[x]
  25. #define value(x) pool[(x) + TEN_POW4]
  26. #define delta(x) pool[(x) + TEN_POW4 + LIMBS]
  27. #define index(x) pool[(x) + TEN_POW4 + LIMBS * 2]
  28. #define exist(x) pool[(x) + TEN_POW4 + LIMBS * 3]
  30. void init( void )
  31. {
  32. UINT32 i1, i2, i3, i4;
  33. UINT32 * p = &table(0) - 1;
  35. memset( pool, 0, sizeof( pool ));
  37. for ( i1 = 0; i1 < 10; ++i1 )
  38. {
  39. for ( i2 = 0; i2 < 10; ++i2 )
  40. {
  41. for ( i3 = 0; i3 < 10; ++i3 )
  42. {
  43. for ( i4 = 0; i4 < 10; ++i4 )
  44. {
  45. *(++p) = i1 + i2 + i3 + i4;
  46. }
  47. }
  48. }
  49. }
  50. }
  53. #define add_value(x) value(x) += delta(x)
  54. #define mod_value(x) if ( value(x) >= TEN_POW4 ){ value(x) -= TEN_POW4; ++value(x+1); }
  55. #define lookup(x) table( value(x) )
  57. void sumOfDigits( void )
  58. {
  59. s = 0;
  60. for ( UINT32 i = 0; i <= m; ++i )
  61. {
  62. add_value(i);
  63. mod_value(i); /* 当 i==m 时不会进入 if，因此时平方根<100^(m+1) */
  65. s += lookup(i);
  66. }
  67. }
  69. void sumOfDigits_1( void )
  70. {
  71. add_value(0);
  73. s = lookup(0);
  74. }
  76. void sumOfDigits_2( void )
  77. {
  78. add_value(0);
  79. add_value(1);
  81. mod_value(0);
  83. s = lookup(0) + lookup(1);
  84. }
  86. void sumOfDigits_3( void )
  87. {
  88. add_value(0);
  89. add_value(1);
  90. add_value(2);
  92. mod_value(0);
  93. mod_value(1);
  95. s = lookup(0) + lookup(1) + lookup(2);
  96. }
  98. void sumOfDigits_4( void )
  99. {
  100. add_value(0);
  101. add_value(1);
  102. add_value(2);
  103. add_value(3);
  105. mod_value(0);
  106. mod_value(1);
  107. mod_value(2);
  109. s = lookup(0) + lookup(1) + lookup(2) + lookup(3);
  110. }
  112. void sumOfDigits_5( void )
  113. {
  114. add_value(0);
  115. add_value(1);
  116. add_value(2);
  117. add_value(3);
  118. add_value(4);
  120. mod_value(0);
  121. mod_value(1);
  122. mod_value(2);
  123. mod_value(3);
  125. s = lookup(0) + lookup(1) + lookup(2) + lookup(3) \
  126. + lookup(4);
  127. }
  129. void sumOfDigits_6( void )
  130. {
  131. add_value(0);
  132. add_value(1);
  133. add_value(2);
  134. add_value(3);
  135. add_value(4);
  136. add_value(5);
  138. mod_value(0);
  139. mod_value(1);
  140. mod_value(2);
  141. mod_value(3);
  142. mod_value(4);
  144. s = lookup(0) + lookup(1) + lookup(2) + lookup(3) \
  145. + lookup(4) + lookup(5);
  146. }
  148. void sumOfDigits_7( void )
  149. {
  150. add_value(0);
  151. add_value(1);
  152. add_value(2);
  153. add_value(3);
  154. add_value(4);
  155. add_value(5);
  156. add_value(6);
  158. mod_value(0);
  159. mod_value(1);
  160. mod_value(2);
  161. mod_value(3);
  162. mod_value(4);
  163. mod_value(5);
  165. s = lookup(0) + lookup(1) + lookup(2) + lookup(3) \
  166. + lookup(4) + lookup(5) + lookup(6);
  167. }
  169. void sumOfDigits_8( void )
  170. {
  171. add_value(0);
  172. add_value(1);
  173. add_value(2);
  174. add_value(3);
  175. add_value(4);
  176. add_value(5);
  177. add_value(6);
  178. add_value(7);
  180. mod_value(0);
  181. mod_value(1);
  182. mod_value(2);
  183. mod_value(3);
  184. mod_value(4);
  185. mod_value(5);
  186. mod_value(6);
  188. s = lookup(0) + lookup(1) + lookup(2) + lookup(3) \
  189. + lookup(4) + lookup(5) + lookup(6) + lookup(7);
  190. }
  192. typedef void ( *lpfnSumOfDigits )( void );
  194. lpfnSumOfDigits lpfn[ ] = { sumOfDigits, sumOfDigits_1, sumOfDigits_2, sumOfDigits_3, \
  195. sumOfDigits_4, sumOfDigits_5, sumOfDigits_6, sumOfDigits_7, sumOfDigits_8 };
  197. int main( void )
  198. {
  199. UINT32 i;
  200. lpfnSumOfDigits SumOfDigits = lpfn[ 1 ];
  202. HugeCalc::EnableTimer();
  203. HugeCalc::ResetTimer();
  205. init();
  207. index(0) = 1;
  208. delta(0) = -1;
  209. m = 0;
  210. for ( ; ; )
  211. {
  212. delta(0) += 2;
  213. if ( delta(0) > TEN_POW4 )
  214. {
  215. delta(0) = 1;
  217. i = 0;
  218. while ( TEN_POW4 == ++delta(++i) )
  219. {
  220. delta(i) = 0;
  221. }
  222. }
  224. SumOfDigits();
  226. if ( 0 == exist(s) )
  227. {
  228. exist(s) = 1;
  230. printf( HugeCalc::GetTimerStr( FT_HHMMSS_ms ));
  231. printf( "\tX = %u\t\tS = %u", s, value( i = m ) );
  232. while ( 0 != i )
  233. {
  234. printf( "%04u", value(--i) );
  235. }
  236. printf( "\n" );
  237. }
  240. i = -1;
  241. while ( TEN_POW2 == ++index(++i) )
  242. {
  243. index(i) = 0;
  244. }
  246. if ( m < i )
  247. {
  248. m = i;
  250. printf( "\n****** %s: Searched all perfect squares less then 10^%u ******\n\n", HugeCalc::GetTimerStr( FT_DOT06SECs ), 4*m );
  252. if ( LIMBS == i )
  253. {
  254. break;
  255. }
  257. #if ( LIMBS > 8 )
  258. if ( m + 1 >= sizeof( lpfn ) / sizeof( lpfn[0] ))
  259. {
  260. SumOfDigits = lpfn[ 0 ];
  261. }
  262. else
  263. #endif
  264. {
  266. SumOfDigits = lpfn[ m + 1 ];
  267. }
  268. }
  269. else if ( i == m && 10 == index(m) )
  270. {
  271. printf( "\n****** %s: Searched all perfect squares less then 10^%u ******\n\n", HugeCalc::GetTimerStr( FT_DOT06SECs ), 4*m + 2 );
  272. }
  273. }
  276. printf( "\nComputation took %s\n\n", HugeCalc::GetTimerStr( FT_DOT06SEC_s ) );
  278. system( "pause" );
  280. return 0;
  281. }
复制代码
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2008-7-14 10:03:56 | 显示全部楼层
0.000004: 1 1 0.000121: 4 4 0.000132: 9 9 0.000140: 7 16 0.000149: 13 49 0.000157: 10 64 0.000165: 16 169 0.000173: 19 289 0.000181: 18 576 0.000190: 22 1849 0.000198: 27 3969 0.000206: 25 4489 0.000215: 31 6889 0.000223: 28 17956 0.000232: 34 27889 0.000242: 36 69696 0.000251: 40 97969 0.000260: 37 98596 0.000274: 43 499849 0.000284: 46 698896 0.000300: 45 1887876 0.000313: 49 2778889 0.000330: 52 4999696 0.000350: 54 9696996 0.000379: 55 19998784 0.000418: 58 46689889 0.000445: 61 66699889 0.000465: 63 79869969 0.000600: 64 277788889 0.000696: 67 478996996 0.000835: 70 876988996 0.001048: 73 1749999889 0.001372: 72 3679999569 0.001621: 76 5599977889 0.002040: 79 7998976969 0.002164: 81 8998988769 0.002986: 82 17999978896 0.004208: 85 36799899889 0.006426: 88 88998998929 0.016116: 90 297889998849 0.016196: 91 299879997769 0.049611: 94 897977978689 0.050550: 97 975979998889 0.092371: 100 2699997789889 0.109283: 99 3957779999889 0.168103: 103 9879498789889 0.168708: 106 9998768898889 0.262466: 108 29998985899689 0.411295: 109 85986989688889 0.431866: 112 97888999968769 0.779954: 115 386999898769969 0.839113: 117 429998989997889 0.961269: 118 578889999977689 1.162582: 121 898999897988929 1.656253: 124 1959999889996996 2.180752: 127 3699998989898689 3.101664: 126 6788999798879769 3.674470: 130 9895699989899689 7.287076: 133 38896878989988889 7.294342: 136 38999699989995889 9.633264: 135 67699789959899889 16.111251: 139 188997899869998769 19.601210: 142 279869897899999969 26.191958: 144 498999778899898896 36.927668: 148 989879999979599689 50.888507: 145 1877896979979898969 90.289988: 153 5899989587897999889 98.299096: 151 6979497898999879969 和上面对比，发现速度提升明显，且编译提示发现可向量化的代码了 编译命令是 icc -fast -msse2
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
发表于 2008-7-14 10:04:05 | 显示全部楼层

运行结果

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 ****** 0.000901s: Searched all perfect squares less then 10^2 ****** 00:00:00.000 X = 16 S = 169 00:00:00.001 X = 19 S = 289 00:00:00.001 X = 18 S = 576 00:00:00.001 X = 22 S = 1849 00:00:00.001 X = 27 S = 3969 00:00:00.001 X = 25 S = 4489 00:00:00.001 X = 31 S = 6889 ****** 0.001846s: Searched all perfect squares less then 10^4 ****** 00:00:00.001 X = 28 S = 17956 00:00:00.001 X = 34 S = 27889 00:00:00.001 X = 36 S = 69696 00:00:00.002 X = 40 S = 97969 00:00:00.002 X = 37 S = 98596 00:00:00.002 X = 43 S = 499849 00:00:00.002 X = 46 S = 698896 ****** 0.002744s: Searched all perfect squares less then 10^6 ****** 00:00:00.002 X = 45 S = 1887876 00:00:00.003 X = 49 S = 2778889 00:00:00.003 X = 52 S = 4999696 00:00:00.003 X = 54 S = 9696996 00:00:00.003 X = 55 S = 19998784 00:00:00.003 X = 58 S = 46689889 00:00:00.003 X = 61 S = 66699889 00:00:00.003 X = 63 S = 79869969 ****** 0.003801s: Searched all perfect squares less then 10^8 ****** 00:00:00.003 X = 64 S = 277788889 00:00:00.004 X = 67 S = 478996996 00:00:00.004 X = 70 S = 876988996 00:00:00.004 X = 73 S = 1749999889 00:00:00.005 X = 72 S = 3679999569 00:00:00.006 X = 76 S = 5599977889 00:00:00.006 X = 79 S = 7998976969 00:00:00.006 X = 81 S = 8998988769 ****** 0.006982s: Searched all perfect squares less then 10^10 ****** 00:00:00.007 X = 82 S = 17999978896 00:00:00.008 X = 85 S = 36799899889 00:00:00.010 X = 88 S = 88998998929 00:00:00.014 X = 90 S = 297889998849 00:00:00.014 X = 91 S = 299879997769 00:00:00.020 X = 94 S = 897977978689 00:00:00.021 X = 97 S = 975979998889 ****** 0.022476s: Searched all perfect squares less then 10^12 ****** 00:00:00.033 X = 100 S = 2699997789889 00:00:00.039 X = 99 S = 3957779999889 00:00:00.059 X = 103 S = 9879498789889 00:00:00.059 X = 106 S = 9998768898889 00:00:00.100 X = 108 S = 29998985899689 00:00:00.169 X = 109 S = 85986989688889 00:00:00.182 X = 112 S = 97888999968769 ****** 0.185879s: Searched all perfect squares less then 10^14 ****** 00:00:00.367 X = 115 S = 386999898769969 00:00:00.386 X = 117 S = 429998989997889 00:00:00.450 X = 118 S = 578889999977689 00:00:00.556 X = 121 S = 898999897988929 00:00:00.822 X = 124 S = 1959999889996996 00:00:01.143 X = 127 S = 3699998989898689 00:00:01.546 X = 126 S = 6788999798879769 00:00:01.859 X = 130 S = 9895699989899689 ****** 1.867877s: Searched all perfect squares less then 10^16 ****** 00:00:03.942 X = 133 S = 38896878989988889 00:00:03.948 X = 136 S = 38999699989995889 00:00:05.279 X = 135 S = 67699789959899889 00:00:08.984 X = 139 S = 188997899869998769 00:00:10.970 X = 142 S = 279869897899999969 00:00:14.728 X = 144 S = 498999778899898896 00:00:20.848 X = 148 S = 989879999979599689 ****** 20.955593s: Searched all perfect squares less then 10^18 ****** 00:00:28.825 X = 145 S = 1877896979979898969 00:00:51.330 X = 153 S = 5899989587897999889 00:00:55.840 X = 151 S = 6979497898999879969 00:01:03.080 X = 154 S = 8899988895999696889 00:01:54.156 X = 157 S = 28979978999958969889 00:03:10.483 X = 160 S = 78897999969769888996 00:03:21.335 X = 162 S = 87989899898866889889 ****** 214.569824s: Searched all perfect squares less then 10^20 ****** Computation took 214.570197 s 请按任意键继续. . .
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2008-7-14 10:07:53 | 显示全部楼层
你新写的代码等于是给手工展开了吧？？？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
发表于 2008-7-14 10:11:30 | 显示全部楼层
也可以这么说， 我不太相信编译器的优化能力。 注：我用的是 VC6，没有用 ICC 编译器。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

1 ...67891011121314... 18下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-11-21 20:37 , Processed in 0.033477 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表