Extremely large integers in C++

[Enterprise D]

Hi!

Does anyone know if it would be possible (and how) to use extremely large integers in a C++ program (such as 20 million digits)?

Any tips would be aprreciated!

[Olysold]

According to this: http://msdn.microsoft.com/en-us/library/s3f49ktz(v=vs.80).aspx

Int can handle way more than that. But of course there are other types that can handle a lot more.

[Enterprise D]

Hi, thanks for your answer.

What I mean is numbers with 20 million digits, not the number 20,000,000. (So, for example, 10^20,000,000).

int can only handle numbers around 2*10^9.

[Olysold]

I shouldn't post after just waking up. Man I have troubles even comprehending such a value. Maybe someone can shed some light on this. The only thing I found is:

http://www.programmersheaven.com/mb/CandCPP/240492/240492/10-million-digits/

Didn't read it through, but there should be some answers there.

[DeXecipher]

in theory it is possible, just use a character string to represent the integer. but it's arbitrary to be able to use such a number on a normal system.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef long big_int;//this wont work for 20million DIGITS...but
//hypothetically you could convert a character string into a large number

int main()
{
//8 bits is one byte under most systems
//so sizeof(big_int) = xbytes
//x bytes * 8 = number_of_bits
//therefore max number = 2^number_of_bits-1
//size = max_number+1;//...

const big_int SIZE = (big_int)ceil(powf(2, sizeof(big_int)*8));// replace with 20000000;
unsigned char* pDigits = 0;

pDigits = new unsigned char[SIZE];

//check if 20,000,000 bytes is allocated
if(!pDigits)
{
 //throw assertion, if the following is false, the program will abort() or exit()
 assert( pDigits && "Too Large OR Out of Memory, Failed to Allocate pDigitString" );
}

//remember that each element of pDigitString has a weighted (positional) significance.

big_int number = 0; //hypothetical big number
//this only works if each cell is between 0 and 255 (256 digits), limit of unsigned char datatype

//i'm not 100 percent sure this code is right, but I am sure it is possible in theory
//to store a large number
for(int pos = 0; pos < SIZE; pos++)
{
//slow as weight gets larget and larger
   number = number + (big_int)pDigits[pos]*(big_int)floor(powf(2,pos));
}

//if this is ever reached
for(big_int pos = 0; pos < SIZE; pos++)
{
//slow as weight gets larger and larger
   printf("number[%d] = %c\n", pos, pDigits[pos] ); 
}

delete [] pDigits;
pDigits = 0;

return 0;
}

[DeXecipher]

If someone knows a good solution and (fast enough), I am also interested. :) It could be useful one day.

[modoran]

There are dedicated libraries for this kind of thing, like GMP.
http://gmplib.org/

You have unlimited number of digits :)

[D80DSL3A]

@DeXipher
A pro library like the one linked to above is best, however if you're asking about "rolling your own" then see this old lounge thread in which Douas hosted a bigNum challenge. There were 5 entrants so there are 5 rather unique solutions to examine there.
http://www.cplusplus.com/forum/lounge/32041/