import java.math.BigInteger;
import java.util.Arrays;
/**
* Created by MGL on 2017/4/21.
*/
public class BigInteger_Sqrt{
public static void main(String[] args) {
String str = "846516548651346132456465132189465134894651645613";
BigInteger n1 = new BigInteger(str);
BigInteger multiply = n1.multiply(n1);
int length = multiply.toString().length();
System.out.println("数的长度 = " + length);
long start = System.nanoTime();
BigInteger sqrt = getSqrt(multiply);
long end = System.nanoTime();
System.out.println(end - start);
System.out.println("对" +length +"位数进行开放运算所需要的时间 = " + (end - start)/1000000000F + "s");
System.out.println("运算结果 = " + (sqrt.compareTo(n1) == 0));
}
private static BigInteger getSqrt(BigInteger num) {
String s = num.toString();
int mlen = s.length(); //被开方数的长度
int len; //开方后的长度
BigInteger beSqrtNum = new BigInteger(s);//被开方数
BigInteger sqrtOfNum; //存储开方后的数
BigInteger sqrtOfNumMul; //开方数的平方
String sString;//存储sArray转化后的字符串
if (mlen % 2 == 0) len = mlen / 2;
else len = mlen / 2 + 1;
char[] sArray = new char[len];
Arrays.fill(sArray, '0');//开方数初始化为0
for (int pos = 0; pos < len; pos++) {
//从最高开始遍历数组,
//每一位都转化为开方数平方后刚好不大于被开方数的程度
for (char ch = '1'; ch <= '9'; ch++) {
sArray[pos] = ch;
sString = String.valueOf(sArray);
sqrtOfNum = new BigInteger(sString);
sqrtOfNumMul = sqrtOfNum.multiply(sqrtOfNum);
if (sqrtOfNumMul.compareTo(beSqrtNum) == 1) {
sArray[pos] -= 1;
break;
}
}
}
return new BigInteger(String.valueOf(sArray));
}
}
该算法的最坏情况是将循环中所有的数字都遍历完,为 len * 9,因此时间复杂度为 O(n)。