[JAVA] Large integer multiplication (divide and conquer method)

Table of Contents

Introduction

Algorithm ideas

Improve ideas

Specific implementation ideas

Supplementary ideas

Complete code

statement

---

Introduction

Large integer multiplication is a method for computing the multiplication of two very large integers, often beyond what computer hardware can handle directly. In this case, we need to use some special algorithms to deal with this type of problem.

This article will introduce in detail the divide-and-conquer algorithm for large integer multiplication

Algorithm Idea

Split two large integers A and B

Where `A1` and `B1` represent the high-order parts of `A` and `B`, `A0` and `B0` represent the low-order parts, and `n` is the number of digits in the integer.

Simplifying the formula we can get

Here we actually need to calculate the product of the four parts, and in order to reduce the time complexity, generally Partial further simplification to obtain a faster algorithm, namely

According to the above ideas, the entire program for large integer multiplication can be designed.

However, this algorithm has a shortcoming, which is that the digits of the two numbers A and B must be the same. When the digits are different, this method cannot be used. Therefore, this article will further improve the algorithm so that it can be used in basic large integer multiplication. based on optimization.

Improvement Ideas

In order to make the algorithm applicable to a wider range, it is necessary to take into account the different digits of the two large integers.

hypothesis

Where B has x digits and D has y digits

then exists

According to this formula, you can write a program to implement optimized large integer multiplication

Specific implementation ideas

Define the large integer multiplication method. In order to allow the integer to be particularly large, you need to use strings to receive and operate.

public static String largeInt(String X, String Y)

First, get the number of digits of two large integers, and intercept the string XY according to the number of digits to get the values of A, B, C, and D.

int x = X.length();
int y = Y.length();
String A = X.substring(0, x - x / 2);//Intercept the numbers into AB*CD
String B = X.substring(x - x / 2);
String C = Y.substring(0, y - y / 2);
String D = Y.substring(y - y / 2);

According to the previous formula, we need to get the values of AC, AD, BC, and BD respectively.

ABCD is part of the large integer XY, so it can be regarded as a large integer, and nested calling functions are used to calculate its value, that is

String AC = largeInt(A, C);//According to the above formula, calculate each set of multipliers and implement it recursively
String BD = largeInt(B, D);
String AD = largeInt(A, D);
String BC = largeInt(B, C);

Looking back at the formula. In addition to addition, the remaining part also needs to be multiplied by 10 raised to the nth power.

And a decimal integer multiplied by 10 to the nth power, that is, the decimal point is moved one place to the right.

Specific to this question, we only need to add n zeros at the end of the string.

code show as below

 int i;
        for (i = 0; i < x + y; i + + )
            AC = AC + "0";
        for (i = 0; i < x; i + + )
            AD = AD + "0";
        for (i = 0; i < y; i + + )
            BC = BC + "0";

At this point, we have completed the preparation of numbers in all formulas

Next, just add up these string type numbers

We first prepare a string addition function as follows

public static String add(String X, String Y) {//String addition function can add two non-negative arbitrary integers
        int i = X.length() - 1;
        int j = Y.length() - 1;
        int add = 0;
        String sum = "";
        while (i >= 0 || j >= 0 || add != 0) {
            if (i >= 0)
                add = add + X.charAt(i--) - '0';
            if (j >= 0)
                add = add + Y.charAt(j--) - '0';

            sum = sum + String.valueOf(add % 10);
            add = add / 10;
        }
        StringBuilder sb = new StringBuilder(sum);

        return sb.reverse().toString();
    }

Then use this function to add the strings we have obtained

//Adding strings
        String sum = "";
        sum = add(AC, AD);
        sum = add(sum, BC);
        sum = add(sum, BD);

Finally, return the value of sum

but! ! ! it’s not finished yet

Supplementary ideas

We just implemented the general framework of the program

When we continuously call this function nestedly to find the values of AC, AD, BC, and BD, when will it end?

The answer is that it will not end normally

When we intercept an empty string at the end, problems will arise. We need to find the conditions for it to end.

Or create a condition that allows it to end the nested call

The simplest way is to end when the length of one of the strings is less than a certain value, but at this time the length of the other value is not necessarily

For example, if you input two numbers with very different digits at the beginning, you will still make mistakes.

I don’t know if the above expression is clear. It doesn’t matter. Let’s look at the code directly.

if ((x <= 1 || y <= 1) & amp; & amp; (x + y < 5)) {

            int n = Integer.parseInt(X);
            int m = Integer.parseInt(Y);
            return String.valueOf(n * m);//When the length of the two numbers is small, multiply them directly so that the subsequent recursive operation can be stopped.
        }

This means that when the length of the integer is small enough and both integers are relatively small, you can directly use multiplication to get the product.

