Sign in to follow this  

Yet another bigint

This topic is 3316 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[i] = lpValue[i];

        delete [] lpValue;

		lpValue = new unsigned int[count];

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

		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
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
Quote:
Original post by DevFred
Why would you give clients a pointer to your internal vector?


so the function << can access the digits.


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

if (theInt.get_signed() == true)
output << '-';

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

return output;
}




if there is another way i would love to get rid of such function

thanks

-----------------------------------------------------------------
nvm, i could pass output to a function called print.

Share this post


Link to post
Share on other sites
Quote:
Original post by b1gjo3
Quote:
Original post by DevFred
Why would you give clients a pointer to your internal vector?

so the function << can access the digits.

It already can, because you declared it as being a friend.

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

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

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

return output;
}

I also changed your funny .operator[](k) to [k]

Share this post


Link to post
Share on other sites
Don't you want to hold the chunks in an std::vector<unsigned> (or perhaps std::vector<unsigned long>) rather than an std::vector<int>?

After closer inspection, I think I see what you're doing, now. You should think of the elements of the vector as the digits in a base MAX_UINT+1 number, otherwise you're wasting huge amounts of memory (proportionally).

<edit>
For example, suppose you change to using std::vector<unsigned int> and a particular bigint object contained four elements in the vector:

[38][528][2][4002]

This represents (38 * (MAX_UINT+1)^3) + (528 * (MAX_UINT+1)^2) + (2 * (MAX_UINT+1)^1) + (4002 * (MAX_UINT+1)^0)

This is just like the digits in a base 10 number:

942 = (9 * 10^2) + (4 * 10^1) + (2 * 10^0)
</edit>

Think back to when you learned how to add in school. You start out with adding the numbers in the "ones" column. If they overflow, then you carry the result to the next column and add it to the result of adding the "tens" column, etc...

To implement addition for a bignum (in a basic fashion), you do exactly the same thing, except the columns aren't "ones", "tens", "hundreds", etc. Instead they're "ones", "(MAX_UINT + 1)s", "(MAX_UINT + 1)^2s", "(MAX_UINT + 1)^3s", etc.

Share this post


Link to post
Share on other sites
Quote:
Original post by the_edd
Don't you want to hold the chunks in an std::vector<unsigned> (or perhaps std::vector<unsigned long>) rather than an std::vector<int>?

After closer inspection, I think I see what you're doing, now. You should think of the elements of the vector as the digits in a base MAX_UINT+1 number, otherwise you're wasting huge amounts of memory (proportionally).

Think back to when you learned how to add in school. You start out with adding the numbers in the "ones" column. If they overflow, then you carry the result to the next column and add it to the result of adding the "tens" column, etc...

To implement addition for a bignum (in a basic fashion), you do exactly the same thing, except the columns aren't "ones", "tens", "hundreds", etc. Instead they're "ones", "(MAX_UINT + 1)s", "(MAX_UINT + 1)^2s", "(MAX_UINT + 1)^3s", etc.


i meant for vector<int> and i see your point on wasting huge amounts of memory, seeing as how im only using a max 4-bits out of the 32-bits for each element in the vector. I suppose i have two options here..

Find/create a data element that only holds 4-bits saving large amounts of memory, or use the "ones", "(MAX_UINT + 1)s", "(MAX_UINT + 1)^2s" idea. Although the latter isn't quite clear to met yet. I will have to experiment with this using paper/pencil, i suspect its going to obvious once i get it though

<edit>
Quote:
Original post by the_edd
<edit>
For example, suppose you change to using std::vector<unsigned int> and a particular bigint object contained four elements in the vector:

[38][528][2][4002]

This represents (38 * (MAX_UINT+1)^3) + (528 * (MAX_UINT+1)^2) + (2 * (MAX_UINT+1)^1) + (4002 * (MAX_UINT+1)^0)


i suppose that the representation (38 * (MAX_UINT+1)^3) + (528 * (MAX_UINT+1)^2) + (2 * (MAX_UINT+1)^1) + (4002 * (MAX_UINT+1)^0) would have to be handled by the elementary adding up, because i cannot think of a data type that can handle that large of an operation. Also, how would i go about the operation (MAX_UINT+1)^3?

