分治法解决大整数乘法

一时失言乱红尘 2022-05-11 01:36 200阅读 0赞

# 大整数乘法 #

最近学习了算法设计与分析课程，留了一道大整数乘法的问题，使用了分治法思想，和我之前在学校算法俱乐部时所写的原理不太一样。于是分享出来

#include "pch.h"
    //大整数乘法
    
    #include<iostream>
    #include <sstream>
    #include<ctime>
    #include<cmath>
    using namespace std;
    
    //在字符串后面添加n个0，起到移位作用
    void mov(string &x, int n)
    { 
    	x.append(n, '0');
    }
    //两多项式结果求和
    string sum(string a, string b)
    { 
    	stringstream ss;
    	string ans;//结果的逆序
    	int la = a.length();
    	int lb = b.length();
    
    	int c = 0;
    	int min = la < lb ? la : lb;
    	for (int i = 0; i < min; i++)
    	{ 
    		int num = a[a.length() - 1 - i] + b[b.length() - 1 - i] - 2 * '0';
    		int num_temp = (c + num) % 10;
    		ss << num_temp;
    		ans.append(ss.str());
    		ss.str("");
    		c = (c + num) / 10;
    	}
    	if (la > lb)
    	{ 
    		int k = min;
    		while (k < la)
    		{ 
    			int num_temp = (a[la - 1 - k] - '0' + c) % 10;
    			ss << num_temp;
    			ans.append(ss.str());
    			ss.str("");
    			c = (a[k] - '0' + c) / 10;
    			k++;
    		}
    	}
    	else if (la < lb)
    	{ 
    		int k = min;
    		while (k < lb)
    		{ 
    			int num_temp = (b[lb - 1 - k] - '0' + c) % 10;
    			ss << num_temp;
    			ans.append(ss.str());
    			ss.str("");
    			c = (b[k] - '0' + c) / 10;
    			k++;
    		}
    	}
    	else { }
    	if (c != 0)
    	{ 
    		ss << c;
    		ans.append(ss.str());
    	}
    
    	//除去多的0
    	if (count(ans.begin(), ans.end(), '0') == ans.length())
    	{ 
    		ans = "0";
    	}
    	//翻转字符串来获得正确顺序
    	for (int i = 0; i < ans.length() / 2; i++)
    	{ 
    		char temp = ans[i];
    		ans[i] = ans[ans.length() - 1 - i];
    		ans[ans.length() - 1 - i] = temp;
    	}
    	return ans;
    }
    string mul(string a, int y1, string b, int y2)
    { 
    	//如果两项都只有一位
    	if (a.length() == 1 && b.length() == 1)
    	{ 
    		stringstream ss;
    		ss << (a[0] - '0')*(b[0] - '0');
    		return ss.str();
    	}
    	int k1 = 0, k2 = 0;
    	string a1, a2, b1, b2;
    	//如果有一个为一位 
    	if (a.length() == 1 || b.length() == 1)
    	{ 
    		if (a.length() == 1)
    		{ 
    			k1 = 0;
    			a1 = a;
    			a2 = "0";
    			k2 = b.length() / 2 + b.length() % 2;
    			b1 = b.substr(0, b.length() / 2);
    			b2 = b.substr(b.length() / 2);
    		}
    		if (b.length() == 1)
    		{ 
    			k2 = 0;
    
    			b1 = b;
    			b2 = "0";
    			k1 = a.length() / 2 + a.length() % 2;
    			a1 = a.substr(0, a.length() / 2);
    			a2 = a.substr(a.length() / 2);
    		}
    	}
    	else
    	{ 
    		k1 = a.length() / 2 + a.length() % 2;
    		a1 = a.substr(0, a.length() / 2);
    		a2 = a.substr(a.length() / 2);
    		k2 = b.length() / 2 + b.length() % 2;
    		b1 = b.substr(0, b.length() / 2);
    		b2 = b.substr(b.length() / 2
    		);
    	}
    	//多项式
    	string x1 = mul(a1, k1, b1, k2);
    	string x2 = mul(a1, k1, b2, 0);
    	string x3 = mul(a2, 0, b1, k2);
    	string x4 = mul(a2, 0, b2, 0);
    
    	//对多项式移位
    	mov(x1, k1 + k2);
    	mov(x2, k1);
    	mov(x3, k2);
    	return sum(sum(x1, x2), sum(x3, x4));
    }
    
    
    int main()
    { 
    	string a, b;
    	cin >> a >> b;
    	string ans;
    	ans = mul(a, 0, b, 0);
    	cout << ans << endl;
    	return 0;
    }

所有的因子都用string类型表示，位数限制在于string类型的位数最大值也就是大概2G，也就是说能够轻松做上万位的乘法。不过想当然的，速度不会和你做int范围内乘法相提并论。  
这个程序经过我的一些测试，如果读者发现一些不正确的用例，请勘误。  
仅做参考，请不要cv交作业，学习编程不是仅仅从看懂程序开始的。