平方数数字和

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%！

#include < stdlib.h >
#include < stdio.h >
#include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h" // 公共接口
#pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
#pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
#define TEN_POW2 100UL
#define TEN_POW4 10000UL
#define LIMBS 5
UINT32 m, s;
#ifdef __INTEL_COMPILER
# undef LIMBS
# define LIMBS 8
__declspec(align(16))
#endif
UINT32 pool[ TEN_POW4 + LIMBS * 39 ];
#define table(x) pool[x]
#define value(x) pool[(x) + TEN_POW4]
#define delta(x) pool[(x) + TEN_POW4 + LIMBS]
#define index(x) pool[(x) + TEN_POW4 + LIMBS * 2]
#define exist(x) pool[(x) + TEN_POW4 + LIMBS * 3]
void init( void )
{
UINT32 i1, i2, i3, i4;
UINT32 * p = &table(0) - 1;
memset( pool, 0, sizeof( pool ));
for ( i1 = 0; i1 < 10; ++i1 )
{
for ( i2 = 0; i2 < 10; ++i2 )
{
for ( i3 = 0; i3 < 10; ++i3 )
{
for ( i4 = 0; i4 < 10; ++i4 )
{
*(++p) = i1 + i2 + i3 + i4;
}
}
}
}
}
#define add_value(x) value(x) += delta(x)
#define mod_value(x) if ( value(x) >= TEN_POW4 ){ value(x) -= TEN_POW4; ++value(x+1); }
#define lookup(x) table( value(x) )
void sumOfDigits( void )
{
s = 0;
for ( UINT32 i = 0; i <= m; ++i )
{
add_value(i);
mod_value(i); /* 当 i==m 时不会进入 if，因此时平方根<100^(m+1) */
s += lookup(i);
}
}
void sumOfDigits_1( void )
{
add_value(0);
s = lookup(0);
}
void sumOfDigits_2( void )
{
add_value(0);
add_value(1);
mod_value(0);
s = lookup(0) + lookup(1);
}
void sumOfDigits_3( void )
{
add_value(0);
add_value(1);
add_value(2);
mod_value(0);
mod_value(1);
s = lookup(0) + lookup(1) + lookup(2);
}
void sumOfDigits_4( void )
{
add_value(0);
add_value(1);
add_value(2);
add_value(3);
mod_value(0);
mod_value(1);
mod_value(2);
s = lookup(0) + lookup(1) + lookup(2) + lookup(3);
}
void sumOfDigits_5( void )
{
add_value(0);
add_value(1);
add_value(2);
add_value(3);
add_value(4);
mod_value(0);
mod_value(1);
mod_value(2);
mod_value(3);
s = lookup(0) + lookup(1) + lookup(2) + lookup(3) \
+ lookup(4);
}
void sumOfDigits_6( void )
{
add_value(0);
add_value(1);
add_value(2);
add_value(3);
add_value(4);
add_value(5);
mod_value(0);
mod_value(1);
mod_value(2);
mod_value(3);
mod_value(4);
s = lookup(0) + lookup(1) + lookup(2) + lookup(3) \
+ lookup(4) + lookup(5);
}
void sumOfDigits_7( void )
{
add_value(0);
add_value(1);
add_value(2);
add_value(3);
add_value(4);
add_value(5);
add_value(6);
mod_value(0);
mod_value(1);
mod_value(2);
mod_value(3);
mod_value(4);
mod_value(5);
s = lookup(0) + lookup(1) + lookup(2) + lookup(3) \
+ lookup(4) + lookup(5) + lookup(6);
}
void sumOfDigits_8( void )
{
add_value(0);
add_value(1);
add_value(2);
add_value(3);
add_value(4);
add_value(5);
add_value(6);
add_value(7);
mod_value(0);
mod_value(1);
mod_value(2);
mod_value(3);
mod_value(4);
mod_value(5);
mod_value(6);
s = lookup(0) + lookup(1) + lookup(2) + lookup(3) \
+ lookup(4) + lookup(5) + lookup(6) + lookup(7);
}
typedef void ( *lpfnSumOfDigits )( void );
lpfnSumOfDigits lpfn[ ] = { sumOfDigits, sumOfDigits_1, sumOfDigits_2, sumOfDigits_3, \
sumOfDigits_4, sumOfDigits_5, sumOfDigits_6, sumOfDigits_7, sumOfDigits_8 };
int main( void )
{
UINT32 i;
lpfnSumOfDigits SumOfDigits = lpfn[ 1 ];
HugeCalc::EnableTimer();
HugeCalc::ResetTimer();
init();
index(0) = 1;
delta(0) = -1;
m = 0;
for ( ; ; )
{
delta(0) += 2;
if ( delta(0) > TEN_POW4 )
{
delta(0) = 1;
i = 0;
while ( TEN_POW4 == ++delta(++i) )
{
delta(i) = 0;
}
}
SumOfDigits();
if ( 0 == exist(s) )
{
exist(s) = 1;
printf( HugeCalc::GetTimerStr( FT_HHMMSS_ms ));
printf( "\tX = %u\t\tS = %u", s, value( i = m ) );
while ( 0 != i )
{
printf( "%04u", value(--i) );
}
printf( "\n" );
}
i = -1;
while ( TEN_POW2 == ++index(++i) )
{
index(i) = 0;
}
if ( m < i )
{
m = i;
printf( "\n****** %s: Searched all perfect squares less then 10^%u ******\n\n", HugeCalc::GetTimerStr( FT_DOT06SECs ), 4*m );
if ( LIMBS == i )
{
break;
}
#if ( LIMBS > 8 )
if ( m + 1 >= sizeof( lpfn ) / sizeof( lpfn[0] ))
{
SumOfDigits = lpfn[ 0 ];
}
else
#endif
{
SumOfDigits = lpfn[ m + 1 ];
}
}
else if ( i == m && 10 == index(m) )
{
printf( "\n****** %s: Searched all perfect squares less then 10^%u ******\n\n", HugeCalc::GetTimerStr( FT_DOT06SECs ), 4*m + 2 );
}
}
printf( "\nComputation took %s\n\n", HugeCalc::GetTimerStr( FT_DOT06SEC_s ) );
system( "pause" );
return 0;
}

复制代码

无心人 · 发表于 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 编译器。

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

[擂台] 平方数数字和

我的终极优化的代码

运行结果