# Example of large number multiplication algorithm implemented by C++

• 2020-05-27 06:32:55
• OfStack

The example of this paper describes the large number multiplication algorithm implemented by C++. I will share it with you for your reference as follows:

Last night school entrance examination and written test, masochee sleep, ability is too weak, but I still in the yard farmers pit forward, hope to jump pit as soon as possible, to solve the worry of food, clothing, housing and travel.

The multiplication of large Numbers refers to those Numbers whose multiplication results or multipliers themselves will overflow if they are of type long long. Usually, these Numbers are represented by type string, and numerical multiplication can be realized by means of dynamic resize data structure (vector,string,deque). For normal multiplication, we know that the m digit is multiplied by the n digit, and the resulting digit is in the interval [m+n-1,m+n]. For example, 34*56, we usually calculate it like this:

Multiply 3,4 by 6, record the low carry, and then do the same with 3,4, and 5 until the highest bit of the second multiplier is multiplied out, and the algorithm ends.

So we can save the multiplication of each of the digits, and we'll do the carry conversion.

``````
#include<iostream>
#include<deque>
#include<sstream>
std::string BigNumMultiply(std::string s1,std::string s2){
// Record the end result
std::string res="";
// use deque Because when a carry occurs, data can be inserted in front of the queue, efficiency ratio vector Height, minimum size
std::deque<int> vec(s1.size()+s2.size()-1,0);
for(int i=0;i<s1.size();++i){
for(int j=0;j<s2.size();++j){
vec[i+j]+=(s1[i]-'0')*(s2[j]-'0');// Record the multiplication
}
}
// Carry handle
// Reverse traversal, because the leftmost value is the highest bit, the rightmost value in the lowest bit, carry operation to start from the lowest bit
for(int i=vec.size()-1;i>=0;--i){
int temp=vec[i]+addflag;// Current value plus carry value
vec[i]=temp%10;// The current value
}
// If there is a carry, add the carry to the head of the queue
vec.push_front(t);
}
for(auto c:vec){
std::ostringstream ss;
ss<<c;
res=res+ss.str();
}
return res;
}
int main(){
std::string str1,str2;
while(std::cin>>str1>>str2)
{
std::cout<<str1<<"*"<<str2<<"="<<std::endl;
std::cout<<BigNumMultiply(str1,str2)<<std::endl;
}
return 0;
}

``````