平方数数字和

gxqcn · 发表于 2008-7-11 08:44:25

原帖由 无心人 于 2008-7-11 08:09 发表呵呵你看看你程序的mark的全部输出而不是部分结果哦

根据数论知识，一个整数的平方 mod 9 只能为 0、1、4、7 四类，所以其它的本就不应有值。不过，我还是不明白你说的 bug 是什么？

我觉得没有任何问题。下面我将发一个改进版，可以搜索任意大范围内的值，当然，依然是高度优化的。。。

gxqcn · 发表于 2008-7-11 08:47:56

下面的代码可以完全搜索 10^(4*LIMBS) 内的数字：

#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
int main( void )
{
UINT32 table[ TEN_POW4 ];
UINT32 index[ LIMBS + 1 ], value[ LIMBS ], delta[ LIMBS ];
BYTE exist[ 9*4*LIMBS ];
UINT32 * p = table;
UINT32 i, m, s;
UINT32 i2, i3, i4, s2, s3;
HugeCalc::EnableTimer();
HugeCalc::ResetTimer();
for ( i4 = 0; i4 < 10; ++i4 )
{
for ( i3 = 0; i3 < 10; ++i3 )
{
s3 = i4 + i3;
for ( i2 = 0; i2 < 10; ++i2 )
{
s2 = s3 + i2;
for ( i = 0; i < 10; ++i )
{
*p++ = s2 + i;
}
}
}
}
memset( index, 0, sizeof( index ));
memset( value, 0, sizeof( value ));
memset( delta, 0, sizeof( delta ));
memset( exist, 0, sizeof( exist ));
delta[ 0 ] = 1;
m = 0;
for ( ; ; )
{
i = -1;
while ( TEN_POW2 == ++index[ ++i ] )
{
index[ i ] = 0;
}
if ( m < i )
{
m = i;
printf( "\n****** Searched all perfect squares less then 10^%u ******\n\n", 4*m );
if ( LIMBS == i )
{
break;
}
}
s = 0;
for ( i = 0; i <= m; ++i )
{
value[ i ] += delta[ i ];
if ( value[ i ] >= TEN_POW4 )
{ /* 当 i==m 时不会进入，因此时平方根<100^(m+1) */
value[ i ] -= TEN_POW4;
++value[ i + 1 ];
}
s += table[ value[ i ] ];
}
if ( 0 == exist[ s ] )
{
exist[ s ] = 1;
printf( HugeCalc::GetTimerStr( FT_HHMMSS_ms ));
printf( "\tX = %u\t\tS = %u", s, value[ --i ] );
while ( 0 != i )
{
printf( "%04u", value[ --i ] );
}
printf( "\n" );
}
delta[ 0 ] += 2;
i = 0;
while ( delta[ i ] >= TEN_POW4 )
{
delta[ i ] -= TEN_POW4;
++delta[ ++i ];
}
}
printf( "\nComputation took %s\n\n", HugeCalc::GetTimerStr( FT_DOT06SEC_s ) );
return 0;
}

复制代码

gxqcn · 发表于 2008-7-11 08:49:31

