任意大整数的相除算法

用链表实现的任意大整数，  
  如何相除 问题点数：100、回复次数：16Top

1 楼hslinux（幻世龙）回复于 2006-06-03 16:08:43 得分 5

HOHO~~~~做因式分解先吧，，嘿嘿，UP下，没深入想过。Top

2 楼lk_517（风雷，www.forwind.cn）回复于 2006-06-03 17:08:34 得分 10

用牛顿迭代实现除数的倒数，然后相乘Top

3 楼chenhu_doc（^0^纯一狼^0^ 看书看到大笑，直到不能自已）回复于 2006-06-03 17:53:08 得分 5

弱弱的:   是否可以模拟一下手工除法的过程,毕竟因式分解和倒数的思路有精度损失问题!!Top

4 楼happytang（一只叫苏格拉底的猪）回复于 2006-06-03 20:44:06 得分 20

转换成乘以“除数的倒数”，其中“除数的倒数”可用牛顿迭代实现。  
  Top

5 楼happytang（一只叫苏格拉底的猪）回复于 2006-06-03 20:52:54 得分 0

大整数除以大整数主要有三种方法：  
  1.   试商法  
  2.   相减法，即由被除数不断地减去除数来得到  
  3.   化除为乘。先把被除数取倒数，然后让倒数与除数相乘。取倒数可以使用牛顿迭代法。（速度最快）  
  Top

6 楼boxer_tony（）回复于 2006-06-07 11:35:14 得分 5

to   chenhu_doc:  
  哪种方法都有精度损失的问题啊。倒数相乘并不一定会比手工法损失更多的精度，只要倒数的精度足够，最后的结果精度也是够的。Top

7 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2006-06-07 16:54:24 得分 0

>>   倒数相乘  
   
  倒数又该怎么算呢....Top

8 楼gxqcn（★)　HugeCalc ← http://hugecalc.ik8.com/　(☆）回复于 2006-06-08 10:40:55 得分 20

可用：A/B   =   A*(C/B)   /C  
   
  其中   C   为你采用进制数的整数次幂（主要是方便实现“移位”），且充分大（需进行误差分析）；而   (C/B)   可通过牛顿迭代法快速计算出来；与   A   乘后“右移”即可（某些时候可能有正负1的误差问题需修正）。  
   
  我的   HugeCalc   即采用上述原理。Top

9 楼yeyanbinghappy（）回复于 2006-06-08 13:11:08 得分 10

大整数（x，y）乘法可以采用分治法，n位的整数都分为两段，每段长为n/2位，  
  x=a*pow(2,n/2)+b,y=c*pow(2,n/2)+d  
  x*y=a*c*pow(2,n)+(a*d+b*c)*pow(2,n/2)+b*d  
  大整数除法也可以这样想吧  
  Top

10 楼liangbch（宝宝）回复于 2006-06-12 20:36:32 得分 20

3.   化除为乘。先把被除数取倒数，然后让倒数与除数相乘。取倒数可以使用牛顿迭代法。（速度   最快）  
      同意该观点,至于精度损失问题可以这样解决:  
   
       
      若被除数为N1,除数为N2,被除数长度了L1,除数长度为L2,且   L1>2*L2   则可用如下方法:  
       
      step1.   求N2的倒数NR,精确到L2+1   位即可  
       
      step2:   取被除数(余数)的L2+1   位与   NR(L2+1位)   相乘   ,得到   近似商   Q(取前L2位即可)  
      step3:   将Q   与   N2   相乘   得到   2*L2位   积P  
      step4:   比较P与   被除数(余数)的前   2*L2位,若Q小于等于后者,转step5,否则,则Q=Q-1,P=P-N2,继续重复step4(理论上step4最多重复一次)  
      step5:   新的近似商与已经求出的部分商错位相加,被除数(余数)的前   2*L2位   与   P   相减,如商达到规定的位数(小数除法)或者余数小于被除数(整数除法),则计算终止,否则转step2(继续下一次求值)  
     
      从上面的过程可以看到,这个算法其本质仍然是试商法,但其试商的过程采用被除数与除数的倒数相乘的算法,一次可以得到多位商.若N*N位数乘法的复杂度为U,则KN位数除以N位数的复杂度为  
    2*K*U(不考虑求倒数的代价),大约是   KN位   与   N位数的   乘法的2倍.  
       
   
    若被除数的位数比除数的位数不是大得太多,则每次试商时,可适当减少运算的位数,",即减小此文"取被除数(余数)的L2+1   位与   NR(L2+1位)   相乘   ,得到   近似商   Q(取前L2位即可)"   中L2的值.Top

11 楼liangbch（宝宝）回复于 2006-06-12 20:39:10 得分 0

更正:   step4   应为:   比较P与   被除数(余数)的前   2*L2位,若P小于等于后者,转step5,否则,则Q=Q-1,P=P-N2,继续重复step4(理论上step4最多重复一次)  
  Top

12 楼liangbch（宝宝）回复于 2006-06-12 20:42:04 得分 0

牛顿迭代法求倒数的算法请参阅：http://enjoy-math.equn.com/Math/Mathematical/Inverse.htmTop

13 楼DentistryDoctor（不在无聊中无奈，就在沉默中变态）回复于 2006-06-16 08:12:34 得分 5

找个RSA的源代码看看吧。Top

14 楼pjie131（★自由★你忘记了吗？）回复于 2006-06-22 16:58:05 得分 0

牛人  
   
  markTop

15 楼pjie131（★自由★你忘记了吗？）回复于 2006-06-22 16:58:19 得分 0

牛人  
  markTop

16 楼universee（吾乃太极语言之父）回复于 2006-06-26 20:52:03 得分 0

markTop

相关问题

• 帖主：Mana
• hslinux
• lk_517
• chenhu_doc
• happytang
• boxer_tony
• gxqcn
• yeyanbinghappy
• liangbch
• DentistryDoctor

• CSDN Blog
• 技术文档
• 代码下载
• 第二书店
• 读书频道