Cartoon: how to multiply large integers? (integrated version)

Some time ago , A cartoon about the small sum of grey numbers was published , If you haven't seen it, you can have a look first ：

comic ： How to add big integers ？（ Revised edition ）

that , How to realize the multiplication of large integers ？

At first , Xiaohui thinks that as long as the idea of adding large integers is done a little deformation , You can easily multiply large integers . But with further study , Xiaohui found out that things are not so simple ......

————— the second day —————

How to list the multiplication column ？ With 93281 X 2034 For example , The vertical form is as follows ：

In the program , We can use int Type of the array , Store two large integers by bit , Then the elements in the array are calculated one by one like the primary vertical .

The calculation of the multiplication column can be roughly divided into two steps ：

1. Integers B Every digit and integer of A All the digits are multiplied in turn , Get an intermediate result .

2. All the intermediate results add up , Get the final result .

/**
 *  The product of large integers 
 * @param bigNumberA   Large integer A
 * @param bigNumberB   Large integer B
 */
public static String multiply(String bigNumberA, String bigNumberB) {
    //1. Store two large integers in reverse order , The length of the array is equal to the sum of the lengths of two integers 
    int lengthA = bigNumberA.length();
    int lengthB = bigNumberB.length();
    int[] arrayA = new int[lengthA];
    for(int i=0; i< lengthA; i++){
        arrayA[i] = bigNumberA.charAt(lengthA-1-i) - '0';
    }
    int[] arrayB = new int[lengthB];
    for(int i=0; i< lengthB; i++){
        arrayB[i] = bigNumberB.charAt(lengthB-1-i) - '0';
    }
    //2. structure result Array , The length of the array is equal to the sum of the lengths of two integers 
    int[] result = new int[lengthA+lengthB];
    //3. Nested loop , Integers B Each bit of, in turn, is an integer A Multiply all the digits of , And add up the results 
    for(int i=0;i<lengthB;i++) {
        for(int j=0;j<lengthA;j++) {
            // Integers B A bit and an integer of A Multiply one of the two 
            result[i+j] += arrayB[i]*arrayA[j];
            // If result One is greater than 10, Then carry , The number of carry is the number of bits divided by 10 The business of 
            if(result[i+j] >= 10){
                result[i+j+1] += result[i+j]/10;
                result[i+j] = result[i+j]%10;
            }
        }
    }
    //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();
}

public static void main(String[] args) {
    String x = "3338429042340042304302404";
    String y = "12303231";
    System.out.println(multiply(x, y));
}

Copy

————————————

below , There will be some brain burning in our derivation , Please sit down and hold on ~~

Large integers go from high to low , It's divided into two parts . Set integer 1 The high part of is A, The lower part is B; Integers 2 The high part of is C, The lower part is D, So there's the following equation ：

If we abstract the length of a large integer as n, that ：

therefore , Integers 1 And integers 2 The product of can be written in the following form ：

In this way , The original length was n Of large integers 1 Times product , Transformed into length n/2 Of large integers 4 Times product （AC,AD,BC,BD）.

What is? master And the theorem ？

master The English name of the theorem is master theorem, It's for many The recurrence relation obtained by divide and conquer method Provides a progressive time complexity analysis .

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 ：

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

According to the conclusion just reached , The multiplication of two large integers is split into four smaller products ：

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

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

among f(n) yes 4 The operation scale of adding the product results ,f(n) The incremental time complexity of is obviously O(n).

Bring this relationship to master The formula of the theorem T(n) = a T(n / b) + f(n) among ,

here a=4, b=2.

here , 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 does it fit ？ The derivation process is as follows ：

So our average time complexity is ：

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—————