對大數（BigInteger）進行開方運算

在 BigInteger 中沒有對 getSqrt(BigInteger num) 方法，在對大數進行開方處理的時候比較麻煩，前幾天在做藍橋杯訓練的時候看到了這個算法，時間複雜度較低，感覺挺好的，分享一下，^_^ ……

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)/F + "s");
        System.out.println("運算結果 = " + (sqrt.compareTo(n1) == ));
    }

    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 %  == ) len = mlen / ;
        else len = mlen /  + ;
        char[] sArray = new char[len];
        Arrays.fill(sArray, '0');//開方數初始化為0
        for (int pos = ; 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) == ) {
                    sArray[pos] -= ;
                    break;
                }
            }
        }
        return new BigInteger(String.valueOf(sArray));
    }
}
           

該算法的最壞情況是将循環中所有的數字都周遊完，為 len * 9，是以時間複雜度為 O(n)。

帥照：