thanks for the insight

[Edited by - b1gjo3 on November 16, 2008 4:03:36 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by b1gjo3
i suppose that the representation (38 * (MAX_UINT+1)^3) + (528 * (MAX_UINT+1)^2) + (2 * (MAX_UINT+1)^1) + (4002 * (MAX_UINT+1)^0) would have to be handled by the elementary adding up, because i cannot think of a data type that can handle that large of an operation. Also, how would i go about the operation (MAX_UINT+1)^3?


You don't need to! To add 398456 * (MAX_UINT+1)^3 to a bigint, you simply need to add 398456 to the element at index 3 (taking care of overflow aka "carry").

To add 3000 (aka 3 * 10^3) to a base 10 number you add 3 to the 4th column. It's no different.

It's as simple as this:

Pretend that an unsigned int is only capable of holding the numbers 0 to 9. Now the element in the array are the digits of the base-10 numbers we know and love. Implement the algorithms you learned in school for basic arithmetic.

Once that's done, replace all references to 10 with MAX_UINT+1. Now you have a reasonably space efficient bigint class.

Share this post


Link to post
Share on other sites
Quote:
Original post by b1gjo3
Also, how would i go about the operation (MAX_UINT+1)^3?

You don't need to actually calculate (MAX_UINT+1)^3. That would be like figuring out 9 * 10^3 in order to calculate 900 + 4. You just add 9 to the thousands column and 4 to the ones column. No exponents needed, because they're built into the columns.

Share this post


Link to post
Share on other sites
so by keeping track of each element

<edit>

lpValue[0] = 2 (ONES)
lpValue[1] = 2 (MAX_UINT+1)^1s

this would be...

the number 8589934593 and is represented as...

(2 * (MAX_UINT+1)^1) + (2 * (MAX_UINT+1)^0)

[Edited by - b1gjo3 on November 16, 2008 10:45:14 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by b1gjo3
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!
You are absolutely right, it definitely needs more coments. I've been particularly slack with that.
In fact I've been particularly slack with updating my site lately. Could be something to do with the 3 solid weeks of house renovations, and training for the 12Km run which I ran yesterday, but dammit I'll find the time in the next 7 days.
I did get around to implementing a faster method of multiplication, but I still need to upload that.

Share this post


Link to post
Share on other sites
Quote:
Original post by b1gjo3
can someone tell me how exactly i can tell my compiler to show (2 * (MAX_UINT+1)^1) + (2 * (MAX_UINT+1)^0) as 8589934593.

Displaying numbers in decimal is a non-trivial problem. How would you print a normal int if there was no printf("%d\n", i) or std::cout << i ?

Maybe you should start with hexadecimal printing, that's fairly trivial.

Share this post


Link to post
Share on other sites
Quote:
Original post by b1gjo3
can someone tell me how exactly i can tell my compiler to show (2 * (MAX_UINT+1)^1) + (2 * (MAX_UINT+1)^0) as 8589934593.

thanks everyone
You may be able to reinterpret_cast your bigint to an __int64 or long long etc, but beyond that, there isn't any way to view the actual number using the debugger. For a 50 decimal digit number (for example) your only option is to write a function to convert it to a string and insert code to output that.

Share this post


Link to post
Share on other sites
Quote:
Original post by b1gjo3
how do i know if two numbers are going to overflow

There is no overflow in unsigned arithmetic, you probably mean if there's a carry? ;-)

I guess there must have been a carry if (a + b) < a, not sure if that always works though.

Share this post


Link to post
Share on other sites
Quote:
Original post by DevFred

I guess there must have been a carry if (a + b) < a, not sure if that always works though.


yes, if the "overflow" when 4,294,967,295 + 1 it goes to 0, it just wraps around. which in this case the carry is 1.

and if a = 4,294,967,295 and b = 1 then...

(a + b) yields 0 and thats less than 4,294,967,295 this definetly does not take care of multiple carrys for instance..

a = 4,294,967,295 b = 4,294,967,295

(a + b) yields 0 and the carry is 2.

Anyone have any ideas?

Share this post


Link to post
Share on other sites

This topic is 3316 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this