Jump to content
  • Advertisement
Sign in to follow this  
b1gjo3

Yet another bigint

This topic is 3623 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

hi everyone, im pretty new to the bigint idea but i know its been done a bunch of times. heres the beginning of my bigint
const unsigned int MAX_UINT = 4294967295;

class bigint
{
private:
	unsigned int *lpValue;
public:
	long count;
	bigint();
	~bigint();
	bigint& operator=(unsigned int);
	bigint& operator+=(unsigned int);
};

bigint::bigint()
{
	lpValue = new unsigned int;
	count = 0;
	lpValue[count] = 0;
}
bigint::~bigint()
{
	if(count > 0)
		delete [] lpValue;
    else
        delete lpValue;
}

bigint& bigint::operator=(unsigned int dVal)
{
	lpValue[count] = dVal;
	return *this;
}

bigint& bigint::operator+=(unsigned int dVal)
{
	int newVal;

	if (MAX_UINT - this->lpValue[count] <= dVal)
	{
		newVal = dVal - (MAX_UINT - this->lpValue[count]);
		this->lpValue[count] += MAX_UINT - this->lpValue[count];
	}

	if(this->lpValue[count] >= MAX_UINT)
	{
		unsigned int *nInt = new unsigned int[++count];

        for(int i = 0; i <= (count - 1); ++i)
			nInt = lpValue;

        delete [] lpValue;

		lpValue = new unsigned int[count];

		for(int i = 0; i <= count; ++i)
			lpValue = nInt;

		delete [] nInt;

		lpValue[count] = newVal;
	}
	else
		lpValue[count] = dVal;

	return *this;
}

so for the number 8589934593, the data in bigint would be.. lpValue[0] = 4294967295 lpValue[1] = 4294967295 lpValue[2] = 3 say i created a method called display_bigint how would i make the array lpValue display 8589934593 any ideas would be great. thanks

Share this post


Link to post
Share on other sites
Advertisement
1) Use std::vector<>
2) Don't mix new and new []
3) MAX_UINT should probably be derived from std::numeric_limits<unsigned>::max()
4) The member "count" is public? This is a massive mistake - you have lost the ability to control your data interrelationship.
5) Follow the Rule of Three.
6) Instinctively, I would expect "count" should equal the number of elements in the array. This is not the case.
7) Simplify your code by extracting common expressions. In bigint::operator+=(unsigned int) you re-use the sub-expression "MAX_UINT - this->lpValue[count]". By naming this value you increase the overall readability.
8) In the above function, can you guarentee that "newVal" is initialised? It is unclear because you are mixing bigint logic with memory management, which renders the code very difficult to read.

As for your actual question, I would urge you to see if you can change how you store the information. Think about how individual byte values can be used to make up a word. The value of the word isn't simply the sum of the byte values, but is determined with the byte values and the position of the byte in the word.

Share this post


Link to post
Share on other sites
Quote:
Original post by _fastcall
for n=number_of_digits_in(bigint):
     output: ( bigint / pow(10, n) ) % 10



Does this give you any ideas?


i cant find out the number of digits unless you meant that to be the index of the array. and for the output, i think your referring bigint to be element of the array at n index?

so are you saying..
for (int n = 0; n < sizeofarray; n++)
display (array[n] / pow(10,n) ) % 10

thanks

Share this post


Link to post
Share on other sites
Quote:
Original post by rip-off
1) Use std::vector<>
2) Don't mix new and new []
3) MAX_UINT should probably be derived from std::numeric_limits<unsigned>::max()
4) The member "count" is public? This is a massive mistake.
5) Follow the Rule of Three.
6) Instinctively, I would expect "count" should equal the number of elements in the array. This is not the case.
7) Simplify your code by extracting common expressions. In bigint::operator+=(unsigned int) you re-use the sub-expression "MAX_UINT - this->lpValue[count]". By naming this value you increase the overall readability.
8) In the above function, can you guarentee that "newVal" is initialised?
It is unclear because you are mixing bigint logic with memory management, which renders the code very difficult to read.

As for your actual question, I would urge you to see if you can change how you store the information. Think about how individual byte values can be used to make up a word. The value of the word isn't simply the sum of the byte values, but is determined with the byte values and the position of the byte in the word.


For #4, I had that as public so i could see what was going on in main() easily, i know this is bad practice but good eye. for #8, is how im storing the data not a logical way, is there no way to represent the big number if i have it stored the way i have it? If not, how do you suggest i change the way the information is stored? And what do you mean by word?

Thanks.

Share this post


Link to post
Share on other sites
Quote:

For #4, I had that as public so i could see what was going on in main() easily, i know this is bad practice but good eye.


You can use a debugger, or you can have a public const member function to return the private count value for debugging purposes. That way clients cannot violate your invariants, yet can inspect the value. Though clients shouldn't really care about that value, its an implementation detail.

Quote:

If not, how do you suggest i change the way the information is stored? And what do you mean by word?


A "word" in comuter architecture is the processors "native size", the number of bytes it prefers to work with. See here.

