bigInt operator* help

[KK]

Hi, im working on this bigInt class. Need help writing algorithm for
the operator*, andy help will be appreciated. Thanks in advance

bigInt.h
===================================================================================
//class bigInt implements big integers by storing the digits of a big
//integer in a private vector data member called digit. Since it uses
a
//vector the size of the big integer can be indefinitely large. This
class
//implements input/output of bigInts,
addition/multiplication/pre-increment
//of bigInts, assignment of a bigInt or long int to a bigInt and ==/<
//comparison of bigInts. The operators
addition/multiplication/pre-increment/<
//only work for big integers >= 0. By adding additional code they
could be
//made to work for negative big integers also.
#ifndef _bigInt_h
#define _bigInt_h

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class bigInt
{
public:
bigInt(); //default constructor, defined
bigInt(long int k); //construct bigInt with value like k,
defined
bigInt(const string& s); //construct bigInt with value like string
s ,defined

void print(ostream& os) const; //function to output a bigInt,
defined
void read(istream& is); //function to input a bigInt,
defined

bigInt operator+(const bigInt& bi2) const; //overloads + operator
bigInt operator*(const bigInt& bi2) const; //overloads * operator
bigInt& operator++(); //overloads
pre-increment op, defined

const bigInt& operator=(const bigInt& bi2); //copy assignment
operator, defined
const bigInt& operator=(long int i); //converts i to bigInt and
assigns

//overload comparison operators
bool operator==(const bigInt& bi2) const; //defined
bool operator<(const bigInt& bi2) const;//defined

private:
char sign; //stores the sign '+' or '-'. Not really
//needed in this program because you only have
//to handle positive numbers (numbers >= 0),
but
//would be needed in a complete program.
vector<int> digit; //vector to store digits of a bigInt with
//one digit in each element of the vector.
//A more efficient version of the program
//would store several digits in each element.
//digit[0] is the 1's digit, digit[1] is the
10's
//digit, digit[2] is the 100's digit, etc.

void convertString(const string& s); //converts string into bigInt
//representaion., defined
};

//overloads << and >> operators as non-member functions using
//public member functions print and read.
ostream& operator<<(ostream& os, const bigInt& bi); //defined
istream& operator>>(istream& is, bigInt& bi);//defined

#endif
=================================================================================

bigInt2.cpp
=================================================================================
#include <iostream>
#include <string>
#include <cctype>
#include <cstdlib>

#include "bigInt.h"

using namespace std;

bigInt::bigInt()
{
}

bigInt::bigInt(long int i)
/*this function should determine whether i is positive or
negative and set the sign accordingly. It then extracts
the digits from i and stores them in the vector digit.
This can be done by nextdigit = i % 10; i = i / 10; For
example if i is 456 then nextdigit = 456 % 10; sets
nextdigit to 6 and i = i / 10; sets i to 45 so i is ready
to have the next digit extracted.
*/
{
long int nextdigit;
if(i < 0)
{
sign = '-';
i=abs(i);
}
else sign='+';

while(i != 0)
{
nextdigit=i % 10;
digit.push_back(nextdigit);
i=i/10;

}

}

bigInt::bigInt(const string& s)
{ convertString(s);
}

void bigInt:rint(ostream& os) const
{ int k;

os<<sign;
for(k = digit.size() - 1; k >= 0; k--) //print right to left
os<<digit[k]; //high order digits first
}

void bigInt::read(istream& is)
{ string s;

is>>s;
convertString(s);
}

bigInt& bigInt:perator++() //++ only works correctly for positive
bigInts
{ int i, sum, newdigit, carry;

sum = digit[0] + 1;
newdigit = sum % 10;
carry = sum / 10;
digit[0] = newdigit;
i = 1;
while(i < digit.size() && carry != 0)
{ sum = digit + carry;
newdigit = sum % 10;
carry = sum / 10;
digit = newdigit;
i++;
}
if (carry != 0) digit.push_back(carry);
return *this;
}

void bigInt::convertString(const string& s)
{ int j, k, nextdigit;

if (s[0] == '+' || s[0] == '-')
{ sign = s[0];
k = 1; //process from subscript 1 so sign not considered again
}
else
{ sign = '+'; //no sign in string then positive number
k = 0; //no sign so process from subscript 0
}

digit.resize(0); //resize the vector digit to 0
for(j = s.size() - 1; j >= k; j--) //process digits in string from
right
if (isdigit(s[j])) //to left - low order digits
first
{ nextdigit = s[j] - '0'; //convert character digit to int
digit.push_back(nextdigit);
}
else
{ cerr<<"Bad string argument for convertString function"<<endl;
cin.get(); cin.get(); //to pause console i/o screen
exit(1);
}
}

ostream& operator <<(ostream& os, const bigInt& bi)
{
bi.print(os);
return os;
}

istream& operator >>(istream& is, bigInt& bi)
{
bi.read(is);
return is;
}

bigInt bigInt:perator *(const bigInt& bi2)const
{
int mul;
int carry=0;
int k;
int len=this->digit.size();
bigInt tem;



for(k=0;k<len;k++)
{



mul=(digit[k]*bi2.digit[k])+carry;
carry=mul/10;
mul=mul%10;
tem.digit.push_back(mul);




}
if(carry != 0)tem.digit.push_back(carry);
tem.sign='+';

return tem;


}

