林俊海的博客

超級大菜鳥，每天要自強！

[JAVA]大數開平方(模擬手算的方法)

在 CSDN 看到的问题。　要求算出开平方结果的精确整数部分
想了想，想不到别的好的方法　就用了摸拟手算的方法

public static void main(String[] args) {
        System.out.print("sqrt(1)=" + sqrt("1"));
        System.out.print("\tsqrt(25)=" + sqrt("25"));
        System.out.print("\tsqrt(26)=" + sqrt("26"));  // sqrt(26)==5 呵呵,因为只有整数部分
        System.out.print("\tsqrt(100)=" + sqrt("100"));
        System.out.println("\tsqrt(144)=" + sqrt("144"));
        
        // 生成一个 5000 位以内的数
        StringBuffer sb = new StringBuffer("");
        Random rand = new Random();
        int length = rand.nextInt(5000)+1;
        for (int i=0; i<length; i++)
            sb.append(rand.nextInt(10));
        String theNumber = sb.toString();

System.out.println("n:" + sb.toString());
        System.out.println("位数:" + length);

// 开方
        long t = System.currentTimeMillis();
        BigInteger result = sqrt(theNumber);
        t = System.currentTimeMillis()-t;

System.out.println("sqrt(n)=" + result.toString());
        System.out.println("用时:" + t + "毫秒");
    }

public static BigInteger sqrt(String theNumber) {
        int length = theNumber.length(), i;
        BigInteger res = BigInteger.ZERO;
        BigInteger twenty = BigInteger.valueOf(20);
        BigInteger t, x=BigInteger.ZERO, v, few=BigInteger.ZERO;
        BigInteger hg = BigInteger.valueOf(100);

String tmpString = null;
        int pos = 2-length%2;
        tmpString = theNumber.substring(0, pos);
        while (true) {
            v = few.multiply(hg).add(BigInteger.valueOf(Integer.parseInt(tmpString)));
            if (res.compareTo(BigInteger.ZERO)==0) i=9;
            else i = v.divide(res.multiply(twenty)).intValue();
            for (; i>=0; i--) {
                t = res.multiply(twenty).add(BigInteger.valueOf(i)).multiply(BigInteger.valueOf(i));
                if (t.compareTo(v)<=0) {
                    x = t;
                    break;
                }
            }
            res = res.multiply(BigInteger.TEN).add(BigInteger.valueOf(i));
            few = v.subtract(x);
            pos++;
            if (pos>length) break;
            tmpString = theNumber.substring(pos-1, ++pos);
        }
        return res;
    }

posted on 2009-05-21 03:55 林俊海閱讀(1045) 評論(0) 編輯收藏

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理

Blog Stats

News

隨筆分類(28)

文章分類(4)

隨筆檔案(53)

文章檔案(4)

相冊

相關鏈接

林俊海的博客