OJ Board

Posted: **Tue Jul 25, 2006 9:27 pm**

Hey guys and gals, I'm getting excited to code my own Big Integer library. But of course, I will need your advices and suggestions in making it as efficient as possible! I designed this Big Integer class with some references to the BigInteger class designed by Suman, which can be downloaded here.

I used a fixed array to store each individual digit of a Big Integer, an integer to store the number of digits in the Big Integer, and a boolean value if the Big Integer is negative.

Ok, here is the code for the abs() function in my library (which returns the absolute value of the Big Integer).

Code: Select all

BigInt abs(BigInt a)
{
	a.isNegative = false;

	return a;
}

I'm wondering if there's any way of making the abs() function as efficient as possible? (Maybe returning by reference? But I don't really know how) By the way, I want it to pass by value because I don't want to change the original Big Integer.

What I saw from Suman's class is

Code: Select all

  BigInteger& abs(BigInteger& arg)
  {
      BigInteger& ret = *new BigInteger(arg);
      ret.isNegative = false;
      return ret;
  }

I do not understand this..
"BigInteger& ret = *new BigInteger(arg);"
Can anyone please explain?

And, thanks for reading this post and helping!

Posted: **Wed Jul 26, 2006 1:47 am**

I am not sure if I know the answer to your question, but being that I recently implemented my BigInt (in Java), I would just suggest to store more than one digit in that array - I used 4 (so products would fit in int), but you can use 8 or 9.
It is much faster - it will pay off in a long run. Well, unless when after the upgrade they allow java.math.* - then I will feel veryverysilly.

Nah, the pleasure of finishing it is priceless :)

I even got some stuff that's not in BigInteger, like integer square root.

I'll give a shot at answering your question anyway - create new BigInt using the passed BigInt and return that one? Hm, that is another thing that should be done - keep them immutable (e.g. when you add two, return third, not one of them that is changed) It tends to get messy if you change state of one BigInt from another. It does slow it down, but I think it's worth it.

Posted: **Wed Jul 26, 2006 2:22 am**

Hey Darko, thank you very much for your reply! It's very much appreciated.

Yup, I agree with you the pleasure of finishing it is priceless~ I'm working for it in full time right now!

Well, this is my progress so far:
- Implemented Addition operator
- Implemented Subtraction operator
- Implemented negative sign / operation

The addition of negative sign is kinda tedious, as I have to consider each situation (which has total 4 possibilities) while adding / subtracting two BigIntegers. But nevertheless, I've just finished implemented it, and finished debugging / optimizing it. I'm quite satisfied with the speed, but I'm just a little bit frustrated about the code though. It's kinda messy, I think I gotta clean it up a bit

By the way, I've tried to experiment with the code a lot... Sometimes, I'll just change a line of code in a certain function, and time the speed (by looping and calling the function), and test if the change makes the code faster. Most of the changes met my expectations, but here's one situation that I do not expect.

I've tried to overload the assignment operator, and by looping this line (something like BigInt x = "123"; ) 10000000 times, i found that by implementing the assignment operator manually, it runs faster than without implementing it myself.

Here is the code for my overloading assignment operator

Code: Select all

const BigInt& BigInt::operator =(const BigInt &b)
{
	this->numDigits = b.numDigits;
	this->isNegative = b.isNegative;
	for (int i = 0; i < numDigits; i++)
	{
		this->digits[i] = b.digits[i];
	}

	return *this;
}

Can someone explains this? I thought the default assignment operator does the exact same thing? In fact, I expected it will run about the same (or even faster) than my overloaded assignment operator...

Posted: **Wed Jul 26, 2006 7:18 am**

Do you compile your code as an optimized code? and what compiler do you use?

Posted: **Wed Jul 26, 2006 1:30 pm**

Yup I do think that I compiled as optimized code. I'm using Visual Studio 2005 .NET for compiling this BigInteger class.

Sometimes, I noticed that by changing some part of the code, I can gain some speed difference (by looping 1000000 times) like 10 seconds, but usually I have to sacrifice it for complexity (ie, i have to code in a way that is harder to understand)... So, I'm wondering, is it worth it to gain the extra 10 seconds? And how do I judge how many seconds are worth it (by increasing the complexity?)

I'm not that experienced in coding complex classes, so I will need as much help as possible. If you have experience in coding this BigInteger class, I would love to hear more from you. Thank you!

OJ Board

Designing my own Big Integer class, need your suggestions :)

Designing my own Big Integer class, need your suggestions :)