这是模拟竖式乘法的大数乘法的实现没什么可讲的代码仅供参考这里add 函数是大数加法的实现,multiply函数是用二维数组存储乘数各位与被乘数相乘的结果的大数乘法实现,multiplyCompress函数是在上述二维数组中不存储全为0的相乘结果的大数乘法的实现,multiply2是不使用上述二维数组的大数乘法的实现C代码:#includeiostream#includestring#includevector#includealgorithmusingnamespacestd;stringcharToStr(charbe_converted)////////{stringtemp(a);if(be_converted!\0)temp[0]be_converted;elsetemp[0]0;returntemp;}enumclassprefix{left,right,non};pairstring::size_type,pairprefix,string::size_typealignment(stringleft,stringright){prefix has_prefix_zero;string::size_type prefix_zero_length;if(left.size()right.size()){has_prefix_zeroprefix::left;prefix_zero_lengthright.size()-left.size();left.append(prefix_zero_length,0);}elseif(left.size()right.size()){has_prefix_zeroprefix::right;prefix_zero_lengthleft.size()-right.size();right.append(prefix_zero_length,0);}else{has_prefix_zeroprefix::non;}return{left.size(),{has_prefix_zero,prefix_zero_length}};}voiddeletePrefixZero(constpairprefix,string::size_typehas_prefix_zero,stringleft,stringright){if(has_prefix_zero.firstprefix::left){left.erase(left.size()-has_prefix_zero.second);}elseif(has_prefix_zero.firstprefix::right){right.erase(right.size()-has_prefix_zero.second);}}stringadd(stringleft,stringright)//输入倒置,输出倒置{autoralignment(left,right);string::size_type sizer.first;intcarry0;string result;for(string::size_type i0;isize;i){inttempleft[i]-48right[i]-48carry;carrytemp/10;resultto_string(temp%10);}if(carry!0){resultto_string(carry);}deletePrefixZero(r.second,left,right);returnresult;}stringmultiply(conststringleft,conststringright)//输入倒置,输出倒置{if(left0||right0)return0;vectorvectorintadd_matrix(right.size(),vectorint(left.size()1,0));{intcarry0;for(string::size_type i0;iright.size();i){carry0;string::size_type j0;for(;jleft.size();j){inttemp(left[j]-48)*(right[i]-48)carry;add_matrix[i][j]temp%10;carrytemp/10;}add_matrix[i][j]carry;}}string result;string carry0;for(size_t t1;tleft.size()right.size();t){size_t start_group0;longlongstart_indexleft.size();if(tleft.size()1){start_groupt-left.size()-1;}else{start_indext-1;}string temp0;while(start_groupright.size()start_index0){string str_formto_string(add_matrix[start_group][start_index]);if(str_form!0)tempadd(temp,str_form);start_group;--start_index;}if(carry!0)tempadd(temp,carry);resultcharToStr(temp[0]);carrytemp.substr(1,temp.size()-1);if(carry)carry0;}if(result[result.size()-1]0){returnresult.substr(0,result.size()-1);}else{returnresult;}}stringmultiplyCompress(conststringleft,conststringright)//输入倒置,输出倒置,压缩存储版本{if(left0||right0)return0;vectorvectorintadd_matrix;vectorboolis_zero_group(right.size());vectorintbefore_non_zero_zero_num;{intcontinuous_zero0;intcarry0;for(string::size_type i0;iright.size();i){if(right[i]0){is_zero_group[i]true;continuous_zero;continue;}is_zero_group[i]false;before_non_zero_zero_num.push_back(continuous_zero);continuous_zero0;add_matrix.push_back(vectorint(left.size()1));carry0;string::size_type j0;for(;jleft.size();j){inttemp(left[j]-48)*(right[i]-48)carry;add_matrix.back()[j]temp%10;carrytemp/10;}add_matrix.back()[j]carry;}}size_t next_visit_non_zero;intcur_before_zero_num;if(is_zero_group[0]){next_visit_non_zero0;cur_before_zero_num1;}else{next_visit_non_zero1;cur_before_zero_num0;}string result;string carry0;for(size_t t1;tleft.size()right.size();t){size_t start_group0;longlongstart_indexleft.size();if(tleft.size()1){start_groupt-left.size()-1;}else{start_indext-1;}string temp0;if(start_group0){start_index-before_non_zero_zero_num[0];}else{if(is_zero_group[start_group]){start_groupnext_visit_non_zero;start_index-before_non_zero_zero_num[next_visit_non_zero]-cur_before_zero_num;cur_before_zero_num;}else{start_groupnext_visit_non_zero;cur_before_zero_num0;next_visit_non_zero;}}while(start_groupbefore_non_zero_zero_num.size()start_index0){string str_formto_string(add_matrix[start_group][start_index]);if(str_form!0)tempadd(temp,str_form);start_group;if(start_group!before_non_zero_zero_num.size()){start_index-before_non_zero_zero_num[start_group]1;}}if(carry!0)tempadd(temp,carry);resultcharToStr(temp[0]);carrytemp.substr(1,temp.size()-1);if(carry)carry0;}if(result[result.size()-1]0){returnresult.substr(0,result.size()-1);}else{returnresult;}}stringmultiply2(conststringleft,conststringright){if(left0||right0)return0;string result;string carry0;for(size_t t1;tleft.size()right.size()-1;t){size_t start_group0;longlongstart_indexleft.size()-1;if(tleft.size()){start_groupt-left.size();}else{start_indext-1;}string temp0;while(start_groupright.size()start_index0){string medto_string(static_castlonglong((right[start_group]-48)*(left[start_index]-48)));reverse(med.begin(),med.end());if(med!0)tempadd(temp,med);start_group;--start_index;}if(carry!0)tempadd(temp,carry);resultcharToStr(temp[0]);carrytemp.substr(1,temp.size()-1);if(carry)carry0;}result.append(carry);if(result[result.size()-1]0){returnresult.substr(0,result.size()-1);}else{returnresult;}}intmain(){string left123;string right456;reverse(left.begin(),left.end());reverse(right.begin(),right.end());string resultmultiply(left,right);reverse(result.begin(),result.end());coutmultiply:;coutresultendl;string result2multiply2(left,right);coutmultiply2:;reverse(result2.begin(),result2.end());coutresult2endl;/*string result3 doKaratsubaMultiply(left, right, true); cout Karatsuba:; reverse(result3.begin(), result3.end()); cout result3 endl;*/string result4multiplyCompress(left,right);coutCompress:;reverse(result4.begin(),result4.end());coutresult4endl;for(inti0;i10000;i){for(intj1000;j1100;j){string leftto_string(i);string rightto_string(j);reverse(left.begin(),left.end());reverse(right.begin(),right.end());couti*jendl;string m_rmultiply(right,left);reverse(m_r.begin(),m_r.end());coutmultiply:;coutm_rendl;string m_r2multiplyCompress(right,left);coutCompress:;reverse(m_r2.begin(),m_r2.end());coutm_r2endl;if(m_rm_r2){cout运算结果正确endl;}else{coutERROR:运算结果错误!endl;exit(-1);}coutendl;}}} 
长河君 · 2026/9/6 15:27:24 · 阅读 1.2k 朴素大数乘法的C++实现
这是模拟竖式乘法的大数乘法的实现没什么可讲的代码仅供参考这里add 函数是大数加法的实现,multiply函数是用二维数组存储乘数各位与被乘数相乘的结果的大数乘法实现,multiplyCompress函数是在上述二维数组中不存储全为0的相乘结果的大数乘法的实现,multiply2是不使用上述二维数组的大数乘法的实现C代码:#includeiostream#includestring#includevector#includealgorithmusingnamespacestd;stringcharToStr(charbe_converted)////////{stringtemp(a);if(be_converted!\0)temp[0]be_converted;elsetemp[0]0;returntemp;}enumclassprefix{left,right,non};pairstring::size_type,pairprefix,string::size_typealignment(stringleft,stringright){prefix has_prefix_zero;string::size_type prefix_zero_length;if(left.size()right.size()){has_prefix_zeroprefix::left;prefix_zero_lengthright.size()-left.size();left.append(prefix_zero_length,0);}elseif(left.size()right.size()){has_prefix_zeroprefix::right;prefix_zero_lengthleft.size()-right.size();right.append(prefix_zero_length,0);}else{has_prefix_zeroprefix::non;}return{left.size(),{has_prefix_zero,prefix_zero_length}};}voiddeletePrefixZero(constpairprefix,string::size_typehas_prefix_zero,stringleft,stringright){if(has_prefix_zero.firstprefix::left){left.erase(left.size()-has_prefix_zero.second);}elseif(has_prefix_zero.firstprefix::right){right.erase(right.size()-has_prefix_zero.second);}}stringadd(stringleft,stringright)//输入倒置,输出倒置{autoralignment(left,right);string::size_type sizer.first;intcarry0;string result;for(string::size_type i0;isize;i){inttempleft[i]-48right[i]-48carry;carrytemp/10;resultto_string(temp%10);}if(carry!0){resultto_string(carry);}deletePrefixZero(r.second,left,right);returnresult;}stringmultiply(conststringleft,conststringright)//输入倒置,输出倒置{if(left0||right0)return0;vectorvectorintadd_matrix(right.size(),vectorint(left.size()1,0));{intcarry0;for(string::size_type i0;iright.size();i){carry0;string::size_type j0;for(;jleft.size();j){inttemp(left[j]-48)*(right[i]-48)carry;add_matrix[i][j]temp%10;carrytemp/10;}add_matrix[i][j]carry;}}string result;string carry0;for(size_t t1;tleft.size()right.size();t){size_t start_group0;longlongstart_indexleft.size();if(tleft.size()1){start_groupt-left.size()-1;}else{start_indext-1;}string temp0;while(start_groupright.size()start_index0){string str_formto_string(add_matrix[start_group][start_index]);if(str_form!0)tempadd(temp,str_form);start_group;--start_index;}if(carry!0)tempadd(temp,carry);resultcharToStr(temp[0]);carrytemp.substr(1,temp.size()-1);if(carry)carry0;}if(result[result.size()-1]0){returnresult.substr(0,result.size()-1);}else{returnresult;}}stringmultiplyCompress(conststringleft,conststringright)//输入倒置,输出倒置,压缩存储版本{if(left0||right0)return0;vectorvectorintadd_matrix;vectorboolis_zero_group(right.size());vectorintbefore_non_zero_zero_num;{intcontinuous_zero0;intcarry0;for(string::size_type i0;iright.size();i){if(right[i]0){is_zero_group[i]true;continuous_zero;continue;}is_zero_group[i]false;before_non_zero_zero_num.push_back(continuous_zero);continuous_zero0;add_matrix.push_back(vectorint(left.size()1));carry0;string::size_type j0;for(;jleft.size();j){inttemp(left[j]-48)*(right[i]-48)carry;add_matrix.back()[j]temp%10;carrytemp/10;}add_matrix.back()[j]carry;}}size_t next_visit_non_zero;intcur_before_zero_num;if(is_zero_group[0]){next_visit_non_zero0;cur_before_zero_num1;}else{next_visit_non_zero1;cur_before_zero_num0;}string result;string carry0;for(size_t t1;tleft.size()right.size();t){size_t start_group0;longlongstart_indexleft.size();if(tleft.size()1){start_groupt-left.size()-1;}else{start_indext-1;}string temp0;if(start_group0){start_index-before_non_zero_zero_num[0];}else{if(is_zero_group[start_group]){start_groupnext_visit_non_zero;start_index-before_non_zero_zero_num[next_visit_non_zero]-cur_before_zero_num;cur_before_zero_num;}else{start_groupnext_visit_non_zero;cur_before_zero_num0;next_visit_non_zero;}}while(start_groupbefore_non_zero_zero_num.size()start_index0){string str_formto_string(add_matrix[start_group][start_index]);if(str_form!0)tempadd(temp,str_form);start_group;if(start_group!before_non_zero_zero_num.size()){start_index-before_non_zero_zero_num[start_group]1;}}if(carry!0)tempadd(temp,carry);resultcharToStr(temp[0]);carrytemp.substr(1,temp.size()-1);if(carry)carry0;}if(result[result.size()-1]0){returnresult.substr(0,result.size()-1);}else{returnresult;}}stringmultiply2(conststringleft,conststringright){if(left0||right0)return0;string result;string carry0;for(size_t t1;tleft.size()right.size()-1;t){size_t start_group0;longlongstart_indexleft.size()-1;if(tleft.size()){start_groupt-left.size();}else{start_indext-1;}string temp0;while(start_groupright.size()start_index0){string medto_string(static_castlonglong((right[start_group]-48)*(left[start_index]-48)));reverse(med.begin(),med.end());if(med!0)tempadd(temp,med);start_group;--start_index;}if(carry!0)tempadd(temp,carry);resultcharToStr(temp[0]);carrytemp.substr(1,temp.size()-1);if(carry)carry0;}result.append(carry);if(result[result.size()-1]0){returnresult.substr(0,result.size()-1);}else{returnresult;}}intmain(){string left123;string right456;reverse(left.begin(),left.end());reverse(right.begin(),right.end());string resultmultiply(left,right);reverse(result.begin(),result.end());coutmultiply:;coutresultendl;string result2multiply2(left,right);coutmultiply2:;reverse(result2.begin(),result2.end());coutresult2endl;/*string result3 doKaratsubaMultiply(left, right, true); cout Karatsuba:; reverse(result3.begin(), result3.end()); cout result3 endl;*/string result4multiplyCompress(left,right);coutCompress:;reverse(result4.begin(),result4.end());coutresult4endl;for(inti0;i10000;i){for(intj1000;j1100;j){string leftto_string(i);string rightto_string(j);reverse(left.begin(),left.end());reverse(right.begin(),right.end());couti*jendl;string m_rmultiply(right,left);reverse(m_r.begin(),m_r.end());coutmultiply:;coutm_rendl;string m_r2multiplyCompress(right,left);coutCompress:;reverse(m_r2.begin(),m_r2.end());coutm_r2endl;if(m_rm_r2){cout运算结果正确endl;}else{coutERROR:运算结果错误!endl;exit(-1);}coutendl;}}}