数字计算检验不等式

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. //////////////////////////////////////////////////////////////////////////
13. // Project -> Setting -> C/C++ -> Code Generation --> Use run-time library:
14. // Win32 Debug: Debug Multithreaded DLL
15. // Win32 Release: Multithreaded DLL
17. #include < iostream.h >
19. #include < HugeCalc.h > // 公共接口
20. #include < HugeIntX.h > // 16进制系统
22. #pragma message( "automatic link to .../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
23. #pragma comment( lib, "HugeCalc.lib" )
25. bool showLastErr( void )
26. {
27. bool bErr = TRUE;
29. switch( HugeCalc::GetLastError() )
30. {
31. case HCERR_NO_LICENSE:
32. cout << "Last Error: HCERR_NO_LICENSE" << endl;
33. break;
35. case HCERR_USER_STOP:
36. cout << "Last Error: HCERR_USER_STOP" << endl;
37. break;
39. case HCERR_NO_ENOUGH_MEMORY:
40. cout << "Last Error: HCERR_NO_ENOUGH_MEMORY" << endl;
41. break;
43. case HCERR_INVALID_POINTER:
44. cout << "Last Error: HCERR_INVALID_POINTER" << endl;
45. break;
47. case HCERR_DIV_ZERO:
48. cout << "Last Error: HCERR_DIV_ZERO" << endl;
49. break;
51. case HCERR_BASE2SMALL:
52. cout << "Last Error: HCERR_BASE2SMALL" << endl;
53. break;
55. case HCERR_RADIX2SMALL:
56. cout << "Last Error: HCERR_RADIX2SMALL" << endl;
57. break;
60. case HCERR_NONE:
61. case HCERR_UNKNOWN:
62. default:
63. bErr = FALSE;
64. }
66. return bErr;
67. }
69. int main(int argc, char* argv[])
70. {
71. CHugeIntX hugeInt, hugeTail;
72. UINT32 n;
73. BOOL bPass;
75. cout << "Call " << HugeCalc::GetVer() << endl << endl;
77. cout << "*** test: {(3/2)^n} <= 1 - (3/4)^n ? ***" << endl;
78. cout << "input n ...(if n<=1, then exit)" << endl;
80. for ( ; ; )
81. {
82. cout << endl << "n = ";
83. cin >> n;
85. if ( n <= 1 )
86. {
87. break;
88. }
90. HugeCalc::EnableTimer();
91. HugeCalc::ResetTimer();
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;
99. HugeCalc::EnableTimer( FALSE );
101. if ( !showLastErr() )
102. {
103. cout << ( bPass ? "pass!\t" : "fail!\t" );
104. cout << HugeCalc::GetTimerStr() << endl;
105. }
106. else
107. {
108. break;
109. }
110. }
112. cout << endl;
113. system( "pause" );
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 请按任意键继续. . .