473,562 Members | 2,604 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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==(cons t 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(c onst string& s); //converts string into bigInt
//representaion., defined
};

//overloads << and >> operators as non-member functions using
//public member functions print and read.
ostream& operator<<(ostr eam& os, const bigInt& bi); //defined
istream& operator>>(istr eam& 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(o stream& 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(is tream& is)
{ string s;

is>>s;
convertString(s );
}

bigInt& bigInt::operato r++() //++ 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::convert String(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::operato r *(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.pus h_back(carry);
tem.sign='+';

return tem;
}

bigInt bigInt::operato r +(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.pu sh_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.siz e();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.pu sh_back(carry);
}

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

for(k=0;k<bi2.d igit.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.pu sh_back(carry);
}

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

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

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

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


}

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

bool bigInt::operato r ==(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::operato r < (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<iostre am>
#include "bigInt.h"
using namespace std;

int main(){
bigInt bi1("+199999999 999999999999999 99999999999");
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 8075
"KK" <ka***********@ yahoo.com> wrote in message
news:6e******** *************** ***@posting.goo gle.com...
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***********@y ahoo.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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

10
2453
by: MK | last post by:
Hello, I use BigInt lib from: http://www.codeguru.com/Cpp/data/data-misc/values/article.php/c4563/ It doesn't work properly. I describe my problem: http://www.codeguru.com/Cpp/data/data-misc/values/comments.php/c4563/?thread=5367 Please, help me! If anybody have good version of the bigint lib, tell me please
1
3985
by: MK | last post by:
I need div two big int. I use this lib: https://sourceforge.net/projects/cpp-bigint/ I create simple project and include two file bigint.h and bigint.cpp (Precompiled headers is not using) When I try build I get: Why? Help. :--------------------Configuration: av - Win32 Debug-------------------- Compiling...
5
6664
by: Rafa³ Maj Raf256 | last post by:
Hi, is there some small project that proviedes bigint, best as a C++ class, or just as set of struct/functions (C-style)? Something like GMP and it's bigint, but I want to have it just in one small source file as small as needed, not to have entire advanced GMP library. -- Rafa³ 'Raf256' Maj
2
3110
by: Jon | last post by:
Since there is no native support for 64bit integers in dbExpress, it is not trivial to fetch a BIGINT from SQL 2k. If it is possible, how can a BIGINT be fetched using TParam or TField? Any help appriciated
0
1890
by: Dan Ruthers | last post by:
Hi, I have read in this list and elsewhere the problem with indexes and big int. Still, I have an index that is used or not, depending of the parameter value used in the query. I am using PostgreSQL 7.4.3 on Linux RH ES3. Here's the table: test=> \d dmaildatum Table "public.dmaildatum" Column | Type | Modifiers...
2
4030
by: Dave Bazell | last post by:
I was using Math::BigInt and found that postive integers have a leading plus sign: +12345678900000 Is there a way to supress this? Thanks, Dave
5
6764
by: mamorgan1 | last post by:
We made a poor decision a long time ago when designing our database structure. We used bigint data types as the identity keys for many of our base tables. For many reasons I would like to change these fields to int at the largest. The largest data in these fields is around 200,000. I know that int can easily store this. What should I be...
2
2942
by: JimN1 | last post by:
I am reading in a SQL data type of Numeric and trying to write it out to another SQL table where the field is defined as BigInt. I am presetly putting the data into a Dim indata as String. I can see the data there but I get an error when I try to put it into the SQL field of BigInt. Is there a conversion function or what data type to I need to...
0
1184
by: SQLGuy | last post by:
My company had a partitioned view across 5 SQL 2000 and 2005 clusters, with 1.9B rows of data, with the key using datatype of int. At this point, we need to convert everything to bigint very soon. We were hoping to change the view to cover both int and bigint so that we do not have to change all 1.9B rows of data to bigint. However, we are running...
0
7579
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language...
0
7874
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. ...
1
7630
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
0
6228
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
1
5479
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
0
5198
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert...
0
3626
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...
1
1192
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
0
907
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.