471,872 Members | 1,440 Online

# bigInt operator* help

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,
//of bigInts, assignment of a bigInt or long int to a bigInt and ==/<
//comparison of bigInts. The operators
//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
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

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::print(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
}

{ string s;

is>>s;
convertString(s);
}

bigInt& bigInt::operator++() //++ 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[i] + carry;
newdigit = sum % 10;
carry = sum / 10;
digit[i] = 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)
{
return is;
}

bigInt bigInt::operator *(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::operator +(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::operator =(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::operator =(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[i]=bi2.digit[i];
}
this->sign='+';
return *this;
}

bool bigInt::operator ==(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[i] != this->digit[i])return isIT;
}
isIT=true;

}

return isIT;;

}

bool bigInt::operator < (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[i] < bi2.digit[i])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;
}

================================================== ===============================
Jul 19 '05 #1
3 7954
"KK" <ka***********@yahoo.com> wrote in message
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[i]*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
--
http://ivan.vecerina.com
http://www.brainbench.com <> Brainbench MVP for C++
Jul 19 '05 #2
On 10 Oct 2003 15:34:56 -0700, ka***********@yahoo.com (KK) wrote:
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/Karatsu...plication.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/AS...d%3D1065990546

rossum
--

The Ultimate Truth is that there is no Ultimate Truth
Jul 19 '05 #3
> 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
Jul 19 '05 #4

### This discussion thread is closed

Replies have been disabled for this discussion.