最新公告
  • 欢迎您光临IO源码网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 分治法解决大整数乘法问题 PDF 下载

    分治法解决大整数乘法问题 PDF 下载

    本站整理下载:
    链接:https://pan.baidu.com/s/1vpRCNJ9y2HqntnkRzSQRMg 
    提取码:i0yq 
     
     
    相关截图:
     
    主要内容:
    通常,在分析算法的计算复杂性时,都将加法和乘法运算当作基本运算来处理,即将执行一次加法或乘法运算所需的计算时间,当作一个仅取决于计算机硬件处理速度的常数。这个假定仅在参加运算的整数能在计算机硬件对整数的表示范围内直接处理才是合理的。然而,在某些情况下,要处理很大的整数,它无法在计算机硬件能直接表示的整数范围内进行处理。若用浮点数来表示它,则只能近似的表示它的大小,计算结果中的有效数字也受到限制。若要精确地表示大整数并在计算结果中要求精确地得到所有位数上的数字,就必须用软件的方法来实现大整数的算术运算。
    设X和Y都是n位的二进制整数,现在要计算它们的乘积Z。可以用小学所学的方法来设计计算乘积XY的算法,但是这样做计算步骤太多,效率较低。如果将每2个1位数的乘法或加法看作一步运算,那么这种方法要进行O(n^2)步运算才能算出乘积XY。下面用分治法来设计更有效的大整数乘积算法。
    将n位二进制数X和Y都分为两段,每段长n/2位(为简单起见,假设n是2的幂)。则有:
     
    其中X1、Xo分别为X的高位和低位,Y1、Yo分别为Y的高位和低位。C2是它们的前半部分的积;Co是它们后半部分的积;C1是X、Y两部分的和的积减去C2与C0的积。如果n/2也是偶数,我们可以利用相同的方法来计算C2、Co的和C1。因此我们就得到了一个计算n位数积的递归算法:
     
    在这种完美的形式下,当n变成1时,递归就停止了.或者当我们认为n已经够小了,小到可以直接对这样大小的数相乘时,递归就可以停止了.
    该算法会有多少次位乘呢?因为n位数的乘法需要对n/2位数做三次乘法运算,乘法次数M(n)的递推式将会是:
    当n>1时,M(n)=3M(n/2),M(1)=1
    当n=2^k时,我们可以用反向替换法对它求解:

     

    *** 次数:10600 已用完,请联系开发者***

    1. 本站所有资源来源于用户上传和网络,因此不包含技术服务请大家谅解!如有侵权请邮件联系客服!384324621@qq.com
    2. 本站不保证所提供下载的资源的准确性、安全性和完整性,资源仅供下载学习之用!如有链接无法下载、失效或广告,请联系客服处理,有奖励!
    3. 您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容资源!如用于商业或者非法用途,与本站无关,一切后果请用户自负!
    4. 如果您也有好的资源或教程,您可以投稿发布,成功分享后有★币奖励和额外收入!

    IO 源码网 » 分治法解决大整数乘法问题 PDF 下载

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    IO源码吧
    一个高级程序员模板开发平台

    发表评论

    • 84会员总数(位)
    • 10552资源总数(个)
    • 68本周发布(个)
    • 0 今日发布(个)
    • 402稳定运行(天)

    提供最优质的资源集合

    立即查看 了解详情