数学研发网设为首页收藏本站

数学研发论坛

 找回密码
 欢迎注册
查看: 5335|回复: 19

[擂台] 数字计算检验不等式

[复制链接]
发表于 2008-1-26 16:04:51 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

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

如果

可以这个看似简单的不等式
{(3/2)^n}<=1-(3/4)^n
数学家无法证明。
现在大家不妨用计算机验算这个不等式,看谁验算的n可以达到最大。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-1-29 11:04:47 | 显示全部楼层
其实这道题目可以看成两个题目:
i)对于任意给定的n,判断不等式是否成立
ii)对于任意N,判断对于所有1<=n<=N,不等式是否成立
而对于问题i),其实挺有意思,
如果我们将3^n用二进制表示,然后把它看成2n位二进制数(前面补0),
把计算结果分成等长两段(每段都n位),可以拆分成两个n比特的整数,
这个不等式是说,将这两个n比特的整数相加,不会发生溢出(也就是结果还是n位)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-1-29 14:08:20 | 显示全部楼层
原帖由 mathe 于 2008-1-26 16:04 发表
... 这个看似简单的不等式
{(3/2)^n}<=1-(3/4)^n
数学家无法证明。
...


这句没看懂,不知“{}”是何意?
(如果等同于普通括号,则当 n>1 时,左边会>1,而右边<1,不等式不成立)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-1-29 15:02:03 | 显示全部楼层
{x} = x- [x],
表示x的小数部分
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-1-29 15:06:43 | 显示全部楼层
常见的符号,居然忘了这层意思,该罚该罚!

请问,要检验的可就是这个不等式?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-1-29 15:12:53 | 显示全部楼层
是的。看起来很简单一个不等式
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-1-30 09:20:18 | 显示全部楼层

一个更适合证明的推导变换

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


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

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

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

因为大整数的模幂运算有许多快速算法,所以上述式子更适合验证。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-1-30 09:35:12 | 显示全部楼层
推荐
这个还可以简化,就如我前面所说:

6n(mod 22n)
可以写成
( 3n(mod 2n) )*2n
所以
就是要求3n计算出来后看成2n比特的数,将后面n比特左移n位(也就是乘上2n),再加上3n
证明不超过4n
由于后面n比特左移n位后最后n比特肯定是0,相加过程最后n比特不会产生进位
所以就变成证明:
3n计算出来后看成2n比特的数,将后面n比特和前面n比特相加,不超过2n(也就是最高位不产生进位)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-1-30 12:35:12 | 显示全部楼层

调用 HugeCalc 来检验一下

  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. // Project -> Setting -> C/C++ -> Code Generation --> Use run-time library:
  13. //      Win32 Debug:    Debug Multithreaded DLL
  14. //      Win32 Release:  Multithreaded DLL

  15. #include < iostream.h >

  16. #include < HugeCalc.h > // 公共接口
  17. #include < HugeIntX.h > // 16进制系统

  18. #pragma message( "automatic link to .../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
  19. #pragma comment( lib, "HugeCalc.lib" )

  20. bool showLastErr( void )
  21. {
  22.     bool bErr = TRUE;

  23.     switch( HugeCalc::GetLastError() )
  24.     {
  25.     case HCERR_NO_LICENSE:
  26.         cout << "Last Error: HCERR_NO_LICENSE" << endl;
  27.         break;

  28.     case HCERR_USER_STOP:
  29.         cout << "Last Error: HCERR_USER_STOP" << endl;
  30.         break;

  31.     case HCERR_NO_ENOUGH_MEMORY:
  32.         cout << "Last Error: HCERR_NO_ENOUGH_MEMORY" << endl;
  33.         break;

  34.     case HCERR_INVALID_POINTER:
  35.         cout << "Last Error: HCERR_INVALID_POINTER" << endl;
  36.         break;

  37.     case HCERR_DIV_ZERO:
  38.         cout << "Last Error: HCERR_DIV_ZERO" << endl;
  39.         break;

  40.     case HCERR_BASE2SMALL:
  41.         cout << "Last Error: HCERR_BASE2SMALL" << endl;
  42.         break;

  43.     case HCERR_RADIX2SMALL:
  44.         cout << "Last Error: HCERR_RADIX2SMALL" << endl;
  45.         break;


  46.     case HCERR_NONE:
  47.     case HCERR_UNKNOWN:
  48.     default:
  49.         bErr = FALSE;
  50.     }

  51.     return bErr;
  52. }

  53. int main(int argc, char* argv[])
  54. {
  55.     CHugeIntX hugeInt, hugeTail;
  56.     UINT32 n;
  57.     BOOL bPass;

  58.     cout << "Call " << HugeCalc::GetVer() << endl << endl;

  59.     cout << "*** test: {(3/2)^n} <= 1 - (3/4)^n ? ***" << endl;
  60.     cout << "input n ...(if n<=1, then exit)" << endl;

  61.     for ( ; ; )
  62.     {
  63.         cout << endl << "n = ";
  64.         cin >> n;

  65.         if ( n <= 1 )
  66.         {
  67.             break;
  68.         }

  69.         HugeCalc::EnableTimer();
  70.         HugeCalc::ResetTimer();

  71.         ( hugeInt = 3 ).Pow( n );                 // 3^n
  72.         ( hugeTail = hugeInt ).ModPowTwo( n );    // 3^n mod 2^n
  73.         ( hugeInt >>= n ) += hugeTail;            // 前n比特 += 后n比特
  74.         bPass = ( hugeInt.GetBits() <= n );
  75.         hugeInt = hugeTail = 0;

  76.         HugeCalc::EnableTimer( FALSE );

  77.         if ( !showLastErr() )
  78.         {
  79.             cout << ( bPass ? "pass!\t" : "fail!\t" );
  80.             cout << HugeCalc::GetTimerStr() << endl;
  81.         }
  82.         else
  83.         {
  84.             break;
  85.         }
  86.     }

  87.     cout << endl;
  88.     system( "pause" );

  89.     return 0;
  90. }
复制代码
下面是源代码及编译好的程序压缩包:
推荐
testWarningQ.zip (307.48 KB, 下载次数: 7)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-1-31 10:42:07 | 显示全部楼层
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

请按任意键继续. . .

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|Archiver|数学研发网 ( 苏ICP备07505100号  

GMT+8, 2017-7-26 18:35 , Processed in 0.209009 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表