Cartoon: how to multiply large integers? (next)

How to use the program to realize the multiplication of large integers ？

In the last article comic ： How to realize the multiplication of large integers ？（ On ） Revised edition among , We introduced two ideas ：

1. It's like a column , Multiply two integers bit by bit

The time complexity of this idea is O（n^2）.

2. Using divide and conquer , Divide each large integer into high and low parts , Into four smaller products .

The time complexity of this idea is also O（n^2）.

that , What kind of optimization plan do you have , It can make the time complexity better than O（n^2） Well ？ Let's study it today .

How to make adjustments ？ It's very simple , Even primary school students can ：

thus , The original 4 The multiplication and 3 Time in addition , Turned into 3 The multiplication and 6 Time in addition .

thus , What's the complexity of time ？

Suppose two lengths are n Multiply the large integers of , The overall operation scale is T(n) .

Just now we said , Multiplication of two large integers can be split into three smaller products ,

So in the first partition ,T(n) and T(n/2) Has the following relation ：

T(n) = 3T(n/2) + f(n)

among f(n) yes 6 The operation scale of sub addition ,f(n) The incremental time complexity of is obviously O(n).

Now let's review master Theorem ：

Let's set a constant a >= 1,b > 1, If the overall computational scale of an algorithm T(n) = a T(n / b) + f(n), Then there are the following rules ：

about T(n) = 3T(n/2) + f(n) In this relation , a=3, b=2.

hold a and b Value , as well as f(n) Time complexity brought to master The first law of the theorem , That's the following rule ：

It's just the right thing to do .

How to meet the conditions ？ The derivation process is as follows ：

So our average time complexity is ：

2 and 1.59 The gap between the two seems small , But when the integer length is very large , The performance of the two methods will be very different .

Here's the implementation code . Our code is very complex , For reference only , The most important thing is the way to solve the problem ：

/**
 *  Multiplication of large integers 
 * @param bigNumberA   Large integer A
 * @param bigNumberB   Large integer B
 */
public static String bigNumberMultiply(String bigNumberA, String bigNumberB) {
    boolean isNegative = false;
    if ((bigNumberA.startsWith("-") && bigNumberB.startsWith("-"))
            || (!bigNumberA.startsWith("-") && !bigNumberB.startsWith("-"))) {
        //  Two numbers with the same sign 
        bigNumberA = bigNumberA.replaceAll("-", "");
        bigNumberB = bigNumberB.replaceAll("-", "");
    } else if ((bigNumberA.startsWith("-") && !bigNumberB.startsWith("-"))
            || (!bigNumberA.startsWith("-") && bigNumberB.startsWith("-"))) {
        //  Two numbers with different symbols 
        bigNumberA = bigNumberA.replace("-", "");
        bigNumberB = bigNumberB.replace("-", "");
        isNegative = true;
    }
    //  If the sum of the two lengths is less than 10, Direct multiplication return 
    if (bigNumberA.length() + bigNumberB.length() < 10) {
        //  Calculate the product 
        int tmp = (Integer.parseInt(bigNumberA) * Integer.parseInt(bigNumberB));
        if (tmp == 0) {
            return "0";
        }
        String value = String.valueOf(tmp);
        if(isNegative){
            value = "-" + value;
        }
        return value;
    }
    //  The formula  AC * 10^n+((A-B)(D-C)+AC+BD) * 10^(n/2)+BD In the middle of a,b,c,d
    String a, b, c, d;
    if (bigNumberA.length() == 1) {
        a = "0";
        b = bigNumberA;
    } else {
        if (bigNumberA.length() % 2 != 0) {
            bigNumberA = "0" + bigNumberA;
        }
        a = bigNumberA.substring(0, bigNumberA.length() / 2);
        b = bigNumberA.substring(bigNumberA.length() / 2);
    }
    if (bigNumberB.length() == 1) {
        c = "0";
        d = bigNumberB;
    } else {
        if (bigNumberB.length() % 2 != 0) {
            bigNumberB = "0" + bigNumberB;
        }
        c = bigNumberB.substring(0, bigNumberB.length() / 2);
        d = bigNumberB.substring(bigNumberB.length() / 2);
    }
    //  Value according to the maximum number of digits , To determine the number of zeros 
    int n = bigNumberA.length() >= bigNumberB.length() ? bigNumberA.length() : bigNumberB.length();

    //t1,t2 Is the result of intermediate operation ,t3 Is the result of multiplication 
    String t1, t2, t3;
    String ac = bigNumberMultiply(a, c);
    String bd = bigNumberMultiply(b, d);

    //t1=(A-B)(D-C)
    t1 = bigNumberMultiply(bigNumberSubtract(a, b), bigNumberSubtract(d, c));
    //t2=(A-B)(D-C)+AC+BD
    t2 = bigNumberSum(bigNumberSum(t1, ac), bd);
    //t3= AC * 10^n+((A-B)(D-C)+AC+BD) * 10^(n/2)+BD
    t3 = bigNumberSum(bigNumberSum(Power10(ac, n), Power10(t2, n/2)), bd).replaceAll("^0+", "");
    if (t3 == "")
        return "0";
    if(isNegative){
        return "-" + t3;
    }
    return t3;
}



/**
 *  Large integer addition 
 * @param bigNumberA   Large integer A
 * @param bigNumberB   Large integer B
 */
