当前位置:网站首页>Cartoon: how to multiply large integers? (next)
Cartoon: how to multiply large integers? (next)
2022-07-05 17:28:00 【Small ash】
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));
}
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—————
边栏推荐
- 叩富网开期货账户安全可靠吗?怎么分辨平台是否安全?
- 编译libssh2报错找不到openssl
- 机器学习01:绪论
- 【7.7直播预告】《SaaS云原生应用典型架构》大咖讲师教你轻松构建云原生SaaS化应用,难题一一击破,更有华为周边好礼等你领!
- 漫画:一道数学题引发的血案
- 普通程序员看代码,顶级程序员看趋势
- 【jmeter】jmeter脚本高级写法:接口自动化脚本内全部为变量,参数(参数可jenkins配置),函数等实现完整业务流测试
- Check the WiFi password connected to your computer
- MySQL queries the latest qualified data rows
- 2022 年 Q2 加密市场投融资报告:GameFi 成为投资关键词
猜你喜欢
随机推荐
WR | Jufeng group of West Lake University revealed the impact of microplastics pollution on the flora and denitrification function of constructed wetlands
机器学习02:模型评估
ICML 2022 | Meta提出魯棒的多目標貝葉斯優化方法,有效應對輸入噪聲
蚂蚁金服的暴富还未开始,Zoom的神话却仍在继续!
一个满分的项目文档是如何书写的|得物技术
网上办理期货开户安全吗?网上会不会骗子比较多?感觉不太靠谱?
[binary tree] insufficient nodes on the root to leaf path
MySql 查询符合条件的最新数据行
How MySQL uses JSON_ Extract() takes JSON value
漫画:寻找无序数组的第k大元素(修订版)
Embedded UC (UNIX System Advanced Programming) -3
Winedt common shortcut key modify shortcut key latex compile button
这个17岁的黑客天才,破解了第一代iPhone!
通过proc接口调试内核代码
Learn about MySQL transaction isolation level
Understand the usage of functions and methods in go language
北京内推 | 微软亚洲研究院机器学习组招聘NLP/语音合成等方向全职研究员
Mysql5.6 parsing JSON strings (supporting complex nested formats)
[Jianzhi offer] 63 Maximum profit of stock
漫画:一道数学题引发的血案