数字计算检验不等式

mathe

Warning问题（http://mathworld.wolfram.com/WaringsProblem.html）
说任何一个正整数可以表示成g(k)个整数k次幂的和.
其中

如果

可以这个看似简单的不等式
{(3/2)^n}<=1-(3/4)^n
数学家无法证明。
现在大家不妨用计算机验算这个不等式，看谁验算的n可以达到最大。

mathe

其实这道题目可以看成两个题目：
i)对于任意给定的n,判断不等式是否成立
ii)对于任意N,判断对于所有1<=n<=N,不等式是否成立
而对于问题i),其实挺有意思，
如果我们将3^n用二进制表示，然后把它看成2n位二进制数（前面补0），
把计算结果分成等长两段（每段都n位），可以拆分成两个n比特的整数，
这个不等式是说，将这两个n比特的整数相加，不会发生溢出（也就是结果还是n位)

gxqcn

原帖由 mathe 于 2008-1-26 16:04 发表
... 这个看似简单的不等式
{(3/2)^n}<=1-(3/4)^n
数学家无法证明。
...

这句没看懂，不知“{}”是何意？
（如果等同于普通括号，则当 n>1 时，左边会>1，而右边<1，不等式不成立）

mathe

{x} = x- [x],
表示x的小数部分

gxqcn

常见的符号，居然忘了这层意思，该罚该罚！

请问，要检验的可就是这个不等式？

mathe

是的。看起来很简单一个不等式

gxqcn

原帖由 mathe 于 2008-1-26 16:04 发表
... 这个看似简单的不等式
{(3/2)^n}<=1-(3/4)^n
数学家无法证明。
...

上述式子因两边均为纯小数，并不太适合计算机证明，尤其是要求追求效率的算法。

我们将其两边同乘以 4^n，则只需证明如下等价不等式即可：

　　( 6ⁿ mod 2²ⁿ ) ≤ ( 4ⁿ - 3ⁿ )  ( n∈N, n≥2 )

因为大整数的模幂运算有许多快速算法，所以上述式子更适合验证。

mathe

这个还可以简化，就如我前面所说：

6ⁿ(mod 2²ⁿ)
可以写成
( 3ⁿ(mod 2ⁿ) )*2ⁿ
所以
就是要求3ⁿ计算出来后看成2n比特的数，将后面n比特左移n位（也就是乘上2ⁿ)，再加上3ⁿ
证明不超过4ⁿ
由于后面n比特左移n位后最后n比特肯定是0，相加过程最后n比特不会产生进位
所以就变成证明:
3ⁿ计算出来后看成2n比特的数，将后面n比特和前面n比特相加，不超过2ⁿ（也就是最高位不产生进位）

gxqcn

1. //////////////////////////////////////////////////////////////////////////
   
2. //
   
3. // 目的：数字计算检验不等式 (与Warning问题相关)
   
4. // 帖子：http://bbs.emath.ac.cn/thread-100-1-1.html
   
5. // 设计：郭先强 ( gxqcn@163.com; HugeCalc@Gmail.com )
   
6. // 日期：2008-01-30
   
7. //
   
8. // Web: http://www.emath.ac.cn/
   
9. // BBS: http://bbs.emath.ac.cn/
   
10. //
    
11. //////////////////////////////////////////////////////////////////////////
    
12. 
    
13. // Project -> Setting -> C/C++ -> Code Generation --> Use run-time library:
    
14. //      Win32 Debug:    Debug Multithreaded DLL
    
15. //      Win32 Release:  Multithreaded DLL
    
16. 
    
17. #include < iostream.h >
    
18. 
    
19. #include < HugeCalc.h > // 公共接口
    
20. #include < HugeIntX.h > // 16进制系统
    
21. 
    
22. #pragma message( "automatic link to .../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
    
23. #pragma comment( lib, "HugeCalc.lib" )
    
24. 
    
25. bool showLastErr( void )
    