But it is not enough. We say that when the difference between the two integers passed is too large, an empty string may be passed in during the recursive operation.

At this time, the program cannot run here and an error occurs.

And an empty string multiplied by another value must be 0, so we directly return 0

if (X.isEmpty() || Y.isEmpty())
            return "0";//Determine whether the string is empty. When the difference between the two digits is large, an empty string will appear during the recursive operation. In this case, 0 needs to be returned

At this point the program can run normally

Including multiplying an arbitrarily large positive integer by an arbitrarily large integer or multiplying by 0, and multiplying two positive integers that are very different.

That’s right, it’s a positive integer

Because we have not considered the case of negative numbers here, if we use negative numbers at this time, we will still make an error.

How to solve?

In fact, it is very simple. We only need to remove the negative sign, calculate it using the absolute value of the two numbers, and finally determine whether it is a positive number or a negative number. If it is a negative number, add a negative sign to it.

if (judge % 2 != 0)//When judge=0, the two numbers are positive; when judge=1, one is positive and the other is negative; judge=2, the two numbers are negative
            sum = "-" + sum;

Complete code

package TestProblem;

import java.util.Scanner;

public class LargeInt {
    static int judge = 0;

    public static void main(String[] args) {
        String X, Y;
        Scanner sc = new Scanner(System.in);
        System.out.println("Please enter the first integer");
        X = sc.next();
        System.out.println("Please enter the second integer");
        Y = sc.next();//Get the string XY from the system input
        String sum = "";//Prepare an empty string and receive the result. This is to easily modify the sign when multiplying with negative numbers.
        sum = largeInt(X, Y);//Get the absolute value of the product of two numbers
        if (judge % 2 != 0)//When judge=0, the two numbers are positive; when judge=1, one is positive and the other is negative; judge=2, the two numbers are negative
            sum = "-" + sum;
        System.out.println(X + " × " + Y + " \\
= " + sum);
    }

    public static String largeInt(String X, String Y) {
        if (X.isEmpty() || Y.isEmpty())
            return "0";//Determine whether the string is empty. When the difference between the two digits is large, an empty string will appear during the recursive operation. In this case, 0 needs to be returned.
        if (X.charAt(0) == '-') {
            X = X.substring(1);
            judge + + ;
        }
        if (Y.charAt(0) == '-') {
            Y = Y.substring(1);
            judge + + ;
        }//When a negative sign appears, remove the negative sign and record it
        int x = X.length();
        int y = Y.length();
        if ((x <= 1 || y <= 1) & amp; & amp; (x + y < 5)) {

            int n = Integer.parseInt(X);
            int m = Integer.parseInt(Y);
            return String.valueOf(n * m);//When the length of the two numbers is small, multiply them directly so that the subsequent recursive operation can be stopped.
        }
        String A = X.substring(0, x - x / 2);//Intercept the numbers into AB*CD
        String B = X.substring(x - x / 2);
        String C = Y.substring(0, y - y / 2);
        String D = Y.substring(y - y / 2);
        //AC*10^(x/2 + y/2) + (AD*10^(x/2) + BC*10^(y/2)) + BD
        String AC = largeInt(A, C);//According to the above formula, calculate each set of multipliers and implement it recursively
        String BD = largeInt(B, D);
        String AD = largeInt(A, D);
        String BC = largeInt(B, C);

        int xy0 = x / 2 + y / 2; //Record how many times 10 is multiplied to the power, that is, how many 0s are added at the end
        int x0 = x / 2;
        int y0 = y / 2;

        int i;
        for (i = 0; i < xy0; i + + )
            AC = AC + "0";
        for (i = 0; i < x0; i + + )
            AD = AD + "0";
        for (i = 0; i < y0; i + + )
            BC = BC + "0";
        //At this point, the string is complete, next

        //Adding strings
        String sum = "";
        sum = add(AC, AD);
        sum = add(sum, BC);
        sum = add(sum, BD);

        return sum;

    }

    public static String add(String X, String Y) {//String addition function can add two non-negative arbitrary integers
        int i = X.length() - 1;
        int j = Y.length() - 1;
        int add = 0;
        String sum = "";
        while (i >= 0 || j >= 0 || add != 0) {
            if (i >= 0)
                add = add + X.charAt(i--) - '0';
            if (j >= 0)
                add = add + Y.charAt(j--) - '0';

            sum = sum + String.valueOf(add % 10);
            add = add / 10;
        }
        StringBuilder sb = new StringBuilder(sum);

        return sb.reverse().toString();
    }
}

Statement

This article is based on the author’s personal experience sharing and may not be completely correct.

This article is the author's first blog content. There may be many flaws. You are welcome to correct me.

This article is the author’s original study notes. I look forward to making progress with you all.

The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57070 people are learning the system