Original Post
🔒 Locked
Making a 128-bit integer?
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 win32Type "help", "copyright", "credits" or "license" for more information.>>>>>> 2 ** 128340282366920938463463374607431768211456LQuote:
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).
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.
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,
If you would like to share emails, or if you want to post it on something like rapid-share just pm me.
Val,
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
"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
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.
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.
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..
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) 52+2 44+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.
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]
Quote: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:
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,
Useful classes
Just bear in mind that it is still in an unfinished state. Very usable, but still a work in progress.
Quote:
Original post by iMalc Quote: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:
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,
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]
Topic Locked
This topic has been locked by a moderator. New replies are not allowed.
Sign in to reply to this topic.
Advertisement