Find out how the value 4,294,967,295 is stored in a four byte word. Each byte can only store 0-255, so if they used your method the maximum value would be 1,020.

You might such research to be enlightening [smile]

Share this post


Link to post
Share on other sites
I can see that 4294967295 is 2^31 + 2^30 + ... + 2^0
But if im adding, how do i know when to skip a bit. For instance.. how do i know that when im adding two numbers that equal 4294967294, to disregard 2^0, furthermore, how do i display such a number that is so big because nothing would be able to store/display 2^128.

Thanks

Share this post


Link to post
Share on other sites
Quote:
Original post by b1gjo3
hi everyone, im pretty new to the bigint idea but i know its been done a bunch of times.

heres the beginning of my bigint
*** Source Snippet Removed ***

so for the number 8589934593, the data in bigint would be..
lpValue[0] = 4294967295
lpValue[1] = 4294967295
lpValue[2] = 3

say i created a method called display_bigint
how would i make the array lpValue display 8589934593
any ideas would be great.

thanks
No, that's now how the bigint data should be for 8589934593. Doing it that way, you'd use upp all your RAM and still never manage to represent 2^128, whereas that should only take 4 longs. 8589934593 should only be two longs, one of which will be a 3 and the other will be a 1. So I'm not surprised you're having trouble writing something moderately difficult like a bigint class. It's because you're taking a completely wrong approach.

You should never have code that works out which operator delete to call. In this case if you're using dynamic memory (which isn't even a must for a class like this) then only use the array version.
That operator = is an accident waiting to happen. Your += can increment count, and then calling = causes a crash. If you mean zero, then just use 0.
That += code is unforunately of no use whatsoever for a bigint class. If you really want to do this at all, you'll have to delete the entire function body and start over, the only useful bit is the return *this. You need to work out how bigint classes are supposed to work, first. It should help to think about how numbers between 256 and 65535 are stored in two bytes.
Using "this->" is redundant in your code. You don't need that syntax for locals in this class, just refer to them directly.

Have you learn't about constructor initialiser lists? You could use them here.

To display the value, all you need to do is to be able to divide the number by 10 and get the remainder. The remainder is 1 digit and you repeat that until the number is zero and then collect up those digits in reverse order, converting each one to ASCII as you go.

I have complete bigint classes of my own on my webpage (fixed-size and dynamic).

Share this post


Link to post
Share on other sites
thank you for your help

Quote:
Original post by iMalc
I have complete bigint classes of my own on my webpage (fixed-size and dynamic).


if your refering to here http://homepages.ihug.co.nz/~aurora76/Malc/Useful_Classes.htm. This is what got me inspired to write a variably sized bigint. I tryed to learn from it but its just to big/complex for me to learn from plus no code comments, so i decided to start from the ground up. I recommend you go back and comment your code so when you modify it 10+ years from now you'll know why you did something where you did. Ive always considered this good programming practice myself. I have used your bigint for leisure purposing watching 2^100000 calculate slowly lol, i just like to see all those digits!

here is my modified code so far

class bigint
{
public:
bigint();
bigint(int i);
bigint(std::string i);
~bigint();
const vector<int>* get_digits() const;
const char& get_sign() const;
friend std::ostream& operator<< (std::ostream&, const bigint&);
private:
char sign;
vector<int> digit;
};

bigint::bigint() {}
bigint::~bigint() {digit.clear();}

bigint::bigint(int i)
{
long nextDigit;

if (i < 0)
{
sign = '-';
abs(i);
}
else
sign = '+';

while (i != 0)
{
nextDigit= i % 10;
digit.push_back(nextDigit);
i /= 10;
}
}

bigint::bigint(std::string i)
{
if (atoi(i.c_str()) < 0)
sign = '-';
else
sign = '+';

for(int k = i.length() - 1; k >= 0; k--)
{
digit.push_back(atoi(i.substr(k, 1).c_str()));
}
}

const vector<int>* bigint::get_digits() const
{
return &digit;
}

const char& bigint::get_sign() const
{
return sign;
}

std::ostream& operator<<(std::ostream& output, const bigint& theInt)
{
int k = 0;

if (theInt.get_sign() != '+')
output << '-';

for(k = theInt.get_digits()->size() - 1; k >= 0; k--)
output << theInt.get_digits()->operator[](k);

return output;
}




still havnt followed rule of three yet, please leave some comments though. I learned through research that bigint variables do their operations through elementary algorithms (lining up the digits and having a carry etc..) This will make all the basic operations easy (add/sub/mult/div).

Share this post


Link to post
Share on other sites
Quote:
Original post by b1gjo3
please leave some comments

You should prefer bigint(const std::string& i) over bigint(std::string i).

Why would you give clients a pointer to your internal vector?

You should prefer char get_sign() over const char& get_sign(). Or better yet, make the sign a bool.

Your destructor is superflous, you don't need to clear the vector.

The line abs(i); doesn't do anything, it has to be i = abs(i);

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!