大数开根号（蓝桥杯-矩阵翻硬币）

在蓝桥上面交了个题目，测试了java和C++的速度发现差距还是蛮大的，java代码相对比较少但是时间和内存差不多就是十倍的差距了。

上C++版本代码：

#include <cstring>
#include <iostream>

using namespace std;

struct Bigint
{
    int len;
    int arg[1005];
    Bigint()
    {
        len = 1;
        memset(arg, 0,sizeof(arg));
    }
    void print()
    {
        for (int i = len - 1; i >= 0; i--){
            cout<<arg[i];
        }
        cout<<endl;
    }
    void CharToBigint(char *str)
    {
        len = strlen(str);
        for (int i = 0; i < len; i++){
            arg[i] = str[len - i - 1] - 48;
        }
        while(arg[len-1] == 0){
            len--;
        }
    }
    friend bool operator==(Bigint r,Bigint w)
    {
        if (r.len != w.len) return false;
        int i = r.len - 1;
        while (i >= 0){
            if (r.arg[i] != w.arg[i])
                return false;
            i--;
        }
        return true;
    }
    friend bool operator<=(Bigint r,Bigint w)
    {
        if (r.len < w.len) return true;
        else if (w.len < r.len) return false;
        int i = r.len - 1;
        while (i >= 0){
            if (r.arg[i]<w.arg[i])
                return true;
            else if (r.arg[i]>w.arg[i])
                return false;
            i--;
        }
        return true;
    }
    friend Bigint operator+(int r,Bigint w){
        w.arg[0] += r;
        int i = 0;
        while (w.arg[i] >= 10){
            w.arg[i + 1] += w.arg[i] / 10;
            w.arg[i] = w.arg[i] % 10;
            i++;
        }
        if(w.arg[i]) i++;
        w.len = i > w.len ? i : w.len;
        return w;
    }
    friend Bigint operator+(Bigint w,int r)
    {
        w.arg[0] += r;
        int i = 0;
        while (w.arg[i] >= 10){
            w.arg[i + 1] += w.arg[i] / 10;
            w.arg[i] = w.arg[i] % 10;
            i++;
        }
        if(w.arg[i]) i++;
        w.len = i > w.len ? i : w.len;
        return w;
    }
    friend Bigint operator-(Bigint r,Bigint w)
    {
        for (int i = 0; i < r.len; i++){
            if (r.arg[i] >= w.arg[i])
                r.arg[i] = r.arg[i] - w.arg[i];
            else{
                r.arg[i] = r.arg[i] + 10;
                r.arg[i + 1] = r.arg[i + 1] - 1;
                r.arg[i] = r.arg[i] - w.arg[i];
            }
        }
        while (r.arg[r.len - 1] == 0 && r.len > 1)
            r.len--;
        return r;
    }
    friend Bigint operator*(int x,Bigint w)
    {
        Bigint r;
        if(x == 0 || (w.len == 1 && w.arg[0] == 0)){
            return r;
        }
        for (int i = 0; i < w.len; i++){
            r.arg[i] += w.arg[i] * x;
            r.arg[i + 1] += r.arg[i] / 10;
            r.arg[i] = r.arg[i] % 10;
        }
        int i = r.arg[w.len] == 0 ? w.len-1 : w.len;
        while (r.arg[i] >= 10){
            r.arg[i + 1] = r.arg[i] / 10;
            r.arg[i] = r.arg[i] % 10;
            i++;
        }
        r.len = (i >= 0) ? i + 1 : 1;
        return r;
    }
    friend Bigint operator*(Bigint r,Bigint w)
    {
        Bigint v;
        if((r.len == 1 && r.arg[0] == 0)|| (w.len == 1 && w.arg[0] == 0)){
            return v;
        }
        for (int i = 0; i < r.len; i++){
            for (int k = 0; k < w.len; k++){
                v.arg[i + k] += w.arg[k] * r.arg[i];
                v.arg[i + k + 1] += v.arg[i + k] / 10;
                v.arg[i + k] = v.arg[i + k] % 10;
            }
        }
        int i = w.len + r.len - 1;
        i = v.arg[i] == 0 ? i-1 : i;
        while (v.arg[i] >= 10){
            v.arg[i + 1] = v.arg[i] / 10;
            v.arg[i] = v.arg[i] % 10;
            i++;
        }
        v.len = (i >= 0) ? i + 1 : 1;
        return v;
    }
    Bigint sqrt()
    {
        Bigint w,r;
        w.len = r.len = 0;
        int lens = len - 1;
        if(len == 1 && arg[0] == 1)
            return *this;
        r.arg[r.len++] = arg[lens--];
        if (len % 2 == 0)
            r = arg[lens--] + 10 * r;
        while (lens >= -1){
            int i = 0;
            while ((i*(i + 20 * w)) <= r){
                i++;
            }
            i--;
            if (i == -1 || (r.len == 1 && r.arg[0] == 1))
                i = 0;
            r = r - (i*(i + 20 * w));
            w = i + 10 * w;
            if(lens >= 0){
                r = arg[lens--] + 10 * r;
                r = arg[lens--] + 10 * r;
            }
            else
                lens -= 2;
        }
        return w;
    }
};



