Consider a representation for integers of arbitrary length t

Consider a representation for integers of arbitrary length that uses a vector of integers to store each digit as a separate element. Each element in the vector is between 0 and 9 (inclusive) and together they represent a larger integer, with the least significant digit first. So, the vector: [8 3 9 0 1] would represent the number 10, 938. There are no leading zeros in the numbers. Write a function that takes two such vectors and returns a new vector (in the same format) storing the product of the two inputs. You may assume as a precondition that the input vectors do not contain elements that are not single, positive digits. You should also enforce this as a postcondition on your output. Your solution must allow integers of arbitrary length without overflow. (For example, do not convert any vector to a single integer, since this doesn\'t allow arbitrary length.

Solution

PROGRAM CODE:

/*
* vectorMultiplicationArbitrary.cpp
*
* Created on: 12-Feb-2017
* Author: kasturi
*/

#include <iostream>
#include <vector>
using namespace std;

//Printing the vectors
void printVector(vector<int> v)
{
   for(std::vector<int>::iterator it1 = v.begin(); it1 != v.end(); ++it1) {
       cout<<*it1;
   }
   cout<<\"\ \";
}

//Function that multiplies two vectors digit by digit and returns the product vector
vector<int> multiplyVector(vector<int> v1, vector<int> v2)
{
   vector<int> product;
   int carryOver = 0;
   int prod = 0;
   int len1 = v1.size();
   int len2 = v2.size();
   //calculating the size of the temporary array of vectors
   int totalSize = len1>len2?len1:len2;
   //size of each vector
   int maxSize = 0;
   vector<int> *temp = new vector<int>[totalSize];
   //k and counter are for calculating the number of times zeroes must be inserted
   //this is for maintaining equal size for all the vectors
   int counter = 0;
   int k = 0;
   //from reverse multiplying each digit and storing the value in temp arrays
   for(int i=len1-1; i>=0; i--)
   {
       while(counter>0)
       {
           temp[i].push_back(0);
           counter--;
       }
       for(int j=len2-1; j>=0; j--)
       {
           prod = v1[i] * v2[j] + carryOver;
           temp[i].push_back(prod%10);
           carryOver = prod/10;
       }
       while(carryOver>0)
       {
           temp[i].push_back(carryOver%10);
           carryOver = carryOver/10;
       }
       k++;
       counter = k;

   }
   carryOver = 0;
   //finding out the maxsize
   for(int m=0; m<totalSize; m++)
   {
       if(temp[m].size() > maxSize)
           maxSize = temp[m].size();
   }

   //making the size equal
   for(int m=0; m<totalSize; m++)
   {
       int k = temp[m].size();
       while(k<maxSize)
       {
           temp[m].push_back(0);
           k++;
       }
   }
   //adding all the temp arrays to get the product
   for(int i=0; i<maxSize; i++)
   {
       int value = 0;
       for(int j=0; j<totalSize; j++)
       {
           value += temp[j][i];
       }
       value += carryOver;
       product.push_back(value%10);
       carryOver = value/10;
   }
   while(carryOver>0)
   {
       product.push_back(carryOver%10);
       carryOver = carryOver/10;
   }
   delete [] temp;
   return product;
}

int main() {
   vector<int> v1, v2, v3;
   v1.push_back(2);
   v1.push_back(4);
   v1.push_back(3);
   v2.push_back(2);
   v2.push_back(3);
   int start_s=clock();
   v3 = multiplyVector(v1, v2);
   int stop_s=clock();
   std::reverse(v3.begin(),v3.end());
   cout<<\"Number 1: \";
   printVector(v1);
   cout<<\"Number 2: \";
   printVector(v2);
   cout<<\"Product: \";
   printVector(v3);
   cout << \"Run time: \" << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000 << \" sec\"<<endl;
   return 0;
}

OUTPUT:

Number 1: 243

Number 2: 23

Product: 5589

Run time: 0.014 sec