#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iterator>
#include <ctime>
using namespace std;
#define STL_WAY
//#define PRINT2FILE
struct BigInt
{
vector<int> digits;
BigInt(string str="0");
BigInt operator+(const BigInt & bi) const;
BigInt operator-(const BigInt & bi) const;
BigInt operator*(const BigInt & bi) const;
BigInt operator*(int n) const;
BigInt operator<<(int n) const;
};
typedef const BigInt & BICR;
typedef BigInt & BIR;
struct Ascii2Int { int operator()(int c) {return c-'0';} };
struct CarryPos
{
int & carry;
CarryPos(int & c):carry(c){}
int operator()(int n)
{
n+=carry; carry=n/10; n%=10;
return n;
}
};
struct CarryNeg
{
int & carry;
CarryNeg(int & c):carry(c){}
int operator()(int n)
{
n-=carry; carry=0;
while (n<0) {n+=10; carry++;}
return n;
}
};
struct NegMinus { int operator()(int a, int b) {return b-a;} };
BigInt::BigInt(string str)
{
transform(str.rbegin(),str.rend(),back_inserter(digits),Ascii2Int());
}
BigInt BigInt::operator+(BICR bi) const
{
const BigInt * max_op=this;
const BigInt * min_op=&bi;
if (max_op->digits.size()<min_op->digits.size())
swap(max_op,min_op);
BigInt result(*max_op);
#ifdef STL_WAY
transform(min_op->digits.begin(),min_op->digits.end(),
result.digits.begin(),result.digits.begin(),plus<int>());
int carry=0;
transform(result.digits.begin(),result.digits.end(),
result.digits.begin(),CarryPos(carry));
#else
int carry=0;
int max_size=max_op->digits.size();
int min_size=min_op->digits.size();
for (int i=0; i<min_size; i++)
{
result.digits[i]+=carry+min_op->digits[i];
carry=result.digits[i]/10;
result.digits[i]%=10;
}
for (int i=min_size; i<max_size; i++)
{
result.digits[i]+=carry;
carry=result.digits[i]/10;
result.digits[i]%=10;
}
#endif
if (carry) result.digits.push_back(carry);
return result;
}
BigInt BigInt::operator-(BICR bi) const
{
BigInt result(*this);
#ifdef STL_WAY
transform(bi.digits.begin(),bi.digits.end(),
result.digits.begin(),result.digits.begin(),NegMinus());
int carry=0;
transform(result.digits.begin(),result.digits.end(),
result.digits.begin(),CarryNeg(carry));
#else
int carry=0;
int max_size=digits.size();
int min_size=bi.digits.size();
for (int i=0; i<min_size; i++)
{
result.digits[i]-=carry;
result.digits[i]-=bi.digits[i];
carry=0;
while(result.digits[i]<0)
{
result.digits[i]+=10;
carry++;
}
}
int i=min_size;
while (carry!=0)
{
result.digits[i]-=carry;
carry=0;
while(result.digits[i]<0)
{
result.digits[i]+=10;
carry++;
}
i++;
}
#endif
return result;
}
BigInt BigInt::operator*(int n) const
{
BigInt result(*this);
#ifdef STL_WAY
transform(result.digits.begin(),result.digits.end(),
result.digits.begin(),bind1st(multiplies<int>(),n));
int carry=0;
transform(result.digits.begin(),result.digits.end(),
result.digits.begin(),CarryPos(carry));
#else
int carry=0;
int size=result.digits.size();
for (int i=0; i<size; i++)
{
result.digits[i]*=n;
result.digits[i]+=carry;
carry=result.digits[i]/10;
result.digits[i]%=10;
}
#endif
while (carry)
{
result.digits.push_back(carry%10);
carry/=10;
}
return result;
}
BigInt BigInt::operator<<(int n) const
{
BigInt result(*this);
result.digits.resize(result.digits.size()+n);
copy(result.digits.rbegin()+n, result.digits.rend(),result.digits.rbegin());
fill(result.digits.begin(),result.digits.begin()+n,0);
return result;
}
BigInt BigInt::operator*(BICR bi) const
{
const BigInt * max_op=this;
const BigInt * min_op=&bi;
int max_size=max_op->digits.size();
int min_size=min_op->digits.size();
if (max_size<min_size)
{
swap(max_op,min_op);
swap(max_size,min_size);
}
BigInt * array=new BigInt[min_size];
for (int i=0; i<min_size; i++)
array[i]=(*max_op)*(min_op->digits[i]);
BigInt result(array[0]);
for (int i=1; i<min_size; i++)
result=result+(array[i]<<i);
delete[] array;
return result;
}
void split(BICR op1, BICR op2, BIR x0, BIR x1, BIR y0, BIR y1, int & m)
{
int size1=op1.digits.size();
int size2=op2.digits.size();
int min_size=size1;
if (min_size>size2) min_size=size2;
m=min_size/2;
x0.digits.resize(m);
x1.digits.resize(size1-m);
y0.digits.resize(m);
y1.digits.resize(size2-m);
copy(op1.digits.begin(),op1.digits.begin()+m,x0.digits.begin());
copy(op1.digits.begin()+m,op1.digits.end(),x1.digits.begin());
copy(op2.digits.begin(),op2.digits.begin()+m,y0.digits.begin());
copy(op2.digits.begin()+m,op2.digits.end(),y1.digits.begin());
}
BigInt karatsuba(BICR op1, BICR op2)
{
BigInt x0, x1, y0, y1;
BigInt z0, z1, z2;
if (op1.digits.size()<30 || op2.digits.size()<30)
return op1*op2;
int m;
split(op1,op2,x0,x1,y0,y1,m);
z0=karatsuba(x0,y0);
z2=karatsuba(x1,y1);
z1=(karatsuba(x0+x1,y0+y1)-z2)-z0;
z1=z1<<m;
z2=z2<<2*m;
return z0+z1+z2;
}
ostream & operator<<(ostream & os, BICR bi)
{
copy(bi.digits.rbegin(),bi.digits.rend(),ostream_iterator<int>(os));
#ifdef PRINT2FILE
#ifdef STL_WAY
ofstream fout("stl.txt",ios::app);
copy(bi.digits.rbegin(),bi.digits.rend(),ostream_iterator<int>(fout));
fout << endl;
#else
ofstream fout("loops.txt",ios::app);
copy(bi.digits.rbegin(),bi.digits.rend(),ostream_iterator<int>(fout));
fout << endl;
#endif
#endif
return os;
}
void test(string s1, string s2)
{
BigInt n1(s1);
BigInt n2(s2);
BigInt rs, rk;
int start_s, stop_s, start_k, stop_k;
start_s=clock();
rs=n1*n2;
stop_s=clock();
start_k=clock();
rk=karatsuba(n1,n2);
stop_k=clock();
cout << rs << endl;
cout << rk << endl;
cout << "standard time: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000 << endl;
cout << "karatsuba time: " << (stop_k-start_k)/double(CLOCKS_PER_SEC)*1000 << endl;
}
int main()
{
test(
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789",
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321");
cout << "\nhit enter to continue..." << endl;
cin.get();
test(
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789",
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321");
cout << "\nhit enter to continue..." << endl;
cin.get();
test(
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789",
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321");
cout << "\nhit enter to continue..." << endl;
cin.get();
test(
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789",
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321");
cout << "\nhit enter to continue..." << endl;
cin.get();
test(
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789"
"123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789",
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321"
"987654321987654321987654321987654321987654321987654321987654321987654321987654321987654321");
cout << "\nhit enter to continue..." << endl;
cin.get();
return 0;
}