我想用一个BigInteger类来实现高精度,其中重载了*进行高精度乘法但不知道为什么,运行代码的时候出现了Process finished with exit code 139 (interrupted by signal 11: SIGSEGV)的错误,哪位大佬可以帮我看一下,谢谢。
#include <iostream>
#include <cstring>
#include <vector>
#include <complex>
using namespace std;
const double PI = acos(-1.0);
static const int M = 3e6+5;
struct BigInteger{
string s;
BigInteger(string _s="", bool pos = 1): s(_s){}
bool operator == (const BigInteger& bgi ){
if( s.size() != bgi.s.size() ) return 0;
else{
for(int i = 0; i < s.size( ); i++){
if( s[i] != bgi.s[i] ) return 0;
}
}
return 1;
}
bool operator <( const BigInteger& bgi ){
if( s.size( ) < bgi.s.size() ) return 1;
else if( s.size() > bgi.s.size() ) return 0;
else{
int n = s.size();
for(int i = 0; i < n; i--){
if( s[i] > bgi.s[i] ) return 0;
else if( s[i] < bgi.s[i] ) return 1;
}
}
return 0;
}
bool operator <= ( const BigInteger& bgi ){
if( (*this) < bgi || (*this) == bgi ) return 1;
else return 0;
}
bool operator > (const BigInteger& bgi ){
if( s.size( ) < bgi.s.size() ) return 0;
else if( s.size() > bgi.s.size() ) return 1;
else{
int n = s.size();
for(int i = 0; i < n; i--){
if( s[i] < bgi.s[i] ) return 0;
else if( s[i] > bgi.s[i] ) return 1;
}
}
return 0;
}
bool operator >= (const BigInteger& bgi ){
if( (*this) > bgi || (*this) == bgi ) return 1;
else return 0;
}
};
vector<int> toIntArray( BigInteger b ){
int n = b.s.size();
vector<int> res;
res.resize(n+5);
for(int i = 0; i < n; i++){
res[n-i-1] = b.s[i]-'0';
}
return res;
}
BigInteger toBigInteger( const vector<int>& v ){
int n = v.size();
int st = n-1;
while( st >= 0 && !v[st] ) --st;
if( st == -1 ) return BigInteger("0");
string s;
for(int i = st; i >= 0; i--){
s += ('0'+v[i]);
}
return BigInteger(s);
}
BigInteger operator + (BigInteger b1, BigInteger b2){
if( b1 < b2 ) swap(b1,b2);
int n = b1.s.size(), m = b2.s.size();
vector<int> a,b;
a = toIntArray(b1);
b = toIntArray(b2);
for(int i = 0; i < m; i++){
a[i] += b[i];
if( a[i] >= 10 ) a[i+1] += a[i]/10;
a[i] %= 10;
}
return toBigInteger(a);
}
void init( vector<int> rev , int k){
int len = (1<<k);
rev.resize(len);
for(int i = 0; i < len; i++){
rev[i] = ((rev[i>>1]>>1)|(i&1)<<(k-1));
}
}
//flag=1:快速傅里叶变换,flag=-1:逆快速傅里叶变换
//a表示变换后的结果,n表示多项式的长度,rev表示多项式分解后各项的顺序
void FFT(vector<complex<double> > &a, int n, int flag, vector<int> rev){
a.resize(n);
for(int i = 0; i < n; i++ ){
if( i < rev[i] ){
swap(a[i],a[rev[i]]);
}
}
for(int h = 1; h < n; h >>= 1){
complex<double> wn = exp(complex<double>(0,flag*PI/h));
for(int j = 0; j < n; j += h*2){
complex<double> w(1,0);
for(int k = j; k < j+h; k++){
complex<double> x = a[k];
complex<double> y = w*a[k+h];
a[k] = x+y;
a[k+h] = x-y;
w *= wn;
}
}
}
if( flag == -1 ){
for(int i = 0; i < n; i++){
a[i] /= n;
}
}
}
BigInteger operator *( const BigInteger& A, const BigInteger& B){
string s1 = A.s, s2 = B.s;
int n = s1.size(), m = s2.size();
vector<complex<double> > a, b;
a.resize(n);
b.resize(m);
for(int i = 0; i < n; i++){
a[n-i-1] = s1[i]-'0';
}
for(int i = 0; i < m; i++){
b[m-i-1] = s2[i]-'0';
}
int k = 1, s = 2;
while( (1<<k) < n+m-1 ){
++k;
s <<= 1;
}
vector<int> rev;
init(rev,k);
FFT(a,s,1,rev);
FFT(b,s,1,rev);
for(int i = 0; i < s; i++){
a[i] *= b[i];
}
FFT(a,s,-1,rev);
vector<int> ans;
ans.resize(s);
for(int i = 0; i < s; i++){
ans[i] = (int)(a[i].real()+0.5);
ans[i+1] += ans[i]/10;
ans[i] %= 10;
}
return toBigInteger(ans);
}
int main() {
string s1, s2;
cin >> s1 >> s2;
BigInteger a(s1), b(s2), c;
c = a*b;
cout << c.s <<endl;
return 0;
}