1. Divide and conquer
There are two things to understand:(1) The basic idea of the divide and conquer method is to decompose a problem of size n into k smaller sub-problems, these sub-problems are independent of each other and the same as the original problem.
(2) Recursively solve these sub-problems, and then combine the solutions of each sub-problem to obtain the solution of the original problem.The focus of the divide and conquer method is to analyze whether the problem can be divided into smaller sub-problems. The difficulty is how to divide and how to combine the solutions of each sub-problem into the final solution after division. This generally requires the use of mathematical knowledge or other theory.
Take the multiplication of large numbers as an example. There are two large numbers, A and B, both of n digits. To calculate A*B, you need to divide A and B into two equal parts, as shown in the figure below:
Divide A into two equal parts, a1 and a0, and divide B into two equal parts, b1 and b0, both of length n/2. Then there are:
A = a1 * 10^(n/2) + a0
B = b1 * 10^(n/2) + b0
A * B = c2 * 10^n + c1 * 10^(n/2) + c0
in:
c2 = a1 * b1
c1 = a0 * b1 + b0 * a1 = (a1 + a0) * (b1 + b0) – (c2 + c0)
(Minimize multiplication as much as possible, you need to transform c1 into the following formula)
In this way, one division is performed, and then the division is continued recursively. Each division is merged according to the above formula, and finally the final answer can be obtained.2. Realize
(1) Dealing with positive and negative signs
When doing multiplication, it should be two positive numbers, and the sign of the final result can be judged in advance. Finally, you only need to process the result according to the positive and negative signs. The judgment code is as follows:(2) After the symbol is processed, the length problem is dealt with
The length of the two numbers that are not multiplied each time is the same, so some preprocessing is required to process the two multiplied numbers into two numbers of the same length, which requires adding a leading 0, the code as follows:The length of the two numbers must be an exponential multiple of 2, because each division is divided by 2, so there may be 0 supplements in front of the final number, so the final two numbers have the same length, and the length should be the longer distance The number whose length is the closest exponential multiple of 2 (a bit convoluted, but easy to understand). For example
A = 1234334 //length is 7
B = 12343 //length is 5
Then it should look like this:A = 01234334 // The length is 8, 8 is the nearest exponential multiple of 2 to 7, 2^3 = 8
B = 00012343
If the length is greater than 2, the minimum length after processing should be 4, and the length processing code is as follows:At this point, the length n has been processed.
(3) The key part, the divide and conquer method deals with the logic of multiplication of large numbers
Looking back at the previous analysis, first we need to divide it into two equal parts a1, a0 and b1, b0, and then add and subtract according to the formula, which requires the algorithm of adding and subtracting large numbers. The algorithm for adding and subtracting large numbers will not be introduced here, just upload the code directly (the code for subtracting large numbers is slightly longer, so it will not be listed here, and a link to the code will be attached at the end):The addition of large numbers will have a pre-zero processing. What needs to be noted is that when the data is 0 or 0000 (multiple 0s), the final processing result should be 0. The code is as follows:
We noticed that there will be a 10^n operation later, which is actually adding n zeros to the end. The code is as follows:
What is also needed is the conversion processing of strings and integers, the code is as follows:
The last is the logic of multiplication. Recursion first needs an exit. The exit is when the length is 2, as we can see from the code, when the length is 2, we divide it into four numbers a1, a0, b1, b0 of length 1, and then calculate the final result according to the formula.
When the length is not 2, that is, when the length is greater than 2, further recursive division is required. Then calculate the c2, c1, c0 values of each part separately, and finally combine them. code show as below:
//
// Created by Harlan on 2016/11/16.
//
#include <iostream>
#include <malloc.h>
#include <algorithm>
#include <sstream>
using namespace std;
//string string to integer type such as str="1234", converted to integer 1234.
int str2Int(string k) {
int back;
stringstream instr(k);
instr >> back;
return back;
}
string int2Str(int intValue) {
string result;
string stream stream;
stream << intValue;//put int into the stream
stream >> result;//Extract the previously placed int value from the stream
return result;
}
void removePreZero(string & str) {
//Remove the leading 0, you need to consider the case where there is only one 0 or all 0s
if (str. length() == 1) return;
int k = 0;
for (int i = 0; i < str. length(); i ++ ) {
if (str.at(i) == '0') {
k++;
} else {
break;
}
}
if (k == str.length())str = "0";
else {
str = str.substr(k);
}
}
/**
* When adding large numbers, the case of leading 0 is not considered
* @param x
* @param y
* @return
*/
string add(string x, string y) {
string result = "";
//Remove the leading 0
removePreZero(x);
removePreZero(y);
//Reverse the string for easy addition
reverse(x.begin(), x.end());
reverse(y.begin(), y.end());
for (int i = 0, j = 0; j || i < max(y. length(), x. length()); i ++ ) {
int t = j;
if (i < x.length())t + = (x.at(i) - '0');
if (i < y.length())t + = (y.at(i) - '0');
//c.s[c.len + + ] = t % 10;
int q = t % 10;
result.insert(0, int2Str(q));
j = t/10;
}
return result;
}
string subtract(string & amp; x, string & amp; y) {
string result = "";
//Remove the leading 0
removePreZero(x);
removePreZero(y);
int len_x = x. length();
int len_y = y. length();
int len = len_x > len_y ? len_x : len_y;
int *tempResult = (int *) malloc(sizeof(int) * len);
string sign;
if (len_x > len_y) {// x - y is a positive number
sign = " + ";
} else if (len_x < len_y) { //x-y is negative
sign = "-";
} else { //If the length is the same, judge the size of each bit
int i;
for (i = 0; i < len_x; i ++ ) {
if (x.at(i) == y.at(i))continue;
else if (x.at(i) > y.at(i)) {
sign = " + ";
break;
} else {
sign = "-";
break;
}
}
//Indicates that there is no break, and that x == y
if (i == len_x) {
return "0";
}
}
//Reverse the string for easy subtraction
reverse(x.begin(), x.end());
reverse(y.begin(), y.end());
int q = 0;
//If x is large, subtract directly, otherwise use y-x, and finally add a negative sign
for (int i = 0; i < len; i ++ ) {
int aint = i < len_x ? x.at(i) - '0' : 0;
int bint = i < len_y ? y.at(i) - '0' : 0;
if (sign.at(0) == ' + ') {
tempResult[q++] = aint - bint;
} else {
tempResult[q++] = bint - aint;
}
}
for (int i = 0; i < q; i ++ ) {
if (tempResult[i] < 0) {
tempResult[i + 1] -= 1;
tempResult[i] += 10;
}
}
q--;
while (tempResult[q] == 0)q--;
for (int i = q; i >= 0; i--) {
result += int2Str(tempResult[i]);
}
if (sign.at(0) == '-') return sign + result;
return result;
}
/**
* add leading 0
* @param str
* @param zero_num
*/
void addPreZero(string & str, int zero_num) {
for (int i = 0; i < zero_num; i ++ ) str.insert(0, "0");
}
string addLastZero(string str, int zero_num) {
string s = str;
for (int i = 0; i < zero_num; i + + )s + = "0";
return s;
}
/**
* Calculate the product of x and y, can receive int type and string type after overloading
* @param x
* @param y
* @return
*/
string multiply(string & amp; x, string & amp; y) {
bool flag_x = false; // positive
bool flag_y = false;
bool flag; // The sign of the final result
// handle the positive and negative signs first
if (x.at(0) == '-') {//negative
flag_x = true;
x = x.substr(1);
}
if (y.at(0) == '-') {
flag_y = true;
y = y.substr(1);
}
//Both are negative or both are positive, then the final is positive
if ((flag_x & amp; & amp; flag_y) || (!flag_x & amp; & amp; !flag_y)) {
flag = false;
} else {
flag = true;//otherwise the result is negative
}
/**
* Preprocessing, processing x and y into two numbers with the same number of digits
* The length of x and y must be an exponential multiple of 2, so that recursive divide and conquer calculations can be performed
* Therefore, it is necessary to add leading 0s to x and y, and process the length to the minimum feasible length
*
* After processing, the lengths of x and y will be unified
*/
int init_len = 4;
if (x.length() > 2 || y.length() > 2) { // When the length is greater than 2, the minimum length should be 4, so the initial value is 4
if (x. length() >= y. length()) {
while (init_len < x.length())init_len *= 2; //Calculate the final length of the two numbers
// add leading 0
if (x. length() != init_len) {
addPreZero(x, init_len - x. length());
}
addPreZero(y, init_len - y. length());
} else {
while (init_len < y. length())init_len *= 2;
// add leading 0
addPreZero(x, init_len - x. length());
if (y. length() != init_len) {
addPreZero(y, init_len - y. length());
}
}
}
if (x. length() == 1) {
addPreZero(x, 1);
}
if (y. length() == 1) {
addPreZero(y, 1);
}
int n = x. length();
string result;
string a1, a0, b1, b0;
if (n > 1) {
a1 = x.substr(0, n / 2);
a0 = x.substr(n / 2, n);
b1 = y.substr(0, n / 2);
b0 = y.substr(n / 2, n);
}
if (n == 2) { // when the length is 2, end the recursion
int x1 = str2Int(a1);
int x2 = str2Int(a0);
int y1 = str2Int(b1);
int y2 = str2Int(b0);
int z = (x1 * 10 + x2) * (y1 * 10 + y2);
result = int2Str(z);
} else {
string c2 = multiply(a1, b1);
string c0 = multiply(a0, b0);
string temp_c1_1 = add(a0, a1);
string temp_c1_2 = add(b1, b0);
string temp_c1_3 = add(c2, c0);
string temp_c1 = multiply(temp_c1_1, temp_c1_2);
string c1 = subtract(temp_c1, temp_c1_3);
string s1 = addLastZero(c1, n / 2);
string s2 = addLastZero(c2, n);
result = add(add(s1, s2), c0);
}
if (flag) { //result is negative
result.insert(0, "-");
}
return result;
}
string multiply(string x, int y) {
string temp = int2Str(y);
return multiply(x, temp);
}
string multiply(int x, string y) {
string temp = int2Str(x);
return multiply(temp, y);
}
string multiply(int x, int y) {
string temp1 = int2Str(x);
string temp2 = int2Str(y);
return multiply(temp1, temp2);
}
int main() {
int a = -123123123;
int b = -123343;
string result = multiply(a, b);
cout << result << endl;
return 0;
}