数字计算检验不等式
Warning问题（http://mathworld.wolfram.com/WaringsProblem.html）说任何一个正整数可以表示成g(k)个整数k次幂的和.
其中
http://mathworld.wolfram.com/images/equations/WaringsProblem/equation3.gif
如果
http://mathworld.wolfram.com/images/equations/WaringsProblem/equation2.gif
可以这个看似简单的不等式
{(3/2)^n}<=1-(3/4)^n
数学家无法证明。
现在大家不妨用计算机验算这个不等式，看谁验算的n可以达到最大。 其实这道题目可以看成两个题目：
i)对于任意给定的n,判断不等式是否成立
ii)对于任意N,判断对于所有1<=n<=N,不等式是否成立
而对于问题i),其实挺有意思，
如果我们将3^n用二进制表示，然后把它看成2n位二进制数（前面补0），
把计算结果分成等长两段（每段都n位），可以拆分成两个n比特的整数，
这个不等式是说，将这两个n比特的整数相加，不会发生溢出（也就是结果还是n位) 原帖由 mathe 于 2008-1-26 16:04 发表 http://bbs.emath.ac.cn/images/common/back.gif
... 这个看似简单的不等式
{(3/2)^n}<=1-(3/4)^n
数学家无法证明。
...
这句没看懂，不知“{}”是何意？
（如果等同于普通括号，则当 n>1 时，左边会>1，而右边<1，不等式不成立） {x} = x- ,
表示x的小数部分 常见的符号，居然忘了这层意思，该罚该罚！:lol
请问，要检验的可就是这个不等式？ 是的。看起来很简单一个不等式
一个更适合证明的推导变换
原帖由 mathe 于 2008-1-26 16:04 发表 http://bbs.emath.ac.cn/images/common/back.gif... 这个看似简单的不等式
{(3/2)^n}<=1-(3/4)^n
数学家无法证明。
...
上述式子因两边均为纯小数，并不太适合计算机证明，尤其是要求追求效率的算法。
我们将其两边同乘以 4^n，则只需证明如下等价不等式即可：
( 6n mod 22n ) ≤ ( 4n - 3n )( n∈N, n≥2 )
因为大整数的模幂运算有许多快速算法，所以上述式子更适合验证。 巧妙推导，更适合程序实现。这个还可以简化，就如我前面所说：
6n(mod 22n)
可以写成
( 3n(mod 2n) )*2n
所以
就是要求3n计算出来后看成2n比特的数，将后面n比特左移n位（也就是乘上2n)，再加上3n
证明不超过4n
由于后面n比特左移n位后最后n比特肯定是0，相加过程最后n比特不会产生进位
所以就变成证明:
3n计算出来后看成2n比特的数，将后面n比特和前面n比特相加，不超过2n（也就是最高位不产生进位）
:)
调用 HugeCalc 来检验一下
////////////////////////////////////////////////////////////////////////////
// 目的：数字计算检验不等式 (与Warning问题相关)
// 帖子：http://bbs.emath.ac.cn/thread-100-1-1.html
// 设计：郭先强 ( gxqcn@163.com; HugeCalc@Gmail.com )
// 日期：2008-01-30
//
// 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 < HugeCalc.h > // 公共接口
#include < HugeIntX.h > // 16进制系统
#pragma message( "automatic link to .../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
#pragma comment( lib, "HugeCalc.lib" )
bool showLastErr( void )
{
bool bErr = TRUE;
switch( HugeCalc::GetLastError() )
{
case HCERR_NO_LICENSE:
cout << "Last Error: HCERR_NO_LICENSE" << endl;
break;
case HCERR_USER_STOP:
cout << "Last Error: HCERR_USER_STOP" << endl;
break;
case HCERR_NO_ENOUGH_MEMORY:
cout << "Last Error: HCERR_NO_ENOUGH_MEMORY" << endl;
break;
case HCERR_INVALID_POINTER:
cout << "Last Error: HCERR_INVALID_POINTER" << endl;
break;
case HCERR_DIV_ZERO:
cout << "Last Error: HCERR_DIV_ZERO" << endl;
break;
case HCERR_BASE2SMALL:
cout << "Last Error: HCERR_BASE2SMALL" << endl;
break;
case HCERR_RADIX2SMALL:
cout << "Last Error: HCERR_RADIX2SMALL" << endl;
break;
case HCERR_NONE:
case HCERR_UNKNOWN:
default:
bErr = FALSE;
}
return bErr;
}
int main(int argc, char* argv[])
{
CHugeIntX hugeInt, hugeTail;
UINT32 n;
BOOL bPass;
cout << "Call " << HugeCalc::GetVer() << endl << endl;
cout << "*** test: {(3/2)^n} <= 1 - (3/4)^n ? ***" << endl;
cout << "input n ...(if n<=1, then exit)" << endl;
for ( ; ; )
{
cout << endl << "n = ";
cin >> n;
if ( n <= 1 )
{
break;
}
HugeCalc::EnableTimer();
HugeCalc::ResetTimer();
( hugeInt = 3 ).Pow( n ); // 3^n
( hugeTail = hugeInt ).ModPowTwo( n ); // 3^n mod 2^n
( hugeInt >>= n ) += hugeTail; // 前n比特 += 后n比特
bPass = ( hugeInt.GetBits() <= n );
hugeInt = hugeTail = 0;
HugeCalc::EnableTimer( FALSE );
if ( !showLastErr() )
{
cout << ( bPass ? "pass!\t" : "fail!\t" );
cout << HugeCalc::GetTimerStr() << endl;
}
else
{
break;
}
}
cout << endl;
system( "pause" );
return 0;
}下面是源代码及编译好的程序压缩包：推荐大家来测试体验一下。。。(314,862 字节)
在我的机器上（单核）运行截图如下：
欢迎大家测试（能测试的极限主要取决于用户的内存大小，这一点 HugeCalc 具有独特的优势:) ）。 Call HugeCalc V8.0.0.0
*** test: {(3/2)^n} <= 1 - (3/4)^n ? ***
input n ...(if n<=1, then exit)
n = 10000
Last Error: HCERR_NO_LICENSE
请按任意键继续. . .
:'(
页:
[1]
2