[ Karatsuba Multiply ] 大數模板乘法Karatsuba法

複雜度大約是$\ord{N^{log3}}$，約為$\ord{N^{1.5}}$比一般直式乘法還快，附上連結:
Karatsuba算法

附模板，配合大數模板使用:

	//operator*的函數用以下這些函數取代
	bigN convert_base(int old_width,int new_width)const{
	vector<long long> p(max(old_width,new_width)+1,1);
	for(size_t i=1;i<p.size();++i)p[i]=p[i-1]*10;
	bigN ans;
	long long cur=0;
	int cur_id=0;
	for(size_t i=0;i<size();++i){
	cur+=at(i)*p[cur_id];
	cur_id+=old_width;
	while(cur_id>=new_width){
	ans.push_back(cur%p[new_width]);
	cur/=p[new_width];
	cur_id-=new_width;
	}
	}
	return ans.push_back(cur),ans.trim(),ans;
	}
	bigN karatsuba(const bigN &b)const{
	bigN res;res.resize(size()*2);
	if(size()<=32){
	for(size_t i=0;i<size();++i)
	for(size_t j=0;j<size();++j)
	res[i+j]+=at(i)*b[j];
	return res;
	}
	size_t k=size()/2;
	bigN a1(begin(),begin()+k);
	bigN a2(begin()+k,end());
	bigN b1(b.begin(),b.begin()+k);
	bigN b2(b.begin()+k,b.end());
	bigN a1b1=a1.karatsuba(b1);
	bigN a2b2=a2.karatsuba(b2);
	for(size_t i=0;i<k;++i)a2[i]+=a1[i];
	for(size_t i=0;i<k;++i)b2[i]+=b1[i];
	bigN r=a2.karatsuba(b2);
	for(size_t i=0;i<a1b1.size();++i)r[i]-=a1b1[i];
	for(size_t i=0;i<a2b2.size();++i)r[i]-=a2b2[i];
	for(size_t i=0;i<r.size();++i)res[i+k]+=r[i];
	for(size_t i=0;i<a1b1.size();++i)res[i]+=a1b1[i];
	for(size_t i=0;i<a2b2.size();++i)res[i+size()]+=a2b2[i];
	return res;
	}
	bigN operator*(const bigN &b)const{
	const static int mul_base=1000000,mul_width=log10(mul_base);
	bigN A=convert_base(width,mul_width);
	bigN B=b.convert_base(width,mul_width);
	int n=max(A.size(),B.size());
	while(n&(n-1))++n;
	A.resize(n),B.resize(n);
	bigN res=A.karatsuba(B);
	res.negative=negative!=b.negative;
	res.carry(mul_base);
	res=res.convert_base(mul_width,width);
	return res.trim(),res;
	}
	bigN operator*(long long b)const{//除法會用到O(N)
	bigN res=*this;
	if(b<0)res.negative=!negative,b=-b;
	for(size_t i=0,is=0;i<res.size()||is;++i){
	if(i==res.size())res.push_back(0);
	long long a=res[i]*b+is;
	is=a/base;
	res[i]=a%base;
	}
	return res.trim(),res;
	}

view raw karatsuba.cpp hosted with ❤ by GitHub