Java BigInteger sqrt方法的实现

时间：2022-11-28 16:50:40
本来是为我上学期写好的MathTool工具类转化，也就是原来这个工具类的方法参数类型是long。为了实现任意大数的运算，long用BigInteger替换带哦。好了废话少数，先说数学原理，也就是手算平方根计算机代码实现！那么什么叫手算平方根了？？？
手开方 
据说前苏联的普通工人都会的（毛熊国果然是一个神奇的国度！听到这里我背脊发冷,再次膜拜俄罗斯基础数！！和那令人望而生畏的吉米多维奇了！！！ )
它的计算步骤如下：   
1．将被开方数的整数部分从个位起向左每隔两位划为一段，用撇号分开(竖式中的11'56)，分成几段，表示所求平方根是几位数；   
2．根据左边第一段里的数，求得平方根的最高位上的数(竖式中的3)；   
3．从第一段的数减去最高位上数的平方，在它们的差的右边写上第二段数组成第一个余数(竖式中的256)   
4．把求得的最高位数乘以20去试除第一个余数，所得的最大整数作为试商(3×20除 256，所得的最大整数是 4，即试商是4)；   
5．用商的最高位数的20倍加上这个试商再乘以试商．如果所得的积小于或等于余数，试商就是平方根的第二位数；如果所得的积大于余数，就把试商减小再试(竖式中(20×3＋4)×4＝256，说明试商4就是平方根的第二位数)；   
6．用同样的方法，继续求平方根的其他各位上的数．  
  一个实例 
(1)如求54756的算术平方根时先由个位向左两位两位地定位：定位为5，47，56，接着象一般除法那样列出除式. 
(2)先从最高位用最大平方数试商：最大平方数不超过5的是2，得商后，除式5-4后得1。把商2写上除式  
(3)加上下一位的数：得147。 
(4)用20去乘商后去试商147：2×20=40 这40可试商为3，那就把试商的3加上40去除147。得147÷43=3,把3写上除式上。这时147-129=18。 
(5)加上下一位的数：得1856。 
(6)用20去乘商后去试商1856：23×20=460 这460可试商为4，那就把试商的4加到460去除1856。得4，把4写上除式上。这时1856-1856=0，无余数啦。 

(7)这时除式上的商是234，即是54756的平方根。手工是这样做的，写得罗嗦了，但望能看懂。


package com.swu.math;
import java.math.BigInteger;
public class Test
{
	public static String sqrt(String num)
	{
		BigInteger b=new BigInteger(num);
		//不用多解释了吧
		if(b.compareTo(BigInteger.ZERO)<0)
			return "不是非负数";

		String sqrt="0"; //开方结果
		String pre="0"; //开方过程中需要计算的被减数
		BigInteger trynum; //试商，开放过程中需要计算的减数
		BigInteger flag;  //试商，得到满足要求减数的之后一个数
		BigInteger _20=new BigInteger("20"); //就是20
		BigInteger dividend; ///开方过程中需要计算的被减数
		BigInteger A;  //(10*A+B)^2=M
		BigInteger B;  
		BigInteger BB;

		int len=num.length(); //数字的长度

		if(len%2==1)  //长度是奇数的画，首位补上1个0凑成偶数位
		{
			num="0"+num;
			len++;
		}

		for(int i=0;i<len/2;++i) //得到的平方根一定是len/2位
		{
			dividend=new BigInteger(pre+num.substring(2*i,2*i+2));	
			A=new BigInteger(sqrt);
			for(int j=0;j<=9;++j)
			{
				B=new BigInteger(j+"");
				BB=new BigInteger((j+1)+"");

				trynum=_20.multiply(A).multiply(B).add(B.pow(2));
				flag=_20.multiply(A).multiply(BB).add(BB.pow(2));;

				//满足要求的j使得试商与计算中的被减数之差为最小正数
				if(trynum.subtract(dividend).compareTo(BigInteger.ZERO)<=0
						&&flag.subtract(dividend).compareTo(BigInteger.ZERO)>0)
				{
					sqrt+=j;  //结果加上得到的j
					pre=dividend.subtract(trynum).toString(); //更新开方过程中需要计算的被减数
					break;
				}
			}		
		}
		return sqrt.substring(1);
	}


	public static void main(String[] args)
	{
		System.out.println(MathTool.sqrt("1234567890123456789"));
		System.out.println(Math.sqrt(1234567890123456789l));
	}
}



测试结果

1111111106
1.1111111061111112E9


标签：

相关文章