首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C++ >

能帮小弟我看看这段程序吗

2012-02-13 
能帮我看看这段程序吗最近在看一个大数的运算的程序,其中有个除法如下voidvlong_value::divide(vlong_valu

能帮我看看这段程序吗
最近在看一个大数的运算的程序,其中有个除法如下
void   vlong_value::divide(   vlong_value&   x,   vlong_value&   y,   vlong_value&   rem   )  
{  
init(0);  
rem.copy(x);  
vlong_value   m,s;  
m.copy(y);  
s.init(1);  
while   (   rem.cf(m)   >   0   )  
{  
  m.shl();  
  s.shl();  
}  
while   (   rem.cf(y)   > =   0   )  
{  
  while   (   rem.cf(m)   <   0   )  
  {  
      m.shr();  
      s.shr();  
  }  
  rem.subtract(   m   );  
  add(   s   );  
}  
}  
其中int()是初始化   ,copy()是指大数的复制,shl()是指左移,shr()是指右移,cf()是比较大小,subtract()是减法,add是加法。
但其中哪个是被除数,哪个是除数啊,总是搞不明白,
哪位热心人帮我看看,理理思路,感激不尽!

[解决办法]
void vlong_value::divide( vlong_value& x, vlong_value& y, vlong_value& rem )
// x:被除数,y:除数,rem:余数
{
init(0); //结合下面的add(s),这里应该是指设商(用q表示)q=0;
rem.copy(x); // rem = x;
vlong_value m,s;
m.copy(y); // m = y
s.init(1); // s = 1

// 目前的状态: assert(q==0 && rem == x && m==y && s==1);

while ( rem.cf(m) > 0 ) // rem > m,即现在x > m 时
{
m.shl(); // m *= 2
s.shl(); // s *= 2
}

// 目前的状态:assert(q==0 && rem==x && m== y*s && (s是2的整数幂) && x <=m
// &&(m是所有满足前面条件的所有数中最小的一个))
// 即上述while让m为y乘以一个2整数幂,以找到第一个不小于x的数,并用s保存这个乘数
// “m是所有满足前面条件的所有数中最小的一个”的数学表达是: y*s/2 <= x <= y*s

while ( rem.cf(y) > = 0 ) // rem > = y
{
while ( rem.cf(m) < 0 ) // rem < m
{
m.shr(); // m /= 2
s.shr(); // s /= 2
}

// 目前的状态 assert(rem> =y && m== y*s && (s是2的整数幂) && rem> =m
// && (m是满足上述条件中的所有数中最大的一个))
// 即while让m为y乘以一个2整数幂,以找到第一个不大于rem的数,并用s保存这个乘数
// “m是满足上述条件中的所有数中最大的一个”的数学表达是: y*s <= rem <= y*s*2
rem.subtract( m ); // rem -= m;即 rem -= y*s
add( s ); // 商q += s
}

// 目前的状态:assert( q==x/y && rem == x%y )

}

这个算法的本质是将商q 用二进制表示成 Sn Sn-1 .... S0
然后从s1开始,每次(即 while ( rem.cf(y) > = 0 ) 段)找到第一个Si==1,令s=2^i,并从rem(开始为x)中减去y*s,直到rem <y
此时 rem == x - (2^n + 2^n-1 + ... + 2^0) * y == x - q*y == x % y

热点排行