题目描述

程序设计语言中的整型数据类型可以存放一定范围内的整数,超出这个范围的大整数就不能再用普通变量存储和操作,这样的整数通常被称为“大整数”。大整数的存储需要借助于数组或链表等,其操作也需要编写程序完成。

要求:

  1. 大整数的位数n≥16,可以是十进制或者二进制数。

  2. 两个大整数相乘如果按照传统的方法,需要耗费n2次数量相乘,试设计大整数乘法的分治算法,要求时间复杂度低于n2阶。

算法分析

  1. 我们采用分治算法,具体算法如下

    我们将n位的二进制整数X和Y各分为2段,每段的长为n/2位(为简单起见,假设n是2的幂),有下图形式

  2. 计算公式为

    XY = (A2^(n/2)+B)(C2^(n/2)+D)=AC2^n+(AD+CB)2^(n/2)+BD

    对于2的n次方,我们采用左移n位即可,需要的时间为n。另外需要四次乘法以及三次加法,这蕴含下图递推式:

  3. ​ 由数学方法我们可知该算法时间复杂度为n^2

    ​ 所以采用Toom—Cook算法对上面的算法进行优化:

    ​ wz + xy = (w + x )(y + z) -wy – xz

    ​ 再结合上面的算式,我们仅计算三次乘法以及次加减 运算,此中方法的递推式如下

  4. 经计算,使用Toom—Cook算法的时间复杂度为O(n^1.59)。

    分治过程如下:

    • 分: 将两个大整数分别分成四个较小整数

    • 治:利用Toom—Cook算法进行计算

    • 组合: 将每次算出的结果以字符串拼接相加

    • 阈值: 这里设置阈值为4,不再分,并将运算结果返回

    • 直接运算 : 当数字的位数为4时,直接计算两数乘法。

参考代码

