数学研发论坛

 找回密码
 欢迎注册
查看: 2768|回复: 4

[求助] 求两个超大整数的商并向上取整,哪个代码效率高?

[复制链接]
发表于 2008-9-8 20:19:07 | 显示全部楼层 |阅读模式

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

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

x
$a$、$b$ 是两个超大整数,$a>=0$,$b>0$,计算 $q = |~a/b~|$,下面的代码哪个效率高?

代码1:
  1. CHugeIntX r;

  2. q.Div(a, b, &r);
  3. if ( !r ) ++q;
复制代码
代码2;
  1. q = ( a + b - 1) / b;
复制代码
代码3(代码2的变体):
  1. CHugeIntX t(a+b);
  2. --t;
  3. q.Div( t, b );
复制代码
或者,有更好的代码???
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-8 21:23:18 | 显示全部楼层
应该是1
但如果可能
还是单独做一个算法效率高些

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-8 21:25:45 | 显示全部楼层
最好最快的代码就是代码1。

代码2和代码3都需要额外的加减法运算,以及潜在的对象拷贝操作。

但是代码1会改变变量a,如果要消除该问题,可用如下代码:
  1. CHugeIntX r;

  2. q.Div(CHugeIntX(a), b, &r);
  3. if ( !(!r) ) ++q;
复制代码
注意:判断 r 非零的代码为“!(!r)”,要多一个“!”,
两个“!”不可同时抵消,因为里面那个是重载的自定义运算符。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-9-8 22:59:29 | 显示全部楼层
不明白 “但是代码1会改变变量a”,以下测试代码:
  1.         CHugeIntX a(999), b(10), aa, q, r;
  2.        
  3.         aa = a;

  4.         q.Div( a, b, &r );
  5.         if ( !(!r) ) ++q;       
  6.        
  7.         cout << "q = " << int(q) << ",  r = " << int(r) << endl << endl;
  8.        
  9.         if ( a == aa)
  10.                 cout << "a == aa";
  11.         else
  12.                 cout << "a<>aa";
  13.        
  14.         cout << endl << endl;
复制代码
的运行结果是:
  1. q = 100,  r = 9

  2. a == aa

  3. Press any key to continue
复制代码
还有,Div 的声明
  1. CHugeIntX& CHugeIntX::Div( CONST CHugeIntX& hugeDividend, CONST CHugeIntX& hugeDivisor, CHugeIntX& CONST pRemainder = NULL );
复制代码
也说被除数 hugeDividend 是 CONST 的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-9 07:49:43 | 显示全部楼层
对不起,我在 3# 说错了,被除数是 CONST 的,返回的是商。
(自己很疲劳,儿子又生病了,所以脑子有点乱

所以最简洁最高效的代码是:
  1. CHugeIntX r;

  2. q.Div(a, b, &r);
  3. if ( !(!r) ) ++q;
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2020-11-30 03:09 , Processed in 0.082536 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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