运行结果如下：

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.001 X = 10 S = 64 00:00:00.001 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.002 X = 25 S = 4489 00:00:00.002 X = 31 S = 6889 ****** Searched all perfect squares less then 10^4 ****** 00:00:00.002 X = 28 S = 17956 00:00:00.002 X = 34 S = 27889 00:00:00.002 X = 36 S = 69696 00:00:00.003 X = 40 S = 97969 00:00:00.003 X = 37 S = 98596 00:00:00.003 X = 43 S = 499849 00:00:00.003 X = 46 S = 698896 00:00:00.005 X = 45 S = 1887876 00:00:00.005 X = 49 S = 2778889 00:00:00.005 X = 52 S = 4999696 00:00:00.005 X = 54 S = 9696996 00:00:00.006 X = 55 S = 19998784 00:00:00.008 X = 58 S = 46689889 00:00:00.008 X = 61 S = 66699889 00:00:00.008 X = 63 S = 79869969 ****** Searched all perfect squares less then 10^8 ****** 00:00:00.008 X = 64 S = 277788889 00:00:00.010 X = 67 S = 478996996 00:00:00.010 X = 70 S = 876988996 00:00:00.011 X = 73 S = 1749999889 00:00:00.012 X = 72 S = 3679999569 00:00:00.013 X = 76 S = 5599977889 00:00:00.014 X = 79 S = 7998976969 00:00:00.014 X = 81 S = 8998988769 00:00:00.016 X = 82 S = 17999978896 00:00:00.017 X = 85 S = 36799899889 00:00:00.020 X = 88 S = 88998998929 00:00:00.027 X = 90 S = 297889998849 00:00:00.027 X = 91 S = 299879997769 00:00:00.037 X = 94 S = 897977978689 00:00:00.038 X = 97 S = 975979998889 ****** Searched all perfect squares less then 10^12 ****** 00:00:00.060 X = 100 S = 2699997789889 00:00:00.072 X = 99 S = 3957779999889 00:00:00.106 X = 103 S = 9879498789889 00:00:00.108 X = 106 S = 9998768898889 00:00:00.186 X = 108 S = 29998985899689 00:00:00.316 X = 109 S = 85986989688889 00:00:00.337 X = 112 S = 97888999968769 00:00:00.674 X = 115 S = 386999898769969 00:00:00.713 X = 117 S = 429998989997889 00:00:00.835 X = 118 S = 578889999977689 00:00:01.035 X = 121 S = 898999897988929 00:00:01.483 X = 124 S = 1959999889996996 00:00:02.012 X = 127 S = 3699998989898689 00:00:02.753 X = 126 S = 6788999798879769 00:00:03.290 X = 130 S = 9895699989899689 ****** Searched all perfect squares less then 10^16 ****** 00:00:07.093 X = 133 S = 38896878989988889 00:00:07.104 X = 136 S = 38999699989995889 00:00:09.566 X = 135 S = 67699789959899889 00:00:16.382 X = 139 S = 188997899869998769 00:00:20.072 X = 142 S = 279869897899999969 00:00:26.956 X = 144 S = 498999778899898896 00:00:38.234 X = 148 S = 989879999979599689 00:00:52.898 X = 145 S = 1877896979979898969 00:01:34.317 X = 153 S = 5899989587897999889 00:01:42.666 X = 151 S = 6979497898999879969 00:01:56.083 X = 154 S = 8899988895999696889 00:03:30.418 X = 157 S = 28979978999958969889 00:05:47.960 X = 160 S = 78897999969769888996 00:06:07.529 X = 162 S = 87989899898866889889 ****** Searched all perfect squares less then 10^20 ****** Computation took 392.264510 s Press any key to continue

可以把代码中的 LIMBS 适当修改成更大的值，即可搜索更大范围内的数据。想多大都行，反正中途即会输出计算结果

无心人 · 发表于 2008-7-11 09:58:11

我机器在挂着程序运行呢我在外边新结果等回家去贴上来 GxQ的正好和我的相互验证

无心人 · 发表于 2008-7-11 10:04:15

GxQ考虑加上状态保存否？

gxqcn · 发表于 2008-7-11 10:04:52

你可与我的 72# 对比一下，看谁的高效？

gxqcn · 发表于 2008-7-11 10:06:23

原帖由 无心人 于 2008-7-11 10:04 发表 GxQ考虑加上状态保存否？

没有太大必要啊。即便保存状态，也只需保存那几个数组，以及 m 即可（m 也可由 index[] 计算出），所需空间非常小。

gxqcn · 发表于 2008-7-11 10:49:54

从现有数据来看，十个阿拉伯数字仅“0”从未出现于S中，请问，S中可能出现某位数字为“0”吗？对应的最小X=?

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

171 00000000000789899899796987988996 169 00000000000969988797999759789889 172 00000000003599979999987777888889 175 00000000004899976999986989889796 178 00000000008889998799995887887889 180 00000000009899698989999989958489 181 00000000017989999975899879969889

无心人 · 发表于 2008-7-11 11:51:41

呵呵我猜测是木有可能出现0

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

[擂台] 平方数数字和

可以搜索任意大范围的程序

评分