/************************************************************************/
//函数功能:分治法求两个N为的整数的乘积
//输入参数:X,Y分别为两个N为整数
//h核心优化方程 :uv = wy2n+[(w-x)(z-y)+wy+xz]2n/2+xz
//时间复杂度为:T(n)=O(nlog3)=O(n1.59)
/************************************************************************/
#include <bits/stdc++.h>
using namespace std;
//C++数字转字符串
string number_to_string(int m){
stringstream ss ;
ss << m ;
string re ;
ss >> re ;
return re;
}
//C++字符串转数字
int string_to_number(string m){
stringstream ss(m);
int s ;
ss >> s ;
return s ;
}
//在数字前面加0
string same_number_zero_before(string m , int s){
for(int i = 0 ; i < s ; ++i){m.insert(0,"0");}
return m ;
}
//在数字后面加零
string same_number_zero_follow(string m , int s){
for(int i = 0 ; i < s ; ++i) {m.insert(m.size(),"0");}
return m ;
}
//两个数字相加
string string_add(string a , string b){
if(a.size() > b.size()) {b = same_number_zero_before(b,a.size() - b.size()) ;}
else if(b.size() > a.size()) {a = same_number_zero_before(a,b.size() - a.size()) ;}
string result;
int co = 0 ;
for(int i = a.size() - 1 ; i >= 0 ; --i){
int c = (a[i] - '0') + (b[i] - '0') + co;
co = c / 10 ;
c %= 10 ;
result.insert(0,number_to_string(c));
}
if(co != 0){result.insert(0,number_to_string(co));}
return result ;
}
string string_sub(string a , string b){
while(a[0] == '0' && a.size() > 1) {a = a.substr(1,a.size()-1);}
while(b[0] == '0' && b.size() > 1) {b = b.substr(1,b.size()-1);}
if(a.size() > b.size()){ b = same_number_zero_before(b,a.size() - b.size());}
string result ;
for(int i = a.size() - 1 ; i >= 0 ; --i){
int c = (a[i] - '0') - (b[i] - '0');
if(c < 0){
c += 10 ;
int prepos = i -1 ;
char prechar = a[prepos];
while(prechar == '0')
{
a[prepos] = '9';
prepos = -1 ;
prechar = a[prepos];
}
a[prepos] -= 1 ;
}
result.insert(0,number_to_string(c));
}
return result;
}
//计算string数字的乘法函数
string multi(string u , string v){
//首先将两个数前面的0去除,保留有效的计算位数
while(u[0] == '0' && u.size() > 1){u = u.substr(1,u.size()-1);}
while(v[0] == '0' && v.size() > 1){v = v.substr(1,v.size()-1);}
int n = 4 ;
if(u.size() > 2 || v.size() > 2)
{
if(u.size() >= v.size())
{
//f为2的n次方位数大小,直到f的位数与x或者y中的 最大的 一个数 位数 相同或者大 停止
while(u.size() > n){ n *= 2 ;}
if(u.size() != n)
{
//为了计算两个数,使u,v,f三个数位数相同
u = same_number_zero_before(u,n-u.size());
v = same_number_zero_before(v,n-v.size());
}
}
else
{
//f为2的n次方大小,直到f的位数比x或者y中的最大的一个数位数大停止
while(v.size() > n){ n *= 2 ;}
if(v.size() != n)
{
//为了计算两个数,使u,v,f三个数位数相同
u = same_number_zero_before(u,n-u.size());
v = same_number_zero_before(v,n-v.size());
}
}
}
//时刻保证u以及v有两位
if(u.size() == 1 ){u = same_number_zero_before(u,1);}
if(v.size() == 1 ){v = same_number_zero_before(v,1);}
//时刻保证u、v位数相同
if(u.size() > v.size()){v = same_number_zero_before(v,u.size() - v.size());}
if(u.size() < v.size()){u = same_number_zero_before(u,v.size() - u.size());}
//确定两数的位数
int num = u.size();
//分割u,v
string w , x , y , z ;
if(num > 1){
w = u.substr(0, num / 2 );
x = u.substr(num/2 , num - 1);
y = v.substr(0, num / 2);
z = v.substr(num / 2 , num - 1);

}
string result ;
//循环阈值为2,结束递归,回迭
if(num == 2 ){
int nw = string_to_number(w);
int nx = string_to_number(x);
int ny = string_to_number(y);
int nz = string_to_number(z);
result = number_to_string((nw*10 + nx)*(ny*10 +nz));
}
else
{
string c1 = multi(w,y);
string c2 = multi(x,z);
string c11 = string_add(w,x);
string c22 = string_add(y,z);
string c33 = multi(c11,c22);
string c44 = string_add(c1,c2);
string c55 = string_sub(c33,c44);
string ss1 = same_number_zero_follow(c55,num/ 2);
string ss2 = same_number_zero_follow(c1 , num );
result = string_add(string_add(ss2,ss1),c2);
}
return result;
}
int main(int argc, char const *argv[])
{
bool flag = true ;
//循环计算多组大数乘法
while(flag)
{
string u , v ;
int sign = 0 ,sign1 = 0, sign2 = 0 ;
//程序使用提示
cout<<"大整数 - 分治法 - C++版 - O(n^1.53)" << endl ;
//输入第一个数
cout<<"请输入第一个数"<<endl;
bool inputfunction = true;
while(inputfunction)
{
cin>>u;
int f = 0 ;
for(int i = 1 ; i < u.size() ; ++i)
{
if(u[i] < '0' || u[i] > '9'){cout<<"输入数据非法,请重新输入"<<endl;f = 1 ;break;}
}
if(f == 0){break;}
}
//输入第二个数
cout << "请输入第二个数"<< endl;
while(inputfunction)
{
cin >> v;
int f = 0 ;
for(int i = 1 ; i < v.size() ; ++i)
{
if(v[i] < '0' || v[i] > '9'){cout<<"输入数据非法,请重新输入"<<endl; f = 1 ;break;}
}
if(f == 0){break;}
}
//取出各个数字的符号位
if(u[0] != '-'){sign1 = 1 ;} else{sign1 = -1;u = u.substr(1,u.size()-1);}
if(v[0] != '-'){sign2 = 1 ;} else{sign2 = -1;v = v.substr(1,v.size()-1);}
//求出两数相乘符号位
sign = sign1 * sign2 ;
//计算两个数的abs乘积值,并以string输出
string result = multi(u,v);
while('0' == result[0] && result.size() > 1)
{
result = result.substr(1,result.size() - 1);
}
cout << "结果:"<<endl;
if(sign == -1) {cout<<'-';}
cout << result << endl;
cout<<"继续请输入1,否则输入任意字符"<<endl;
string s ;
cin >> s ;
if(s.size() == 1 && s[0] == '1') {continue;}
else {break;}
}
}

谢谢访问