• Advertisement
Sign in to follow this  

Making a 128-bit integer?

This topic is 3990 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, I know this is probably a noobish question, and probably is not possible do to the fact that processors are only 32/64 bit. But would it be possible to create a new integer that uses 128 bit, or even more if needed. Sorry if I make my self sound stupid. ^^;;

Share this post


Link to post
Share on other sites
Advertisement
Use a bignum library or a language that directly supports bignum arithmetic:


Python 2.4.3 (#69, Mar 29 2006, 17:35:34) [MSC v.1310 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>>
>>> 2 ** 128
340282366920938463463374607431768211456L

Share this post


Link to post
Share on other sites
Quote:
Original post by Valeranth
Hi, I know this is probably a noobish question, and probably is not possible do to the fact that processors are only 32/64 bit. But would it be possible to create a new integer that uses 128 bit, or even more if needed.
Sorry if I make my self sound stupid. ^^;;


The MVS long long type working on my 32-bit processor proves you wrong :)

Other than that, this covers most of it:
http://en.wikipedia.org/wiki/Bignum

Generally, you define a type that is a composite of available types.

Your 128 bit would be represented with 4 32 bit ints. Then it's just a matter of implementing operations on those types.

If you know the size in advance it's possible to have these operations implemented optimally with minimal overhead (still slower than build-in types).




Share this post


Link to post
Share on other sites
Still having problems figuring out how to do this. I get how its done, but I do not know how to make it. You should know I'm fairly new to C++. A example, or a link to a example would be greatly appreciated; Or a link to anything describing more then just the logic behind it.

Share this post


Link to post
Share on other sites
I once found this which was what I wanted, although it had a few bugs and things that needed optimising etc. I can send you my own updated version of this that also handles signed bigints etc and has other added or improved functionality, if you like.

Share this post


Link to post
Share on other sites
With a quick look threw, that seems to be exactly what I need. If you would be willing to give em your version, I would be much obliged. My email isn't really that hard to figure out (Ill give you a hint:Gmail) but not sure if I am allowed to post it here, so I wont.
If you would like to share emails, or if you want to post it on something like rapid-share just pm me.
Val,

Share this post


Link to post
Share on other sites
The Lead programmer from Chaos Studios was browsing around GameDev, and found this article. He took a look at it, and saw that it was similar to what he did. He once made a un-overflowing decimal variable, but he got too lazy to compleat it. This is what he has to say just taking a quick peak at what you wanted to do:

"It's not quite that hard. Before I made an un-overflowable decimal variable. Basically, you just need to check to see the status on the variable, if it's close to it's overflow number, you re-allocate 1 more long or double, and then start filling that next variable." - Marc

Share this post


Link to post
Share on other sites
Quote:
Original post by iamtehpwn
The Lead programmer from Chaos Studios was browsing around GameDev, and found this article. He took a look at it, and saw that it was similar to what he did. He once made a un-overflowing decimal variable, but he got too lazy to compleat it. This is what he has to say just taking a quick peak at what you wanted to do:

"It's not quite that hard. Before I made an un-overflowable decimal variable. Basically, you just need to check to see the status on the variable, if it's close to it's overflow number, you re-allocate 1 more long or double, and then start filling that next variable." - Marc


Who is this lead programmer?
Also like Ive said, I know the logic behind it; I just don't know how to make it work. I remember back before 2000 I had a class with a 'Infinite' variable, that would basically do do what Marc said; It would start out as 1 byte, then more up and up the more you put in it. But sadly I have sense lost it.

Share this post


Link to post
Share on other sites
This is actually more fitted to assembly than C++ or C. Not only in terms of performance but also in terms of clarity. Things like carry I guess.. I remember we implemented the same thing in our microprocessor session. Well now I don't have my book neither can I recreate what was done in the lecture completely, but I think it was important to note.

Share this post


Link to post
Share on other sites
Quote:
Original post by arithma
This is actually more fitted to assembly than C++ or C. Not only in terms of performance but also in terms of clarity. Things like carry I guess.. I remember we implemented the same thing in our microprocessor session. Well now I don't have my book neither can I recreate what was done in the lecture completely, but I think it was important to note.


Well I just joined, so I did not get to attend this session. (forgive me if it is simply a forum post or something, but seeing as you said you don't have your book and you cant recreate what was done, I'm assuming that this was not the case.) Also I know nothing at all about ASM.. so I'm even worse off there..

Share this post


Link to post
Share on other sites
Quote:
Original post by Valeranth
Quote:
Original post by arithma
This is actually more fitted to assembly than C++ or C. Not only in terms of performance but also in terms of clarity. Things like carry I guess.. I remember we implemented the same thing in our microprocessor session. Well now I don't have my book neither can I recreate what was done in the lecture completely, but I think it was important to note.


Well I just joined, so I did not get to attend this session. (forgive me if it is simply a forum post or something, but seeing as you said you don't have your book and you cant recreate what was done, I'm assuming that this was not the case.) Also I know nothing at all about ASM.. so I'm even worse off there..


How would you add up 2 4-digit numbers, say 4219 and 7235?


4 2 1 9
+ 7 2 3 5
--------------------------
9+5 4 (carry 1)
1+3(+1) 5
2+2 4
4+7 1 (carry 1)

= 1 4 5 4

The actual result in this case is 11454, but we only have 4 digit numbers, so we overflow.

Now, let's replace our digits with ints. So each of digits (0-9) will be (0 - 2^32), and put it in code.


struct bigint {
unsigned int digits[N_DIGITS];
bool overflow;
};




