0

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;
}

Edited by mazix2: n/a

1
Contributor
1
Reply
3
Views
6 Years
Discussion Span
Last Post by mazix2
0

And, as you can see it in my code, the base is 256, not as usually 10.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.