 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
akickdoe22@hotmail.com
Guest
|
 Posted: Sun Jan 16, 2005 5:29 am Post subject: please help me with large int addition |
 |
|
i could really use help finishing this addition program. I'm stuck on
the part that allows you to add any two large integers,up to 100
digits,(pos+pos, neg+neg, and pos+neg). could use hints ideas code
anything for neg+pos addition.
CODE SO FAR:
class INT {
int digits[100];
char sign;
public:
INT( ) {
sign = 'p';
for (int a=0; a<100; a++)
digits[a] = 0;
}
INT(int num) {
int a;
for (a=0; a<100; a++) digits[a] = 0;
if (num < 0) { sign = 'n'; num = num * -1; }
else sign = 'p';
a = 99;
while (num > 0) {
digits[a] = num % 10;
num = num / 10;
a = a - 1;
}
}
friend INT operator+(const INT&, const INT&);
friend ostream& operator<<(ostream&, const INT&);
friend istream& operator>>(istream&, INT&);
};
ostream& operator<< (ostream& os, const INT& num) {
int a = 0;
if (num.sign == 'n') os << '-';
while (a < 99 && num.digits[a] == 0)
a++;
while (a < 100)
os << num.digits[a++];
return os;
}
istream& operator>> (istream& is, INT& num) {
string number;
is >> number;
if (number.at(0) == '-') num.sign='n';
if (number.at(0) == '+') num.sign='p';
int start = 0;
if ( !isdigit(number.at(0)) ) start = 1;
int loc = 100-(number.length()-start);
for (int a=start; a<number.length(); a++)
num.digits[loc++] = number.at(a) - '0';
return is;
}
INT operator+(const INT& x, const INT& y) {
INT result;
if (x.sign == y.sign) {
result.sign = x.sign;
int a, carry = 0, total;
for (a=99; a>=0; a--) {
total=x.digits[a]+y.digits[a]+carry;
if (total > 9) carry = 1;
else carry = 0;
result.digits[a] = total % 10;
}
}
else {
//CODE TO ADD TWO NUMBERS WITH DIFFERENT SIGNS
}
return result;
}
Here's a sample main routine to test it:
int main( ) {
INT a, b, c;
cout << "Enter two large integers : ";
cin >> a >> b;
c = a + b;
cout << "The result is : " << endl;
cout << c << endl;
return 0;
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Harald Luessen
Guest
|
| Posted: Mon Jan 17, 2005 12:36 am Post subject: Re: please help me with large int addition |
|
|
On 16 Jan 2005 akickdoe wrote:
Looks like a troll's name.
| Quote: | i could really use help finishing this addition program. I'm stuck on
the part that allows you to add any two large integers,up to 100
digits,(pos+pos, neg+neg, and pos+neg). could use hints ideas code
anything for neg+pos addition.
|
I hope you have omitted the comment lines for a shorter posting only.
| Quote: | CODE SO FAR:
class INT {
|
Bad name for this class. Better is class LongDecimalInt.
| Quote: | int digits[100];
char sign;
public:
INT( ) {
sign = 'p';
for (int a=0; a<100; a++)
digits[a] = 0;
}
|
For real long arithmetic a 2-complement on base 256 in an array
would be better I think. But let's have a look at this homework.
Why not a bool flag for negative values?
An indentation of the code is strongly recommended.
| Quote: | INT(int num) {
int a;
for (a=0; a<100; a++) digits[a] = 0;
if (num < 0) { sign = 'n'; num = num * -1; }
else sign = 'p';
a = 99;
while (num > 0) {
digits[a] = num % 10;
num = num / 10;
a = a - 1;
}
}
|
Why start with the rightmost digit at index 99?
Reverse the array and you can easily extend it to more
than 100 digits. And it would be clearer to understand.
| Quote: | friend INT operator+(const INT&, const INT&);
friend ostream& operator<<(ostream&, const INT&);
friend istream& operator>>(istream&, INT&);
};
ostream& operator<< (ostream& os, const INT& num) {
int a = 0;
if (num.sign == 'n') os << '-';
while (a < 99 && num.digits[a] == 0)
a++;
while (a < 100)
os << num.digits[a++];
return os;
}
istream& operator>> (istream& is, INT& num) {
string number;
is >> number;
if (number.at(0) == '-') num.sign='n';
if (number.at(0) == '+') num.sign='p';
|
Why not num.sign == '+' or '-' if you want to use chars?
| Quote: | int start = 0;
if ( !isdigit(number.at(0)) ) start = 1;
int loc = 100-(number.length()-start);
for (int a=start; a<number.length(); a++)
num.digits[loc++] = number.at(a) - '0';
return is;
}
INT operator+(const INT& x, const INT& y) {
INT result;
|
A copy of the result is slow. If you want it fast use a
function with a 3rd result parameter instead of operator+.
| Quote: | if (x.sign == y.sign) {
result.sign = x.sign;
int a, carry = 0, total;
|
For 3 variables use 3 lines of code.
| Quote: | for (a=99; a>=0; a--) {
total=x.digits[a]+y.digits[a]+carry;
if (total > 9) carry = 1;
else carry = 0;
result.digits[a] = total % 10;
}
|
if ( carry )
overflow
| Quote: | }
else {
//CODE TO ADD TWO NUMBERS WITH DIFFERENT SIGNS
|
// X + -y : + x-y
// x + -Y : - y-x
// -X + y : - x-y
// -x + Y : + y-x
else
{
bool less = lessAbs(x, y); // you have to write this function
result.sign = 'p';
if ( less && y.sign == 'n'
| Quote: | | !less && x.sign == 'n' && !(y == x)
) |
{
// you have to write the operator==
result.sign = 'n';
}
int a;
int carry = 0;
if ( !less )
{
// x - y
for (a=99; a>=0; a--)
{
if ( x.digits[a] > (y.digits[a] + carry) )
{
result.digits[a] = x.digits[a] - (y.digits[a] + carry);
carry = 0;
}
else
{
result.digits[a] = 10 + x.digits[a] - (y.digits[a] + carry);
carry = 1;
}
}
if ( carry )
overflow
}
else
{
// y - x
...
}
}
Do the rest of the code and some optimisations yourself.
You have to write the operator==.
You have to write a function lessAbs( x, y ),
that is (abs(x) < abs(y))
| Quote: | }
return result;
}
Here's a sample main routine to test it:
int main( ) {
INT a, b, c;
cout << "Enter two large integers : ";
cin >> a >> b;
c = a + b;
cout << "The result is : " << endl;
cout << c << endl;
return 0;
|
I am not sure if my code is right, but it may give you some hints.
Harald
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
M Jared Finder
Guest
|
| Posted: Mon Jan 17, 2005 12:42 am Post subject: Re: please help me with large int addition |
|
|
[email]akickdoe22 (AT) hotmail (DOT) com[/email] wrote:
| Quote: | i could really use help finishing this addition program. I'm stuck on
the part that allows you to add any two large integers,up to 100
digits,(pos+pos, neg+neg, and pos+neg). could use hints ideas code
anything for neg+pos addition.
|
Adding a positive number to a negative number is the same as
subtraction. Remember in grade school how you subtracted digit by
digit, borrowing as necessary? Code that up, similar to how you already
wrote addition.
-- MJF
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
dtmoore
Guest
|
| Posted: Mon Jan 17, 2005 12:42 am Post subject: Re: please help me with large int addition |
|
|
Well, when the signs are different, you have to do subtraction rather
than addition. The simplest implementation requires you to first find
out which argument is "larger" (i.e. has a larger absolute value), and
then subtract the "smaller" one from it to obtain the absolute value of
the result. The sign of the result is of course the sign of the
"larger" argument. This should be fairly simple to do in your
implementation, especially if you add some code to keep track of the
length (i.e. number of digits) of the value stored in your INT class.
HTH,
Dave Moore
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Basil
Guest
|
| Posted: Mon Jan 17, 2005 7:59 pm Post subject: Re: please help me with large int addition |
|
|
[email]akickdoe22 (AT) hotmail (DOT) com[/email] wrote in message news:<1105820024.878654.31550 (AT) z14g2000cwz (DOT) googlegroups.com>...
| Quote: | i could really use help finishing this addition program. I'm stuck on
the part that allows you to add any two large integers,up to 100
digits,(pos+pos, neg+neg, and pos+neg). could use hints ideas code
anything for neg+pos addition.
|
Use complementary code for storage you large integers. For this code
you can use add for all digits (pos and neg). And sign of result will
be store to MSB (most significant bit).
See link:
http://sourceforge.net/projects/muntl/
or
http://www.mktmk.narod.ru/eng/muntl/muntl.htm
or
http://www.mktmk.narod.ru/rus/muntl/muntl.htm
if you read Russian.
This library use complementary code for store large integers.
This library for unsigned large integers, but you can use it for
signed large integers if treat MSB like signed bit.
Thank
Basil
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
kanze@gabi-soft.fr
Guest
|
| Posted: Tue Jan 18, 2005 11:04 pm Post subject: Re: please help me with large int addition |
|
|
Harald Luessen wrote:
| Quote: | On 16 Jan 2005 akickdoe wrote:
|
[...]
| Quote: | CODE SO FAR:
class INT {
Bad name for this class. Better is class LongDecimalInt.
|
Integers are integers. The fact that it is decimal is only
relevant for the rounding in floating or fixed point classes.
Just LongInt or BigInt.
| Quote: | int digits[100];
char sign;
public:
INT( ) {
sign = 'p';
for (int a=0; a<100; a++)
digits[a] = 0;
}
For real long arithmetic a 2-complement on base 256 in an
array would be better I think.
|
It depends. I've never analysed how you extend 2's complement.
I sort of agree that base 256 would be better. Or even base
2^16 or base 2^32, supposing you have a larger type (in order to
easily detect carry) -- at an assembler level, I'd use the
largest type available (because I would have a separate carry
bit).
Even for a simple implementation using decimal, why int[100]
instead of char[100]?
| Quote: | But let's have a look at this homework.
Why not a bool flag for negative values?
An indentation of the code is strongly recommended.
|
That could be an effect of how he posted. I've found that
Google looses my indentation.
| Quote: | INT(int num) {
int a;
for (a=0; a<100; a++) digits[a] = 0;
if (num < 0) { sign = 'n'; num = num * -1; }
else sign = 'p';
a = 99;
while (num > 0) {
digits[a] = num % 10;
num = num / 10;
a = a - 1;
}
}
Why start with the rightmost digit at index 99?
Reverse the array and you can easily extend it to more than
100 digits. And it would be clearer to understand.
|
Ah, big-endian or small-endian. That is the question?
Small endian is more convenient for addition and subtraction,
big endian for multiplication and division.
Why not std::deque<char>, and have it both ways:-)?
Seriously, why not generate backwards, then use std::reverse?
| Quote: | friend INT operator+(const INT&, const INT&);
|
I wouldn't make this one a friend.
| Quote: | friend ostream& operator<<(ostream&, const INT&);
friend istream& operator>>(istream&, INT&);
};
ostream& operator<< (ostream& os, const INT& num) {
int a = 0;
if (num.sign == 'n') os << '-';
while (a < 99 && num.digits[a] == 0)
a++;
while (a < 100)
os << num.digits[a++];
return os;
}
istream& operator>> (istream& is, INT& num) {
string number;
is >> number;
if (number.at(0) == '-') num.sign='n';
if (number.at(0) == '+') num.sign='p';
Why not num.sign == '+' or '-' if you want to use chars?
int start = 0;
if ( !isdigit(number.at(0)) ) start = 1;
int loc = 100-(number.length()-start);
for (int a=start; a<number.length(); a++)
num.digits[loc++] = number.at(a) - '0';
return is;
}
INT operator+(const INT& x, const INT& y) {
INT result;
A copy of the result is slow. If you want it fast use a
function with a 3rd result parameter instead of operator+.
|
Rather difficult to do if you are overloading operator+.
Of course, the classical solution is to first overload
operator+= (as a member), and then define operator+ in terms of
it and the copy constructor.
| Quote: | if (x.sign == y.sign) {
result.sign = x.sign;
int a, carry = 0, total;
For 3 variables use 3 lines of code.
|
Also, don't define a variable until you can initialize it.
| Quote: | for (a=99; a>=0; a--) {
|
So we would have:
for ( int a = 99 ; a >= 0 ; -- a )
Personally, I prefer something like:
int a = 100 ;
while ( a > 0 ) {
-- a ;
// ...
}
| Quote: | total=x.digits[a]+y.digits[a]+carry;
if (total > 9) carry = 1;
else carry = 0;
result.digits[a] = total % 10;
|
total += x.digits[ a ] + y.digits[ a ] ;
results.digits[ a ] = total % 10 ;
total /= 10 ;
I'd also call it carry, or something like that.
| Quote: | }
if ( carry )
overflow
|
He did sort of ignore error handling:-).
I'd have just sent him to Knuth:-). It's all clearly explained
there, if you know how to read Knuth. And you'll have to learn
how to read Knuth if you want to become a computer scientist.
| Quote: | Do the rest of the code and some optimisations yourself.
You have to write the operator==. You have to write a
function lessAbs( x, y ), that is (abs(x) < abs(y))
|
Actually, I'd start with the full complement of comparison
operators. Which will need a lessAbs too:-). I'd also do abs()
pretty quickly -- given his representation, it is really
trivial.
| Quote: | }
return result;
}
|
--
James Kanze GABI Software http://www.gabi-soft.fr
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
