1

How can I solve: 2 ^ 200'000 in C
I tried several solution like:

unsigned long long int variable = 1;
int i = 0;
 for(i = 0; i < 200000; i++) {
        variable *= 2;
 }
 printf("%llu", variable);

I got the result: 0

I tired too:

variable = 1 << 200000;

and I got the same result

And too:

pow(2, 200000);

And I got the result: inf

I know result is going to be a really big number!

JMBise
  • 680
  • 4
  • 19
  • 4
    What exactly needs to be done? 2^200000 is already "solved" as it is. Do you need to provide the decimal representation or what? – COME FROM Nov 26 '12 at 09:27

6 Answers6

6

You need to use bignums. A good C library providing them is GMPlib (or Gmp).

See also this & this answers.

If it is a homework and you have to avoid external libraries, implement your own naive and inefficient bignum operations, by representing big numbers in e.g. base 1000000000 as a vector of bigdigits (in base 1000000000, i.e. of unsigned int-s less than 1000000000). But be aware that efficient algorithmics of bignum operations is a very hard subject (you could do a PhD on it).

With Common Lisp (actually SBCL on Linux), (expt 2 200000) gives a lot of digits, ending with 920038457001984739009853229094231266558782271736355646970683344733851701497060850614781367869193252027245901165192794172829673551622776804677516046034691191314830879238153864550662072000140791040750506601286234544337124194554552216233147391907942666374197047501518768776635660639895886684528408599509875931170744171632720906652165051356810584676925732763418087079259790326514074925059567293113070694950457694751972448438483214134115453746217764408771372456029214052022079066814407632012911631016804966554137474010944697979109376

Community
  • 1
  • 1
Basile Starynkevitch
  • 223,805
  • 18
  • 296
  • 547
  • the purpose is to solve that problem! http://www.soi.ch/node/515 so I need to be the more efficient as possible in the algorithm – JMBise Nov 26 '12 at 09:42
  • Then I would suggest to code with the right tools. Either an existing bignum library like GMPlib in C, or some language (like Common Lisp) with built-in bignums. Don't lose your time in coding a poor bignum implementation, unless you really have to. Don't pretend to implement a complete efficient state-of-the-art bignum library in a few months of work, you'll need years, and you'll deserve a PhD! – Basile Starynkevitch Nov 26 '12 at 09:44
  • @JMBise "we are only interested in the last 100 digits of the result", so you can calculate modulo 10^100. If using GMP isn't an option because the code would be compiled on machines without it, a homebrew library handling such numbers sufficiently efficiently isn't too hard (still very hard if you want really fast, but "fast enough" can be done). – Daniel Fischer Nov 26 '12 at 12:17
3

How would you try to solve this problem in a classroom for 20 or a hundred iterations with pencil and paper? The same approach is perfect in here too. I'd just suggest reversing the array, so one can multiply left to right and just print the final number in the correct order.

Aki Suihkonen
  • 19,144
  • 1
  • 36
  • 57
  • unfortunately I need to push this number in a variable because after I have to make a loop for with that number! – JMBise Nov 26 '12 at 09:38
  • Have you any idea of the size of that variable? The string to represent 2^200000 is 60207 bytes long including the terminating zero. You really have to treat the number as an array. The simplest, although not fastest method, is to use characters: '0'..'9'. A straight forward implementation using ascii strings will calculate the output in less than a minute. – Aki Suihkonen Nov 26 '12 at 09:53
3

If you can't use an external bignum library, then you have to implement your own.

Start by defining what your big number will look like in memory. For example, for rational numbers (which are the most awesome) a number might be represented as "a/b*(2**e)"; and you might have a variable sized array of unsigned bytes to represent a denominator, a variable length array of unsigned bytes to represent a divisor, a variable length array of unsigned bytes to represent an exponent, and some flags (e.g. denominator sign and exponent sign).

The next step is to write code to do primitive operations on pieces of your big number. For example, code to add variable length arrays together, code to shift a variable length array left/right, code to multiply 2 variable length arrays, etc.

The next step would be to implement normal operations using your primitive operations. For example (for the rational numbers), "bigNumber << 44" is actually "a/b*(2**e) << 44", and you'd just add 44 to "e".

The next step is to convert your number into your format using those normal operations you implemented. For example, you might create a big number that has the value 1 (denominator=1, divisor=1, exponent=0) and then shift it left by 200000 (denominator=1, divisor=1, exponent=0+200000).

Of course then you need some way of converting your big number into a string so it can be displayed. This requires actual division (rather than "multiply by inverse") which gets tricky.

Please note that for your purposes you only actually need a "0 bit" significand and an 18-bit exponent to store the number (in a format designed specifically for that number). If you don't need to display the resulting number in decimal, then it becomes very easy.

For example, to display it in hex you could do:

char hexDigitTable[16] = "0123456789ABCDEF";

// My big number with a 0-bit significand and 18-bit exponent!
uint32_t exponent = 20000;     

printBigNumber(uint32_t exponent) {
    int digit;

    if(exponent > 4) {
        // Note: "number / 16" is the same as "number >> 4" which is
        //       the same as "exponent - 4".
        printBigNumber(exponent - 4);
    }
    digit = 1 << (exponent & 3);
    printf("%c", hexDigitTable[digit]);
}

See how easy it is if you're lazy? :-)

Brendan
  • 35,656
  • 2
  • 39
  • 66
  • for this particular example displaying the number in hexadecimal does not need algorithm: because the result will be `8000...000` the number contains 4999 `0` (`4999 = 20000/4 -1`) – MOHAMED Nov 26 '12 at 10:36
  • unfortunately I need to push this number in a variable because after I have to make a loop for with that number! – JMBise Nov 26 '12 at 10:46
2

You don't need to "calculate" anything. Base 2 is special - it's the binary base - and powers of two, in the form of 2^x, can be generated as 1 << x (left shift). You need to set up a bitfield which can hold at least 200,000 bits, e.g. unsigned char[25000] and set the highest bit to 1. Then, you only need to interpret this bitfield as an integer.

It would be trivial to write out this number in hexadecimal - just write out each and every byte in hex. To print it out in decimal, you will probably need a bignum library :(

Ivan Voras
  • 1,895
  • 1
  • 13
  • 20
  • thanks for your answer for now can I do a loop for on this number: does for(char[25000] i = 0; (char[25000] type variable) < i; i++) works? – JMBise Nov 27 '12 at 13:19
0

You need some form of bignum library for this, no native datatype in C will be able to hold this number exactly. Be aware that it will take quite a lot of memory to represent this number.

unwind
  • 391,730
  • 64
  • 469
  • 606
0

2 ^ 200000 is far beyond any build-in data type.

You need to represent the powers in arrays to simulate multiplication by hand.

For example, you can use array { 0,1,2,3,4,5,6,7,8,9 } to store 9,876,543,210.

Secondly, you should use a divide and conquer algorithm to reduce the compute complexity.

In order to compute

a ^ b

you need to compute 

t = a ^ (b/2)

first. And then use t to compute

a ^ b = t * t * a ^ ( b % 2 )
konjac
  • 757
  • 8
  • 14