How to realize large integer multiplication and divide-and-conquer algorithm

This article mainly explains "how to realize large integer multiplication and divide and conquer algorithm". Interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Next let the editor to take you to learn "how to achieve large integer multiplication and divide and conquer algorithm"!

General multiplier operation

There is a relatively simple and easy to understand method for multiplier operation, and we can use the column vertical calculation method learned in primary school to carry out multiplication.

Column vertical multiplication

With reference to the column vertical calculation method in the figure above, we implement it in code.

# include # include std::string multiply (std::string a, std::string b) {std::string result = ""; int row = b.size (); int col = a.size () + 1; int tmp [row] [col]; memset (tmp,0, sizeof (int) * row*col); reverse (a.begin (), a.end ()) Reverse (b.begin (), b.end ()); for (int I = 0; I

< b.size(); i++) { for(int j = 0; j < a.size(); j++) { std::string bit_a = std::string(1, a.at(j)); std::string bit_b = std::string(1, b.at(i)); tmp[i][j] += std::stoi(bit_a) * std::stoi(bit_b); tmp[i][j+1] = tmp[i][j] / 10; tmp[i][j] %= 10; } } int N = a.size() + b.size(); int sum[N]; memset(sum, 0, sizeof(int)*N); for(int n = 0; n < N; n++) { int i = 0; int j = n; while (i = 0 ) { if(i < row && j < col) { sum[n] += tmp[i][j]; } i++; j--; } if( n+1 < N ) { sum[n+1] = sum[n] / 10; sum[n] %= 10; } } bool zeroStartFlag = true; for (int i = N-1; i >

= 0; return result; -) {if (zeroStartFlag [I] = = 0 & & zeroStartFlag) {continue;} zeroStartFlag = false; result.append (std::to_string (Sumi));} return result;} int main () {std::string a = "3456"; std::string b = "1234" Std::string result = multiply (a, b); std::cout