Cartoon: how to multiply large integers? (I) revised version

In the new cartoon released by Xiaohui on Monday , There are two small problems ：

1. about master The third condition of the theorem is incorrectly stated , Should be a+ε, instead of a-ε.

2. Divide and conquer T(n) and T(n/2) The relationship between master The first condition of the theorem , Calculation ε The process of value is wrong .

These two questions have been revised this time , Thank you very much for your correction .

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 ：

—————END—————