当前位置:首页 > 开发 > 编程语言 > 算法 > 正文

折半试乘查找算法计算超大整数平方根

发表于: 2012-04-19   作者:bardo   来源:转载   浏览次数:
摘要: 折半试乘查找算法,听此名字,还不如直接试乘呢,直接试乘是没有范围的。此算法先确定一个范围,然后再试乘。并且试乘的积并不是原来的数。 正常的开方,我们是用以下公式:(a+b)^2=a^2+2ab+b^2。这相当易于手算。但不利于写程序代码。对于超大整数开方,利用上述公式,代码是较为烦琐的。所以,这里介绍一个试乘折半查找算法。数学根据如下:我们有:对于奇数,[(n+1)/2]^2-[(n-1)/2]

折半试乘查找算法,听此名字,还不如直接试乘呢,直接试乘是没有范围的。此算法先确定一个范围,然后再试乘。并且试乘的积并不是原来的数。


正常的开方,我们是用以下公式:(a+b)^2=a^2+2ab+b^2。这相当易于手算。但不利于写程序代码。
对于超大整数开方,利用上述公式,代码是较为烦琐的。所以,这里介绍一个试乘折半查找算法。
数学根据如下:
我们有:
对于奇数,[(n+1)/2]^2-[(n-1)/2]^2=n
我们令:a+b=(n+1)/2 c+d=(n-1)/2
则:(a+b)^2-(c+d)^2=n
当ab=cd时,我们有:(a-b)^2-(c-d)^2=n
所以,如果n为完全平方,则有:c=d,所以,我们只要求出
a+b=(n+1)/2,c=d时,ab=c^2,或ab=d^2即可得到平方根。
举例说明如下:
对于:9
c+d=4,c=d=2, cd=4
a+b=5, 所以,ab=4时: a=4, b=1  a-b=3 即是平方根。
对于25:
c+d=12,c=d=6, cd=36
a+b=13, 所以,ab=36时: a=9, b=4  a-b=5 即是平方根。

对于偶数,[(n+2)/2]^2-[(n-2)/2]^2=4n
我们令:a+b=(n+2)/2 c+d=(n-2)/2
则:(a+b)^2-(c+d)^2=4n
同理我们也有(a-b)^2-(c-d)^2=4n
所以一样也有,如果n这完全平方,则有:c=d,所以,我们只要求出
a+b=(n+2)/2,c=d时,ab=c^2,或ab=d^2即可得到平方根。
举例说明如下:
对于:16
c+d=6,c=d=3, cd=9
a+b=10, 所以,ab=9时: a=9, b=1  (a-b)/2=8/2=4   即是平方根。
对于36:
c+d=16,c=d=8, cd=64
a+b=20, 所以,ab=64时: a=16, b=4  (a-b)/=12/2=6   即是平方根。

由此可见,算法就是简单地让 c=d, 并求出 ab=c^2,
其中, a+b=(n+1)/2 c+d=(n-1)/2(奇数)
       a+b=(n+2)/2 c+d=(n-2)/2(偶数) 
      
理论上来讲,如果是用10进制,40位的数字,如果用(a+b)^2=a^2+2ab+b^2公式法,要算40次。
但折半试乘查找算法却要试乘126次左右。
表面上看,可能前者快,但对于每一个10进制的位实际都要试根。要试出合适的2ab+b^2。也就多许多次加法和许多次减法。
但折半试乘查找算法只是将乘出的结果直接与目标数比大小。
所以,此算法的效率,必须经过测试才能证明。
另一方面,此算法的算法复杂度则远远小于平方和法的复杂度。
如果此算法效率高,则我们可以有这样的结论,并非算法复杂度高的算法效率一定高。

折半试乘查找算法计算超大整数平方根

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
•顺序查找   从线性表的一端开始,依次将每个记录的关键字与给定值进行比较,若某个记录的关键字
折半查找 折半查找(二分查找)对处理元素要求 有序 顺序存储结构 基本思想 就是每次查找中间元素和
原文: JavaScript超大整数加法 什么是「超大整数」? JavaScript 采用 IEEE754标准 中的浮点数算法来
/* 折半查找 */ class TwoSearch { //折半查找可以提高效率,但必须得保证是有序的数组 public stat
在面试笔试中会考到这类题目,要求不用加减乘除运算来计算两数和,其实考的就是位运算。 规则1: 如
在面试笔试中会考到这类题目,要求不用加减乘除运算来计算两数和,其实考的就是位运算。 规则1: 如
static int binSearch(int value) { int upperBound, lowerBound, mid; upperBound = arr.Length-1;
查找又称检索,是指在某种数据结构中找出满足给定条件的元素。若在查找的同时对表做修改运算(如插入
哈希表的概念 哈希表又称散列表,是一种线性的存储结构。是根据关键码值(Key Value)而直接进行访
项目中复合指标由配置好的基础指标公式解析后存到如下一张表中: --Create table create table TESTR
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号