当前位置:网站首页>Cartoon: how to multiply large integers? (integrated version)
Cartoon: how to multiply large integers? (integrated version)
2022-07-05 17:28:00 【Small ash】
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));
}
————————————
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));
}
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—————
边栏推荐
- Use JDBC technology and MySQL database management system to realize the function of course management, including adding, modifying, querying and deleting course information.
- Force deduction solution summary 729- my schedule I
- Embedded-c Language-1
- 兰空图床苹果快捷指令
- CMake教程Step6(添加自定义命令和生成文件)
- [Jianzhi offer] 61 Shunzi in playing cards
- flask解决CORS ERR 问题
- Is it safe and reliable to open futures accounts on koufu.com? How to distinguish whether the platform is safe?
- First day of learning C language
- 腾讯音乐上线新产品“曲易买”,提供音乐商用版权授权
猜你喜欢
thinkphp模板的使用
stirring! 2022 open atom global open source summit registration is hot!
MySQL queries the latest qualified data rows
ICML 2022 | Meta提出鲁棒的多目标贝叶斯优化方法,有效应对输入噪声
MySQL之知识点(六)
Summary of optimization scheme for implementing delay queue based on redis
Complete solution instance of Oracle shrink table space
Embedded -arm (bare board development) -2
MySql 查询符合条件的最新数据行
IDC报告:腾讯云数据库稳居关系型数据库市场TOP 2!
随机推荐
[Jianzhi offer] 62 The last remaining number in the circle
Read the basic grammar of C language in one article
In depth understanding of redis memory obsolescence strategy
漫画:如何实现大整数相乘?(下)
Tita performance treasure: how to prepare for the mid year examination?
华为云云原生容器综合竞争力,中国第一!
thinkphp3.2.3
About JSON parsing function JSON in MySQL_ EXTRACT
Flow characteristics of kitchen knife, ant sword, ice scorpion and Godzilla
Judge whether a number is a prime number (prime number)
easyNmon使用汇总
mysql中取出json字段的小技巧
ternary operator
CMake教程Step4(安装和测试)
mysql5.6解析JSON字符串方式(支持复杂的嵌套格式)
蚂蚁金服的暴富还未开始,Zoom的神话却仍在继续!
Mysql5.6 parsing JSON strings (supporting complex nested formats)
Debug kernel code through proc interface
thinkphp模板的使用
漫画:如何实现大整数相乘?(整合版)