bigInt bigInt:perator +(const bigInt& bi2)const//works only for both
numbers positive.
{
int sum;
int carry=0;
int k;
int len=digit.size();
bigInt temp;

if(digit.size() == bi2.digit.size())//this addition to take place if
both numbers are of equal length.
{

for(k=0;k < len; k++)
{
sum=digit[k]+bi2.digit[k]+carry;
carry=sum/10;
sum=sum%10;
temp.digit.push_back(sum);
}
if(carry != 0)temp.digit.push_back(carry);
}//end of code for addition if both numbers are equal.

if(digit.size() < bi2.digit.size())//if this has fewer numbers
{
for(k=0;k < digit.size();k++)//this loop will go on till the one
with fewer numbers will be exhausted
{
sum=digit[k]+bi2.digit[k]+carry;
carry=sum/10;
sum=sum%10;
temp.digit.push_back(sum);
}
for(k=digit.size();k<bi2.digit.size();k++)//this will work on the
left over digits of the big digit.
{
sum=bi2.digit[k]+carry;
carry=sum/10;
sum=sum%10;
temp.digit.push_back(sum);
}
if(carry != 0)temp.digit.push_back(carry);
}

if(bi2.digit.size() < digit.size())//if bi2 is the smaller number,
then it will be on the bottom.
{

for(k=0;k<bi2.digit.size();k++)
{
sum=digit[k]+bi2.digit[k]+carry;
carry=sum/10;
sum=sum%10;
temp.digit.push_back(sum);
}
for(k=bi2.digit.size();k<digit.size();k++)//this will work on the
left over digits of big int.
{
sum=digit[k]+carry;
carry=sum/10;
sum=sum%10;
temp.digit.push_back(sum);
}
if(carry != 0)temp.digit.push_back(carry);
}



temp.sign='+';
return temp;
}

const bigInt& bigInt:perator =(long int i)
{
bigInt temp(i);
int k=0;

digit.erase(this->digit.begin(), this->digit.end());

while(k < temp.digit.size())
{
this->digit[k]=temp.digit[k];
k++;
}
this->sign='+';
return *this;




}

const bigInt& bigInt:perator =(const bigInt& bi2)
{
int size = bi2.digit.size(); // get vector size
digit.erase(this->digit.begin(), this->digit.end()); // erase current
vector
this->digit.resize(size); // set new vector size
for(int i= 0; i < size; i++)
{
this->digit=bi2.digit;
}
this->sign='+';
return *this;
}

bool bigInt:perator ==(const bigInt& bi2)const
{
bool isIT=false;


if( bi2.digit.size() == this->digit.size() )
{
for(int i=0; i < this->digit.size();i++)
{
if(bi2.digit != this->digit)return isIT;
}
isIT=true;

}

return isIT;;

}

bool bigInt:perator < (const bigInt& bi2)const
{
bool isIt=false;

if(this->digit.size() != bi2.digit.size())return( this->digit.size()
< bi2.digit.size());

for(int i=0;i < this->digit.size();i++)
{
if(this->digit < bi2.digit)return isIt=true;
}
return isIt;


}
=================================================================================

testbigInt.cpp
=================================================================================
#include<iostream>
#include "bigInt.h"
using namespace std;

int main(){
bigInt bi1("+19999999999999999999999999999999999");
bigInt bi3(2);
bigInt bi2(21);

cout << "bi1: " << bi1 << endl;
cout << "bi2: " << bi2 << endl;
cout << "bi3: " << bi3 << endl;
cout << "bi2 + bi3: " << bi2*bi3 << endl;


return 0;
}

=================================================================================

 

[Ivan Vecerina]

Hi, im working on this bigInt class. Need help writing algorithm for
the operator*, andy help will be appreciated.

No reply yet it seems, so I'll bite...

typedef std::vector<int> Num;
const int base = 10;

void Mul(Num const& a, Num const& b, Num& dst)
{
// allocate the destination number
dst.assign( a.size() + b.size(), 0 );

// sum up products of all digit pairs
for( int i = 0 ; i<a.size() ; ++i )
for( int j = 0 ; j<b.size() ; ++j )
{
dst[i+j] += a*b[j];
}

// propagate carry from the lowest digit up
int carry = 0;
for( int d = 0 ; d<dst.size() ; ++d )
{
int digit = dst[d] + carry;
dst[d] = digit % base;
carry = digit / base;
}

// drop any leading zeroes in highest position
while( dst.back()==0 ) dst.pop_back();
}

Written on the fly and not tested,
plus quite some room for optimization.
But I hope this helps !

Ivan

 

[Erik]

Hi, im working on this bigInt class. Need help writing algorithm for

the operator*, andy help will be appreciated. Thanks in advance

Do it in the same way as when you multiply numbers on paper.

/ Erik

 

[rossum]

Hi, im working on this bigInt class. Need help writing algorithm for
the operator*, andy help will be appreciated. Thanks in advance

[snip]

As well as Ivan's suggestion you could have a look at the Karatsuba
method: http://mathworld.wolfram.com/KaratsubaMultiplication.html

Karatsuba is also covered in Crandall and Pomerance which is good for
numerical methods if you are into that sort of thing.

http://www.amazon.com/exec/obidos/ASIN/0387947779/qid=1065990546

rossum