public static String bigNumberSum(String bigNumberA, String bigNumberB) {

    if (bigNumberA.startsWith("-") && !bigNumberB.startsWith("-")) {
        return bigNumberSubtract(bigNumberB, bigNumberA.replaceAll("^-", ""));
    } else if (!bigNumberA.startsWith("-") && bigNumberB.startsWith("-")) {
        return bigNumberSubtract(bigNumberA, bigNumberB.replaceAll("^-", ""));
    } else if (bigNumberA.startsWith("-") && bigNumberB.startsWith("-")) {
        return "-" + bigNumberSum(bigNumberA.replaceAll("^-", ""), bigNumberB.replaceAll("^-", ""));
    }

    //1. Store two large integers in reverse order , The length of the array is equal to the larger number of integers +1
    int maxLength = bigNumberA.length() > bigNumberB.length() ? bigNumberA.length() : bigNumberB.length();
    int[] arrayA = new int[maxLength+1];
    for(int i=0; i< bigNumberA.length(); i++){
        arrayA[i] = bigNumberA.charAt(bigNumberA.length()-1-i) - '0';
    }
    int[] arrayB = new int[maxLength+1];
    for(int i=0; i< bigNumberB.length(); i++){
        arrayB[i] = bigNumberB.charAt(bigNumberB.length()-1-i) - '0';
    }
    //2. structure result Array , The length of the array is equal to the larger number of integers +1
    int[] result = new int[maxLength+1];
    //3. Traversal array , Add bit by bit 
    for(int i=0; i<result.length; i++){
        int temp = result[i];
        temp += arrayA[i];
        temp += arrayB[i];
        // Judge whether to carry 
        if(temp >= 10){
            temp -= 10;
            result[i+1] = 1;
        }
        result[i] = temp;
    }
    //4. hold result The array is reversed again and converted to String
    StringBuilder sb = new StringBuilder();
    // Whether to find the most significant bit of a large integer 
    boolean findFirst = false;
    for (int i = result.length - 1; i >= 0; i--) {
        if(!findFirst){
            if(result[i] == 0){
                continue;
            }
            findFirst = true;
        }
        sb.append(result[i]);
    }
    return sb.toString();
}


/**
 *  Subtraction of large integers 
 * @param bigNumberA   Large integer A
 * @param bigNumberB   Large integer B
 */
public static String bigNumberSubtract(String bigNumberA, String bigNumberB) {
    int compareResult = compare(bigNumberA, bigNumberB);
    if (compareResult == 0) {
        return "0";
    }
    boolean isNegative = false;
    if (compareResult == -1) {
        String tmp = bigNumberB;
        bigNumberB = bigNumberA;
        bigNumberA = tmp;
        isNegative = true;
    }
    //1. Store two large integers in reverse order , The length of the array is equal to the larger number of integers +1
    int maxLength = bigNumberA.length() > bigNumberB.length() ? bigNumberA.length() : bigNumberB.length();
    int[] arrayA = new int[maxLength+1];
    for(int i=0; i< bigNumberA.length(); i++){
        arrayA[i] = bigNumberA.charAt(bigNumberA.length()-1-i) - '0';
    }
    int[] arrayB = new int[maxLength+1];
    for(int i=0; i< bigNumberB.length(); i++){
        arrayB[i] = bigNumberB.charAt(bigNumberB.length()-1-i) - '0';
    }
    //2. structure result Array , The length of the array is equal to the larger number of integers +1
    int[] result = new int[maxLength+1];
    //3. Traversal array , Add bit by bit 
    for(int i=0; i<result.length; i++){
        int temp = result[i];
        temp += arrayA[i];
        temp -= arrayB[i];
        // Judge whether to carry 
        if(temp < 0){
            temp += 10;
            result[i+1] = -1;
        }
        result[i] = temp;
    }
    //4. hold result The array is reversed again and converted to String
    StringBuilder sb = new StringBuilder();
    // Whether to find the most significant bit of a large integer 
    boolean findFirst = false;
    for (int i = result.length - 1; i >= 0; i--) {
        if(!findFirst){
            if(result[i] == 0){
                continue;
            }
            findFirst = true;
        }
        sb.append(result[i]);
    }
    String value = sb.toString();
    if (isNegative) {
        value = "-" + value;
    }
    return value;
}


//  Compare the size 
private static int compare(String x, String y) {
    if (x.length() > y.length()) {
        return 1;
    } else if (x.length() < y.length()) {
        return -1;
    } else {
        for (int i = 0; i < x.length(); i++) {
            if (x.charAt(i) > y.charAt(i)) {
                return 1;
            } else if (x.charAt(i) < y.charAt(i)) {
                return -1;
            }
        }
        return 0;
    }
}


//  expand 10 Of n Times the power 
public static String Power10(String num, int n) {
    for (int i = 0; i < n; i++) {
        num += "0";
    }
    return num;
}


public static void main(String[] args) {
    String x = "1513143";
    String y = "9345963";
    System.out.println(bigNumberMultiply(x, y));
}

Copy

It should be noted that , This implementation code is only applicable to the case that two large integers are equal in length . If you want to multiply integers of different lengths , Just make small changes to the code , Interested partners didn't give it a try .

Some supplements ：

1. The code at the end of the article , Through the code changes of online technology blog , Just for your reference .

2. About the fast Fourier transform , Those who are interested in further research can refer to 《 Introduction to algorithms 》 The first 30 Content of Chapter .

—————END—————