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

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

正常的开方，我们是用以下公式：(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。也就多许多次加法和许多次减法。
但折半试乘查找算法只是将乘出的结果直接与目标数比大小。
所以，此算法的效率，必须经过测试才能证明。
另一方面，此算法的算法复杂度则远远小于平方和法的复杂度。
如果此算法效率高，则我们可以有这样的结论，并非算法复杂度高的算法效率一定高。