我的可以计算更大的 :)
我用类似快速乘幂的算法，消除了递归，效率大幅提升：:)r = 1000 耗时：0.000062 s 位数：765r = 10000 耗时：0.001045 s 位数：7655
r = 100000 耗时：0.028692 s 位数：76555
r = 1000000 耗时：0.362074 s 位数：765551
r = 10000000 耗时：3.179194 s 位数：7655514
测试环境：Windows XP SP2，AMD Athlon 64 Processor 3200+，1GB DDR - 200MHz代码如下：#include < iostream.h >
#include < HugeCalc.h > // 公共接口
#include < HugeInt.h >// 10进制系统
#include < HugeIntX.h > // 16进制系统
#pragma message( "automatic link to .../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
#pragma comment( lib, "HugeCalc.lib" )
int main(int argc, char* argv[])
{
cout << "Call " << HugeCalc::GetVer() << endl;
if ( HC_LICENSE_NONE == HugeCalc::GetLicenseLevel() )
{
cout << "\r\n警告：您未通过 HugeCalc.dll 的许可认证！\r\n" \
<< "\r\n解决方案可选下列方案之一：" \
<< "\r\n 一、请将本程序移动到“/CopyrightByGuoXianqiang/[../]”目录下运行；" \
<< "\r\n 二、或请在 HugeCalc.chm 中进行注册（一劳永逸）。" \
<< endl;
}
else
{
CHugeInt a, b, k;
UINT32 i, r;
cout << "*** ^r = sqrt(k) - sqrt(k-1) ***"<< endl;
cout << "input r, output k ...(if r==0, then exit)" << endl;
for ( ; ; )
{
cout << endl << "r = ";
cin >> r;
if ( 0 == r ) break;
HugeCalc::EnableTimer();
HugeCalc::ResetTimer();
// a + b*sqrt(2)
a = 1;
b = -1;
i = 1;
while ( i <= r )
{
i <<= 1;
}
i >>= 1;
while ( 1 != i )
{
k.Mul( a, b ) <<= 1;
a.Pow(2) += ( b.Pow(2) <<= 1 );
b.Swap(k);
if ( 0 != ( r & ( i >>= 1 )))
{
( k = b ).Negate();
b -= a;
a.Swap( k ) -= b;
}
}
if ( 0 == ( 1 & r ))
{
k.Swap(a).Pow(2);
}
else
{
k.Swap(b).Pow(2) <<= 1;
}
HugeCalc::EnableTimer( FALSE );
#if 1 // 设“0”可关闭输出具体数值
cout << "k = " << k.GetStr(FS_NORMAL) << endl;
#else
cout << "k have " << k.GetDigits() << " digits!" << endl;
#endif
cout << "computation took " << HugeCalc::GetTimerStr() << endl;
}
}
cout << endl;
system( "pause" );
return 0;
}编译好的程序压缩包：再次证明 HugeCalc 比 GMP 更优越！（注：非 HugeCalc 注册用户也可正常运行） 呵呵，程序运行结果输出太花时间了，
我在我的笔记本上运行
1,000,000计算时间是1.322009 s，不过输出好像花了更长的时间。
10,000,000的情况竟然也能够算下去，计算时间是16.754020s. 原帖由 mathe 于 2008-1-24 15:49 发表 http://bbs.emath.ac.cn/images/common/back.gif
呵呵，程序运行结果输出太花时间了，
我在我的笔记本上运行
1,000,000计算时间是1.322009 s，不过输出好像花了更长的时间。
10,000,000的情况竟然也能够算下去，计算时间是16.754020s.
这不是我的程序吧？（在我印象中，你的笔记本速度比我的台式机速度还要好）
我的输出也会很快的。 是你的程序。
如果不重定向，输出应该没有办法提高速度吧，比如r=10,000,000
显示的计算时间只有1.3秒左右，可是整个输出过程，我就看见窗口中白花花一片数字在向上闪去，闪了1分多钟，
你是不是运行时将输出重定向了？ 对照 14# 与 12# 的描述，感觉在12# 中的“r”值均少打了个“0”，
所以我才会有所疑惑。
我没有重定向输出，但由于不存在复杂的进制转换，所以 HugeCalc 输出会很高效，
如果不想输出具体数值，可把我在 11# 中源代码的“#if 1”改成“#if 0”即可。 不是进制转换问题，只是纯粹屏幕输入输出问题。12#的确少了个0
通常我都在Linux上面写代码的，所以没有去编译你的代码，而是直接在笔记本上运行你编译后的程序。 屏幕输出确实比较耗时。http://www.emath.ac.cn/image/bbs/smiley/57.gif
我重定向输出到文件测试，所耗时间也只是秒级。
“终极”版本 :)
下面对该问题进行理论推导并尝试推广。为叙述方便，记 sqrt(2)=j，
巧妙的推导，高效的算法，严谨的代码数 (a + b*j) 中 a 可称为“有理部”，b 可称为“无理部”。
则 r=0 时，(j-1)^r = (j+1)^(-r) = 1 ± 0*j
当 r>0 时，(j-1)^r = (j+1)^(-r) = ar - br*j= sqrt( kr ) - sqrt( kr - 1 )
当 r<0 时，(j-1)^r = (j+1)^(-r) = ar + br*j = sqrt( kr ) + sqrt( kr - 1 )
楼主所要求的 k = max{ ar^2, 2*br^2 }，更一般地：
当 r 为偶数时，kr = ar^2；当 r 为奇数时 kr = 2*br^2
从以上等式可看出，(j-1)^r、(j+1)^r、(j-1)^(-r)、(j+1)^(-r) 的 kr 值彼此相等。
（因为它们的“有理部”、“无理部”绝对值彼此相等）
有了这个结论就好办了，甚至可为下一步程序优化作理论指导，
因为大数同号加法更简单，所以我们尽可能采用“有理部”与“无理部”同号之情形。
(1+j)*(a + b*j) = (a+2*b) + (a+b)*j => br+1 = ar + br, ar+1 = br+1 + br
(a + b*j)^2 = (a^2 + 2*b^2) + 2*a*b*j => a2r = ar^2 + 2*br^2, b2r = 2*ar*br
注意到 ar^2 - 2*br^2 = ±1，所以 a2r 的计算可以少算一次平方。
更好的结论则为 a2r = 2*kr - 1
于是乎，就有了下面的优化算法：//////////////////////////////////////////////////////////////////////////
//
// 目的：快速计算 (sqrt(2) - 1)^r
// 设计：郭先强 ( gxqcn@163.com; HugeCalc@Gmail.com )
// 日期：2008-01-24
// 备注：运行编译好的程序，后面若带参数则输出到文件 Output.txt 中
//
// Web: http://www.emath.ac.cn/
// BBS: http://bbs.emath.ac.cn/
//
//////////////////////////////////////////////////////////////////////////
// Project -> Setting -> C/C++ -> Code Generation --> Use run-time library:
// Win32 Debug: Debug Multithreaded DLL
// Win32 Release:Multithreaded DLL
#include < iostream.h >
#include < fstream.h >
#include < HugeCalc.h > // 公共接口
#include < HugeInt.h >// 10进制系统
#include < HugeIntX.h > // 16进制系统
#pragma message( "automatic link to .../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
#pragma comment( lib, "HugeCalc.lib" )
int main(int argc, char* argv[])
{
cout << "Call " << HugeCalc::GetVer() << endl << endl;
if ( HC_LICENSE_NONE == HugeCalc::GetLicenseLevel() )
{
cout << "\r\n警告：您未通过 HugeCalc.dll 的许可认证！\r\n" \
<< "\r\n解决方案可选下列方案之一：" \
<< "\r\n 一、请将本程序移动到“/CopyrightByGuoXianqiang/[../]”目录下运行；" \
<< "\r\n 二、或请在 HugeCalc.chm 中进行注册（一劳永逸）。" \
<< endl;
}
else
{
#if 1 // 用10进制内核
CHugeInt a, b, k;
#else // 用16进制内核
CHugeIntX a, b, k;
#endif
SINT32 r; // r 可正可负
BOOL bSave2File = ( argc > 1 ); // 后面若有参数则存盘
cout << "*** ^r = sqrt(k) - sqrt(k-1) ***" << endl;
cout << "input r, output k ...(if r==0, then exit)" << endl;
for ( ; ; )
{
cout << endl << "r = ";
cin >> r;
if ( 0 == r )
{
cout << "k = 1" << endl;
break;
}
if ( r < 0 ) r = -r;
HugeCalc::EnableTimer();
HugeCalc::ResetTimer();
// a + b*sqrt(2)
a = 1;
b = 1;
k = 2;
UINT32 i = 1UL << 31;
while ( i > (UINT32)r )
{
i >>= 1;
}
while ( 0 != ( r & ( i - 1 )))
{
( b *= a ) <<= 1;
--( a.Swap( k ) <<= 1 );
if ( 0 != ( r & ( i >>= 1 )))
{
k = b;
b += a;
a.Swap( k ) += b;
( k = b ).Pow( 2 ) <<= 1;
}
else
{
( k = a ).Pow( 2 );
}
}
// 变量 a,b 不再使用，清空其所占资源
a = b = 0;
while ( 1 != i )
{
( --( k <<= 1 )).Pow( 2 );
i >>= 1;
}
HugeCalc::EnableTimer( FALSE );
if ( bSave2File )
{
ofstream outputFile( "Output.txt", ios::ate );
if ( outputFile )
{
outputFile << endl;
outputFile << "r = " << r << endl;
outputFile << "k = " << k.GetStr( FS_NORMAL ) << endl;
outputFile << "*** k have " << k.GetDigits() << " digits! ***" << endl;
outputFile << "computation took " << HugeCalc::GetTimerStr() << endl;
outputFile.close();
}
else
{
cerr << "File could not be opened" << endl;
bSave2File = FALSE;
}
}
if ( !bSave2File )
{
cout << "k = " << k.GetStr( FS_NORMAL ) << endl;
}
cout << "*** k have " << k.GetDigits() << " digits! ***" << endl;
cout << "computation took " << HugeCalc::GetTimerStr() << endl;
}
}
cout << endl;
system( "pause" );
return 0;
}编译好的程序压缩包：（无论注册 HugeCalc 与否均可正常运行；可存盘输出；内含源代码）
“终极版”的测试报告
调用 HugeCalc 的 10 进制内核版本：r = 1000 耗时：0.000048 s 位数：765
r = 10000 耗时：0.000632 s 位数：7655
r = 100000 耗时：0.012068 s 位数：76555
r = 1000000 耗时：0.236285 s 位数：765551
r = 10000000 耗时：1.586116 s 位数：7655514
r = 100000000 耗时：19.850545 s 位数：76555137
调用 HugeCalc 的 16 进制内核版本：
r = 1000 耗时：0.000067 s 位数：636
r = 10000 耗时：0.000379 s 位数：6358
r = 100000 耗时：0.021730 s 位数：63578
r = 1000000 耗时：0.227757 s 位数：635777
r = 10000000 耗时：1.378083 s 位数：6357767
r = 100000000 耗时：19.163445 s 位数：63577665
测试环境：Windows XP SP2，AMD Athlon 64 Processor 3200+，1GB DDR - 200MHz 对于特殊情况应该还有优化机会，不过机会不是很大了
现在对于(a+bj)做一次平方，需要对系数做一次平方，一次乘法，两次移位。（一次简单减法可以忽略）
而(a+bj)乘上1+j或(1-j)需要两次加减法运算。
不知道现在通常情况现在乘法需要时间是加法的多少倍（当然同数据大小相关），如果我们对于这个关系有一个比较的表达式，那么应该还有少数优化机会。
比如如果计算(j-1)^1023，有可能写成(j-1)^1024*(j+1)还更加快一些。