Jump to content
  • Advertisement
Sign in to follow this  
Juliean

Big integer (128 bit++)

This topic is 2539 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'm working on a little side project, which basically encodes images (32x32 with 256 colors for now) into integer values and vis versa. I've got the algorythm figured out, but my problem is the space. I need to possibly store a number as high as 256^1024 for bow, later I want to move on to higher resolutions and more colors. So I wondered if there is any standard type in c++ that allows me to store such (insane) numbers? If not, what can I do about it? Any tutorials on how to create your own (unsigned) integer type? I can't calculate the exact value of 256^1024 right now, as I lack a proprieta calculator on my iphone, but as I quess 64 bit unsigned int would be to less. Any suggestions?

Also, what about speed? Would there be any drawback of using a 128 bit or 256 bit integers? With a custom type, if written well (no assembler)?

Also, for encoding a given value into the picture, I need to perform a lot of divisons and modulo (x / 256 repeatetly until x < 0, then for every divison that happend before perform (x / (256) ) % 256). I've heard divisions are very slow, and given my algorythm I may habe to perform up to 1024 of them to decode an image. I do not necessarily need to do this in real time but it would be great if it ran as fast as possible. Any ideas?

Share this post


Link to post
Share on other sites
Advertisement
The term to Google would be "Bignum". There are libraries out there, or you could find information on how to implement your own. I recommend the former if you're just getting work done.

Share this post


Link to post
Share on other sites
/256 and %256 are easily implemented by shifts and masks, at least if you do them on integers.

just x>>8 to divide by 256 and do x&0xff to get the remainder.

Shifts and masks are about as fast as an instruction can be on most processors.
On some, you will even get them for free if you do calculations with the result. (like ARM)

Share this post


Link to post
Share on other sites
@Rip-off: thanks, I think at first I'll go with the former, however I think it could be a good learning experience to do it on my own. Quess the whole project could be a good chance to start with SIMD and SSE/2 etc instructions, couldn't it?

@Olof Hedman:

Thanks, I didn't know about that! Should be a good addition for my main project to speed some things up, too. However as I said, I want to use really, really big numbers (probably 1000 digits). Would shifts and mask work for these too, if I use existing libaries and/or build my own, and if yes, would they be as fast (no floating point)?

Share this post


Link to post
Share on other sites
Hidden

a number as high as 256^1024 for bow


256 * 256 * 256 * ... * 256 (1024 times)?

256 = 2^8 ==> 2^8^1024 = 2^8192. A gigabyte is 2^9, a petabyte is 2^15.

To compute value of 2^8192, you would need vastly more memory than the combined digital storage in existence.

Share this post


Link to post
May I ask what you're trying to achieve? I get the idea you're trying to save space by packing the image in a large integer, but that won't work. You'll need an integer with just as many bits to store the 'compressed' image as when you would store it as byte array. Look up the pigeonhole principle.

Share this post


Link to post
Share on other sites
32*32*8bits = 1024 bits.

The original image is already encoded and it's already a 1024 bit integer. No need to calculate anything.

For example:struct Image {
int w, h;
char pixels[w*h];
}
Pixels are your integer. It's just not represented as such, but using a bignum would not change that, it would probably use ints instead of char, but principle remains the same.

If trying to encrypt such an image, just do character-wise encoding of the pixels.

Some operations are also trivial. For example:
- Image / (i * 256) = pixels in range 0 .. 255-i
- Image mod (i * 256) = pixels[255-i]

Share this post


Link to post
Share on other sites
To both of you: It's not exactly what I want to achieve. It's about a crazy idea I had about a random image generator. Basically in an image of any given size, like 32x32, when choosing a random number (of my envoded image) and by performing a various number of operations (like loop all colors on pixel 24.16), and saving or outputting these images, you would basically, after a large amount of time, get some pictures that actually make some sense. For 256 colors, You have 256^1024 possible combinatons.

I know it may sound stupid. Whe I first got the idea I made a mistake, thinking that evenfor 640*480 with 32bit colors there would be much less combinations (its 16mio^640*480, not 16mio*640*480, appearently). I got stuck with this idea and, even if this can't rwally be used as any serious project for a portfolio, I still at least want to try it. If you ask why I want to use an int representing the image: Just assigning random numbers to the single pixels prove useless as it created just messy images that all looked the same. So, I'm probably better of with a random generated number with 10k digits.. Oh, I know 256^1024 is a huge amount of possible images.. But as I work on this project, I can try out different programming techniques I don't want to apply to my game project without testing first..So, I hope you get the idea^^

Share this post


Link to post
Share on other sites

Just assigning random numbers to the single pixels prove useless as it created just messy images that all looked the same. So, I'm probably better of with a random generated number with 10k digits.


Why would you think a random number of 10k digits would be any different to an array of pixels with randomly assigned values?

Share this post


Link to post
Share on other sites

To both of you: It's not exactly what I want to achieve. It's about a crazy idea I had about a random image generator. Basically in an image of any given size, like 32x32, when choosing a random number (of my envoded image) and by performing a various number of operations (like loop all colors on pixel 24.16), and saving or outputting these images, you would basically, after a large amount of time, get some pictures that actually make some sense. For 256 colors, You have 256^1024 possible combinatons.

I am confused, why do you need to encode a bunch of tiny numbers into one huge number to do this?

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!