int main()
{
    char stra[1005],strb[1005];
    while(cin>>stra>>strb)
    {
        Bigint a,b;
        a.CharToBigint(stra);
        b.CharToBigint(strb);
        a = a.sqrt()*b.sqrt();
        a.print();
    }
    return 0;
}

Java版本代码：

package HelloWord;

import java.io.*;
import java.util.*;
import java.math.*;
import java.math.BigInteger;
import java.math.BigDecimal.*;
import java.math.BigInteger.*;

public class HelloWord {
    public static int length(BigInteger a) {
        int length = 0;
        while (a != BigInteger.ZERO) {
            a = a.divide(BigInteger.valueOf(10));
            length++;
        }
        return length;
    }
    public static int GetNumber(BigInteger a,int pos) {
        BigInteger flag = BigInteger.valueOf(10);
        flag = flag.pow(pos - 1);
        a = a.divide(flag);
        a = a.mod(BigInteger.valueOf(10));
        return a.intValue();
    }
    public static BigDecimal sqrt(BigInteger a,int cor) {
        BigInteger w = BigInteger.ZERO;
        BigInteger r = BigInteger.ZERO;
        BigInteger num_10 = BigInteger.valueOf(10);
        BigInteger num_20 = BigInteger.valueOf(20);
        if (a == BigInteger.ONE) {
            return BigDecimal.valueOf(1);
        }
        a = a.multiply(num_10.pow(2*cor));
        int lens = length(a);
        r = BigInteger.valueOf(GetNumber(a,lens--));
        if (lens % 2 == 1)
            r = r.multiply(num_10).add(BigInteger.valueOf(GetNumber(a,lens--)));
        while (lens >= 0) {
            int i = 0;
            BigInteger num_i = BigInteger.valueOf(i);
            while (r.compareTo(w.multiply(num_20).add(num_i).multiply(num_i)) >= 0) {
                num_i = BigInteger.valueOf(++i);
            }
            num_i = BigInteger.valueOf(--i);
            if (i == -1 || r == BigInteger.ONE)
                i = 0;
            r = r.subtract(w.multiply(num_20).add(num_i).multiply(num_i));
            w = w.multiply(num_10).add(num_i);
            if (lens >= 1) {
                r = r.multiply(num_10).add(BigInteger.valueOf(GetNumber(a,lens--)));
                r = r.multiply(num_10).add(BigInteger.valueOf(GetNumber(a,lens--)));
            }
            else
                lens -= 2;
        }
        String str = w.toString();
        StringBuilder strb = new StringBuilder(str);
        strb.insert(strb.length() - cor,'.');
        str = strb.toString();
        return new BigDecimal(str);
    }
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while (cin.hasNext()) {
            String str = cin.next();
            BigInteger a = new BigInteger(str);
            str = cin.next();
            BigInteger b = new BigInteger(str);
            System.out.println(sqrt(a,0).multiply(sqrt(b,0)));
        }
    }
}