Hi guys, I'm trying to implement Karatsuba multiplication in c++ using stl vectors. I have some problems with multiplication (addition and subtraction are ok, I've checked). I need to read data from the file, when the file looks like that:
3 // tells me how many pairs I have to multiply
3 // tells me how many digits is in every number
0 0 2
0 45 45 // first pair
1 1 1
2 2 2 // second pair
200 0 0
0 0 3 // last pair to multiply using Karatsuba ...
(text after "//" doesn't appear in my file, I wrote it only to explain what do the numbers exactly means)
Please, help me ! I'm going crazy, I don't know where I'm going wrong .. I've been trying to do this for 3 weeks and I just don't know what is wrong ... :(
Here's my code (and btw, sorry for my english :) )
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
/*Adding zero at the beggining of the number*/
vector<int> addZero(vector<int> v){
vector<int>::iterator i;
i=v.begin();
v.insert(i,0);
return v;
}
/*Removing zero from the begging of the number*/
vector<int> removeZero(vector<int> v){
vector<int>::iterator i;
i=v.begin();
v.erase(i);
return v;
}
/*Multiplying number and a digit*/
vector<int> multiplyNumberDigit(vector<int> v,int d){
vector<int> r;
int c = 0;
for(int i=0;i<v.size();i++)
{
r.push_back((v[i]*d+c%256));
c = (v[i]*d+c)/256;
}//for
while(c>0)
{
r.push_back(c%256);
c/=256;
}//while
return r;
}
/*Number1 - Number2*/
vector<int> operator-(vector<int> v1,vector<int> v2){
vector<int> r;
int p = 0;
int b = 0;
for(int i=0;i<v1.size();i++)
{
if(i<v2.size())
p=(v1[i]-v2[i]+b);
else
p=(v1[i]+b);
if(p<0){
p+=256;
b=-1;
}else{
b=0;
}//else
r.push_back(p);
}//for
return r;
}
/*Number1+Number2*/
vector<int> operator+(vector<int> v1, vector<int> v2){
vector<int> r;
int c = 0;
int dl = min(v1.size(),v2.size());
for(int i=0; i<dl; i++)
{
r.push_back((v1[i]+v2[i]+c)%256);
c = (v1[i]+c)/256;
}
/*Number v1 is longer than number v2*/
while(dl<v1.size())
{
r.push_back((v1[dl]+c)/256);
c = (v1[dl]+c)/256;
dl++;
}
/*Number v2 is longer than number v1*/
while(dl<v2.size())
{
r.push_back((v2[dl]+c)%256);
c = (v2[dl]+c)/256;
dl++;
}
if(c > 0)
r.push_back(c);
return r;
}
/*Multiplying 2 numbers, when their length = 2*/
vector<int> operator*(vector<int> x,vector<int> y){
vector<int> a,b;
a = multiplyNumberDigit(x,y[1]);
b = multiplyNumberDigit(x,y[0]);
vector<int>::iterator i;
i = b.begin();
b.insert(i,0);
return a+b;
}
vector<int> karatsuba(vector<int> v1,vector<int> v2,int m){
vector<int> r;
if(m%2!=0)
{
v1 = addZero(v1);
v2 = addZero(v2);
}
int size = v1.size();
if(size<=2)
{
r = v1*v2;
return r;
}else{
vector<int> x1,x2,y1,y2,X,Y,Z;
int lX = v1.size();
int lY = v2.size();
for(int i=0;i<lX/2;i++)
x1.push_back(v1[i]);
for(int i=lX/2;i<lX;i++)
x2.push_back(v1[i]);
for(int j=0;j<lY/2;j++)
y1.push_back(v2[j]);
for(int j=lY/2;j<lY;j++)
y2.push_back(v2[j]);
X = x1+x2;
Y = y1+y2;
vector<int> u,v,w,uPLUSv,wMINUSuv,res2;
u = karatsuba(x1,y1,m);
v = karatsuba(x2,y2,m);
w = karatsuba(X,Y,m);
uPLUSv = u+v;
wMINUSuv = w-uPLUSv;
res2 = u+wMINUSuv;
Z = res2+v;
return removeZero(Z);
}
}
void solve(vector<int>* r,vector<int>* all,int n,int m){
int j=0;
for(int i=0;i<2*n;i+=2)
{
r[j]=karatsuba(all[i],all[i+1],m);
j++;
}
}
int main(){
vector<int>* all;
vector<int>* r;
int n,m,temp,h=0;
ifstream in("file.txt");
in>>n;
in>>m;
all = new vector<int>[2*n];
r = new vector<int>[n];
for(int i=0;i<2*n;i++)
{
for(int j=0;j<n;j++)
{
in>>temp;
all[h].push_back(temp);
if(j==n-1)
h++;
}
}
solve(r,all,n,m);
for(int i=0;i<n;i++)
{
for(int j=0;j<all[i].size();j++)
cout<<all[i][j];
cout<<("\n");
}
system("PAUSE");
return 0;
}