How do we add up two numbers like before now? We use the same process.


enum { N_DIGITS = 200 };

int carry_add( unsigned int a, unsigned int b)
{
// Addition of two numbers will overflow only if
// both have 32nd bit set.
return ( a >> 31 ) & ( b >> 31 );
}
bigint add( bigint &a, bigint &b)
{
bool carry = 0;
bigint result;
// add two digits, keep track of carry
for (int i = 0; i < N_DIGITS; i++) {
result.digits = a.digits + b.digits + carry;
carry = carry_add(a.digits, b.digits);
}
// if carry is set, we can't do much about it,
// since we ran out of place to store it, so we just
// mark the overflow
result.overflow = (carry != 0);
return result;
}




Hopefully I got this right, didn't test it.

If you would want to use 128 bit numbers, you would set the N_DIGITS to 4, since each "digit" in our case is an int, represented with 32 bytes.

The question that still remains is how to render such a number. This is just binary representation, so you still need a way to render it in decimal, and it cannot be done by simply rendering all individual digits.

Other operations are defined similarly.

The value of carry for addition will always be 0 or 1. Multiplication of 2 n-digit numbers can overflow by up to n digits. Multiplying 2 3-digit numbers (999x999 = 998001, or 6 digits).

If you now wanted to make two bigints of infinite length, you would merely need to implement a way to resize the digits array as needed.

This code is not even remotely intended for real use, it's merely demonstration of the concept.

Share this post


Link to post
Share on other sites
Quote:
Original post by Valeranth
Quote:
Original post by iamtehpwn
The Lead programmer from Chaos Studios was browsing around GameDev, and found this article. He took a look at it, and saw that it was similar to what he did. He once made a un-overflowing decimal variable, but he got too lazy to compleat it. This is what he has to say just taking a quick peak at what you wanted to do:

"It's not quite that hard. Before I made an un-overflowable decimal variable. Basically, you just need to check to see the status on the variable, if it's close to it's overflow number, you re-allocate 1 more long or double, and then start filling that next variable." - Marc


Who is this lead programmer?
Also like Ive said, I know the logic behind it; I just don't know how to make it work. I remember back before 2000 I had a class with a 'Infinite' variable, that would basically do do what Marc said; It would start out as 1 byte, then more up and up the more you put in it. But sadly I have sense lost it.


I am Marc, indeed. You're quite right, it could start out as 1 byte. But even then you're limiting it in both capacity and precision. I've heard that it's easier and simpler (with many less errors and complexities) to do it with ASM, but I prefer C++ anyway.

So, if you follow the semi-psuedo-code

class CDecimal
{
private:
double *lpValue;
unsigned long count;
public:
CDecimal();
~CDecimal();
CDecimal &operator=(double);
CDecimal &operator+=(double);
//You get the idea
};

CDecimal::CDecimal()
{
lpValue = new double;
count = 0;
}
CDecimal::~CDecimal()
{
if(count > 0)
{
delete[] lpValue;
}
else
{
delete lpValue;
}
}

CDecimal::&operator=(double dVal)
{
lpValue[count] = dVal;
return *this;
}
CDecimal::&operator+=(double dVal)
{
if(this->lpValue[count] > 0xffffff)
{
double *nDouble = new double[++count];
for(int i = 0; i <= (count - 1); ++i)
{
nDouble = lpValue;
}
delete [] lpValue;
lpValue = new double[count];
for(int i = 0; i <= count; ++i)
{
lpValue = nDouble;
}
delete [] nDouble;
lpValue[count] = dVal;
}
else
{
lpValue[count] = dVal;
}
return *this;
}


Well, little more than psuedo code, but still definately not tested. It has been a while since I made that variable, I really should rewrite it, I cannot find the code I once wrote.

(And before anyone mentions it, yes. The prior code above is quite sloppy. I apologise in advance)

[Edited by - Demonic_Marek on March 24, 2007 11:56:58 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Valeranth
With a quick look threw, that seems to be exactly what I need. If you would be willing to give em your version, I would be much obliged. My email isn't really that hard to figure out (Ill give you a hint:Gmail) but not sure if I am allowed to post it here, so I wont.
If you would like to share emails, or if you want to post it on something like rapid-share just pm me.
Val,
You're in luck, I've just started uploading some of the web content I have been writing. Not much at all yet, but here is a tiny page that contains the file I was telling you about:

Useful classes

Just bear in mind that it is still in an unfinished state. Very usable, but still a work in progress.

Share this post


Link to post
Share on other sites
Quote:
Original post by iMalc
Quote:
Original post by Valeranth
With a quick look threw, that seems to be exactly what I need. If you would be willing to give em your version, I would be much obliged. My email isn't really that hard to figure out (Ill give you a hint:Gmail) but not sure if I am allowed to post it here, so I wont.
If you would like to share emails, or if you want to post it on something like rapid-share just pm me.
Val,
You're in luck, I've just started uploading some of the web content I have been writing. Not much at all yet, but here is a tiny page that contains the file I was telling you about:

Useful classes

Just bear in mind that it is still in an unfinished state. Very usable, but still a work in progress.


Great! Thanks a lot, always love not having to do work ^^.

Edit: I see that you can define big-end. in bigint.h, which does bring up some good portability questions. My main one right now is; Would it be possible to do some check around the define to test which type they are using?

Edit2: Just got around adding it, 49 errors using eclipse (cygwin) and Dev-C++ (G++). So.. missing a file? Just using bigint.h

[Edited by - Valeranth on March 25, 2007 12:21:40 PM]

Share this post


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

  • Advertisement