26. {
    
27.     bool bErr = TRUE;
    
28. 
    
29.     switch( HugeCalc::GetLastError() )
    
30.     {
    
31.     case HCERR_NO_LICENSE:
    
32.         cout << "Last Error: HCERR_NO_LICENSE" << endl;
    
33.         break;
    
34. 
    
35.     case HCERR_USER_STOP:
    
36.         cout << "Last Error: HCERR_USER_STOP" << endl;
    
37.         break;
    
38. 
    
39.     case HCERR_NO_ENOUGH_MEMORY:
    
40.         cout << "Last Error: HCERR_NO_ENOUGH_MEMORY" << endl;
    
41.         break;
    
42. 
    
43.     case HCERR_INVALID_POINTER:
    
44.         cout << "Last Error: HCERR_INVALID_POINTER" << endl;
    
45.         break;
    
46. 
    
47.     case HCERR_DIV_ZERO:
    
48.         cout << "Last Error: HCERR_DIV_ZERO" << endl;
    
49.         break;
    
50. 
    
51.     case HCERR_BASE2SMALL:
    
52.         cout << "Last Error: HCERR_BASE2SMALL" << endl;
    
53.         break;
    
54. 
    
55.     case HCERR_RADIX2SMALL:
    
56.         cout << "Last Error: HCERR_RADIX2SMALL" << endl;
    
57.         break;
    
58. 
    
59. 
    
60.     case HCERR_NONE:
    
61.     case HCERR_UNKNOWN:
    
62.     default:
    
63.         bErr = FALSE;
    
64.     }
    
65. 
    
66.     return bErr;
    
67. }
    
68. 
    
69. int main(int argc, char* argv[])
    
70. {
    
71.     CHugeIntX hugeInt, hugeTail;
    
72.     UINT32 n;
    
73.     BOOL bPass;
    
74. 
    
75.     cout << "Call " << HugeCalc::GetVer() << endl << endl;
    
76. 
    
77.     cout << "*** test: {(3/2)^n} <= 1 - (3/4)^n ? ***" << endl;
    
78.     cout << "input n ...(if n<=1, then exit)" << endl;
    
79. 
    
80.     for ( ; ; )
    
81.     {
    
82.         cout << endl << "n = ";
    
83.         cin >> n;
    
84. 
    
85.         if ( n <= 1 )
    
86.         {
    
87.             break;
    
88.         }
    
89. 
    
90.         HugeCalc::EnableTimer();
    
91.         HugeCalc::ResetTimer();
    
92. 
    
93.         ( hugeInt = 3 ).Pow( n );                 // 3^n
    
94.         ( hugeTail = hugeInt ).ModPowTwo( n );    // 3^n mod 2^n
    
95.         ( hugeInt >>= n ) += hugeTail;            // 前n比特 += 后n比特
    
96.         bPass = ( hugeInt.GetBits() <= n );
    
97.         hugeInt = hugeTail = 0;
    
98. 
    
99.         HugeCalc::EnableTimer( FALSE );
    
100. 
     
101.         if ( !showLastErr() )
     
102.         {
     
103.             cout << ( bPass ? "pass!\t" : "fail!\t" );
     
104.             cout << HugeCalc::GetTimerStr() << endl;
     
105.         }
     
106.         else
     
107.         {
     
108.             break;
     
109.         }
     
110.     }
     
111. 
     
112.     cout << endl;
     
113.     system( "pause" );
     
114. 
     
115.     return 0;
     
116. }

复制代码

下面是源代码及编译好的程序压缩包：

testWarningQ.zip (307.48 KB, 下载次数: 7)

2008-1-30 13:43 上传

点击文件名下载附件
数字计算检验不等式 (与Warning问题相关)

(314,862 字节)

在我的机器上（单核）运行截图如下：

数字计算检验不等式 (与Warning问题相关)

欢迎大家测试（能测试的极限主要取决于用户的内存大小，这一点 HugeCalc 具有独特的优势 ）。

kofeffect

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

请按任意键继续. . .