LongInt class

[afdave14]

Folks, i have been working on a LongInt class for the past two weeks almost. For those of you who may not understand what I'm referring to, this class replaces the normal int type by going beyond it's normal ranges and being able to calculate much larger numbers (for example, 1000!. It's a very big number I assure you. Google it!) Anyway, in order to accomplish this, I obviously have to make lots of operators: LongInt::operator+, LongInt::operator!=, etc. Well, right now, I'm working on the operator+. It is killing me. Without trying to explain all of my problems, I will just tell you about the one I am focusing on right now.

Ok, when I pass in two negative LongInt's:
LongInt(-999) + LongInt(-999)
I've got some weird stuff going on. In my operator, I say, "if the signs are the same, move in here. If the signs are both negative, move in here." Well, when I get inside, I change the signs of the two numbers being passed in (I know it works, I've cout'ed the results.) and return the negative of the sum of the two numbers:
return (-(*this + k));
For some stupid reason, it doesn't work. I tried to trace my code it ends up going into an if-statement of the operator+ method that says if the two signs are equal and they are positive, move in. Which makes sense because I changed the sign. But why doesn't it return it's value to my original return (-(*this + k));? I tried to get around it by creating a bool variable that said to return the negative of an operation if what I'm trying to do is the case but I quickly realized that will not work because once I go back into the method, the variable will be reset. I'm confused, please help!

[PiMaster]

Sounds like you aren't using two's complement, which would probably simplify this a lot. Then again, it probably also matters how you're storing the data. Come to think of it, I've always wondered how you would implement something like this...

http://en.wikipedia.org/wiki/Two's_complement

[Duthomhas]

Are you storing the bignum as sign + magnitude or is it a two's complement bit array?

I'm writing one also, and I've got it as sign + magnitude. Something to keep in mind for that is that you can only add numbers with the same sign. Otherwise you must negate the rhs and use a subtraction algorithm. A code snippit from my code:

      biginteger& operator += ( const biginteger& that )
        {
        if (this->sign != that.sign)
          return *this -= biginteger( that ).negate();

        /* addition algorithm goes here */

        return *this;
        }

Notice how it makes sure the signs are identical before performing any work. If they are not, it farms out to the proper algorithm (subtraction).

Hope this helps.

[afdave14]

I appreciate both of your's help. I am not using two's compliment, as I am not familiar with it. Even if it is more efficient, I don't really have time to go back and change it. But I will check it out sometime. It would just take too much time for me to go back and change what I have already.

Do you understand what I'm asking though, with my original question? For some reason, I get into the addition operator, and get into an if-statement that says to return the negative of the addition of the two numbers passed in. It DOES indeed go into the right if-statement but for some reason I don't get a negative. Does that make sense? Thanks

[Duthomhas]

Not really, because you haven't really answered the questions we reciprocated.

I assume you are using a sign + magnitude representation.

To answer your original question, (-3 + -4) != -(-3 + -4).

[afdave14]

I apologize. What exactly is the "sign + magnitude" representation? It sounds like what I am using. For each LongInt object I assign a sign of either +1 or -1.

And yes, I do understand that (-3 + -4) != -(-3 + -4). What I did was change the sign of the 3 and 4 so it would go from (-3 + -4) to -(3 + 4).

[Duthomhas]

Yes, that is what sign-magnitude is. If you are still unsure, google it.

I think I missed something in your first post. You said you do this, right?

1. negate *this
2. negate k
3. return -(*this + k)

If you are and you are still getting error with negative numbers (but not with positive ones), post some code.

[ne555]

LongInt operator+(const LongInt &) const; You shouldn't change your parameters. Call another function add_but_dont_care_about_the_sign.

[Galik]

Have you checked your unary minus overload?

[afdave14]

@Duoas
You are correct. Here is my LongInt::operator+, LongInt::operator-, and LongInt::operator- (unary)

LongInt LongInt::operator+(LongInt & k)
{
	//std::cout <<"plus operator" << std::endl;
	//std::cout << "*this: " << *this << std::endl;
	//std::cout << "k: " << k << std::endl;
	LongInt ret;

	int a, b, carry = 0, size;
	size = (x.size() >= k.x.size() ? x.size() : k.x.size());

	ret.x.clear();
	
	if (sign != k.sign)
	{
		if (sign == 1 && k.x[k.x.size() - 1] < 0)
		{
			if (*this > -k)
			{
				k.sign = 1;
				k.x[k.x.size() - 1] *= -1;
				return (*this - k);
			}
			else if (*this < -k)
			{
				k.sign = 1;
				k.x[k.x.size() - 1] *= -1;
				return -(k - *this);
			}
		}
		else if (sign == -1 && k.sign == 1)
		{
			if (-*this > k)
			{
				sign = 1;
				x[x.size() - 1] *= -1;
				return -(*this - k);
			}
			else if(-*this < k)
			{
				sign = 1;
				x[x.size() - 1] *= -1;
				return (k - *this);
			}
		}
	}
	else if (sign == k.sign)
	{
		//std::cout << "signs equal" << std::endl;
		if (sign == -1 && k.sign == -1)
		{
			//std::cout << "negative" << std::endl;
			sign = 1;
			x[x.size() - 1] *= -1;
			//std::cout << "now?" << std::endl;
			k.x[k.x.size() - 1] *= -1;
			k.sign = 1;
			std::cout << "x[x.size() - 1]: " << x[x.size() - 1] << std::endl;
			std::cout << "k.x[k.x.size() - 1]: " << k.x[k.x.size() - 1] << std::endl;
			//std::cout <<"what's wrong" << std::endl;
			std::cout << "-(*this + k): " << -(*this + k) << std::endl;

			return (-(*this + k));
		}
		else if (sign == 1 && k.sign == 1)
		{
			std::cout << "ya" << std::endl;
			for (int i = 0; i < size; i++)
			{
				a = (i < x.size() ? x[i] : 0);
				b = (i < k.x.size() ? k.x[i] : 0);

				ret.x.push_back((a + b + carry) % 10);
				carry = (a + b + carry) / 10;
			}
	
			if (sign == -1 && k.sign == -1)
			{
				for (int i = 0; i < ret.x.size(); i++)
				{
					if (ret.x[i] < 0)
						ret.x[i] = -ret.x[i];
				}
				ret.x[ret.x.size() - 1] = -ret.x[ret.x.size() - 1];
			}

			return ret;
		}
	}
}

LongInt LongInt::operator-(LongInt & k)
{
	LongInt ret = *this;
	LongInt diff;

	int a, b, carry = 0, size;
	size = (x.size() >= k.x.size() ? x.size() : k.x.size());

	diff.x.clear();
	
	if (sign != k.sign)
	{
		if (sign == 1 && k.sign == -1)
		{
			k = -k;
			k.sign = 1;
			return (*this + k);
		}
		else if (sign == -1 && k.sign == 1)
		{
			sign = 1;
			*this = -*this;
			return -(*this + k);
		}
	}
	else if (sign == k.sign)
	{
		if (sign == -1 && k.sign == -1)
		{
			if (*this < k)
			{
				sign = 1;
				*this = -*this;
				k.sign = 1;
				k = -k;
				return -(*this - k);
			}
			else if (k < *this)
			{
				sign = 1;
				*this = -*this;
				k.sign = 1;
				k = -k;
				return (k - *this);
			}
		}
		else if (sign == 1 && k.sign == 1)
		{
			if (*this < k)
			{
				return -(k - *this);
			}
			else if (k < *this)
			{
				for (int i = 0; i < size; i++)
				{
					a = (i < x.size() ? ret.x[i] : 0);
					b = (i < k.x.size() ? k.x[i] : 0);

					if (b > a)
					{
						int j = i + 1;
						while (x[j] == 0)
							j++;

						ret.x[j]--;
						j--;

						while (j > i)
						{
							ret.x[j] = 9;
							j--;
						}
						a += 10;
					}
					diff.x.push_back(a - b);
				}
				for (int i = diff.x.size() - 1; i >= 0; i--)
				{
					if (diff.x[i] > 0)
						break;
					if (diff.x[i] == 0)
						diff.x.pop_back();
				}

				return diff;
			}
		}
	}
}

LongInt LongInt::operator-() const
{
	LongInt ret = *this;
	
	ret.sign = -1;
	ret.x[ret.x.size() - 1] *= -1;

	return ret;
}

Sorry it's a little messy. Besides the little debugging with the cout's I have going on, there is definitely some cleaning up I can do, but try to ignore it if you don't think it's causing any serious issues.

@ne555
It is actually necessary to, within the operator+, have an if-statement that changes the signs. Otherwise it will get all screwed up. If you go through my code you will understand why.

@Galik
Yes, I have. It works just fine.

[Duthomhas]

It is late for me, so give me a day to come back and look it over.
I'm off to bed.

[ne555]

ret.sign = -1;
ret.x[ret.x.size() - 1] *= -1;

Why are you repeating information? Could you explain your convention for negative numbers, please.

The idea was:

LongInt operator+(const LongInt &B) const{

  if( sign == B.sign ){
     LongInt result = this->add_but_dont_give_a_peanut_about_the_sign(B); //private method
     result.sign = sign;
     return result;
  }
  else //is a substraction
}

If I flollow your code correctly, you've also got a problem when the numbers are the "same", but with different sign.

[afdave14]

I am not actually repeating information. Changing the sign member variable doesn't actually change the actual value. It's just a value assigned to the object as a reminder of what it's sign is. I was not actually able to implement it in the the construction of the LongInt.

Again, if you read my code, you will understand that if the signs are negative, you MUST change the signs, add the values, then make the resulting value negative. Here is the logic that I came up with regarding adding and subtracting two numbers and the signs that they have:

Adding

	signs are NOT the same
		top is positive, bottom is negative
			top is bigger than bottom
				change sign of bottom to positive and subtract bottom from top
			top is smaller than bottom
				change sign of bottom to positive, subtract top from bottom 
				and make resulting sign negative
		bottom is positive, top is negative
			top is bigger than bottom
				change sign of top to positive, subtract bottom from top and 
				make resulting sign negative
			top is smaller than bottom
				change sign of top to positive and subtract top from bottom
	signs ARE the same
		both are positive
			just add them
		both are negative
			remove the signs, add, then put the negative on the result


Subtracting

	signs are NOT the same
		top is positive, bottom is negative
			change the sign to positive for the bottom and add the two				
				
		bottom is positive, top is negative
			change the sign of the top to positive and add the two
			and make resulting sign negative

	signs ARE the same
		both are positive
			top is bigger than bottom
				subtract like normal
			top is smaller than bottom
				subtract top from bottom and make resulting sign negative
		both are negative
			top is bigger than bottom
				change the sign of top and bottom to positive, subtract bottom from top, 
				and make the resutling sign negative
			top is smaller than bottom
				chage the sign of the top and bottom to positive and subtract top from bottom

[afdave14]

Keep in mind, there are some inconsistencies with my wording in my logic above. For instance, I don't always say to change the sign. Hopefully you can still understand

[jimc]

If you are still working on this, I see a couple bugs without going to far into it.

Your unary minus operator assumes that the sign of its input is positive. If you give it a negative LongInt, it will return an inconsistent LongInt with sign set to -1 and ret.x[ret.x.size()-1] set to a positive value.

	ret.sign = -1;
	ret.x[ret.x.size() - 1] *= -1;

The above bug or the bug with equal magnitudes that ne555 already pointed out may be causing your problem. You have test for *this<k and *this>k, but if the magnitudes are equal, your code will fall through without setting ret to anything.

You are overcomplicating things a lot with your representation. I would definitely recommend switching to storing the sign only one place, in your sign variable. Also, make sure it is initialized properly. I would also second the idea that your addition operator should not change its operands and you should have a separate function to add or subtract the magnitudes regardless of sign. This eliminates some conditionals, since you don't care what the sign is if they are the same sign; the result sign is just the same as the input signs.

Anyway, storing your value in (essentially) a "binary coded decimal" (BCD) is about the most inefficient way to do it and using division operators (%,/) is an inefficient way to handle a BCD.

	ret.x.push_back((a + b + carry) % 10);
	carry = (a + b + carry) / 10;

There are a few other things I would do differently, but this is your project.

[Duthomhas]

Also, your reasoning is a little long-winded.

────────────────────────

You only want to switch (from addition to subtraction) or (from subtraction to addition) if the sign of the numbers are different. A little algebra:

    (+a) + (-b) == (+a) - (+b)
    (-a) + (+b) == (-a) - (-b)

You are used to this from elementary school: 4 + -5 is the same as 4 - 5.

Notice that only the sign of b changed when we switch from addition to subtraction? The sign of a did not matter. (Well, except that it was different from the sign of b.)

────────────────────────

If the signs of the numbers are the same, then you are set to continue. The only thing left to consider is the magnitude of a must be greater than or equal to the magnitude of b.

Be careful when checking magnitude. A gross indicator of magnitude is the length of the number, but if the lengths are equal you must compare the most significant digits to see which is greater. For example:

    123 ≥  79    True because '123' is longer than '79'
    941 ≥ 284    True because '9' is greater than or equal to '2'

For subtraction, if this condition does not hold, then you need to reorder your numbers and compute the answer recursively, then adjust the sign of the result appropriately. For example, since:

    28 < 93

In order to compute 28 - 93 you must reorder it to -(93 - 28). Algebra saves the day again. :-)

────────────────────────

BTW, once you've got it figured out, check out my Bignum Challenge. I'd like to see your LongInt class there.
http://www.cplusplus.com/forum/lounge/32041/


Hope this helps.

[afdave14]

It does help. Thank you guys. I decided to return to the drawing board and re-create my LongInt class. The way I was doing it before was, if the number was negative, multiplying the first number by -1. So if the number was -123, instead of storing it as 123 with -1 as the sign, I stored it as -123 with -1 as the sign. BIG mistake. And yes, most of you pointed that out. I didn't see why that was a bad idea until I posted this up here. Again, thanks guys, and hopefully I can get this done soon!