How to calculate 2 to the power 10000000

Question

How to calclute 2 to the power 10000000 without crashing the compiler. What shoud be data type for extramily big integer in c/c++.

Answer 1

For the very specific value 2 raised to the power of 1000 a double is sufficient.

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

int main(int argc, const char *argv[]) {
    printf("%f\n", pow(2., 1000));
    return 0;
}

In general however you will need to implement an arbitrary precision multiplication algorithm to compute numbers that big (or use a library that provides that).

C++ has no predefined standard functions for this kind of computation.

If you want to implement your own version as an exercise then my suggestion is to use numbers in base 10000. They're small enough that single-digit multiplication won't overflow and it's very easy and fast to translate the result into decimal at the end because you can just map base-10000 digits to decimal without having to implement division an modulo too.

Also to compute such a big power (10,000,000) you will need to implement power by squaring, i.e.

BigNum pow(BigNum a, int b) {
    if (b == 0) {
        return 1;
    } else if (b & 1) {
        return a*pow(a, b-1);
    } else {
        BigNum x = pow(a, b/2);
        return x*x;
    }
}

this will allow to compute pow(a, b) with O(log(b)) instead of O(b) multiplications.

Answer 2

Store the digits in an int array where each location of the array denotes one digit. Then multiply them repetitively. That way you will get the answer with out crashing the compiler.

Well you need 302 locations for that. And the multiplication is simply the one that we do in grade classes. You have implement it in coding.

Little bit of code

int d[400];

for(int i=0;i<399;i++)
   d[i]=0;

d[0]=1;

int carry=0;
int temp=0;
for(int j=0;j<=999;j++)
{
   carry=0;
   temp=0;
   for(int i=0;i<=399;i++)
   {
      temp=d[i]*2+carry;
      d[i]= temp%10;
      carry = temp/10;
   }
}
print d[0..399] in reverse order trimming zeroes.

Answer 3

Unlike Python/Java, C++ does not handle such big number by itself nor does it have a dedicated data type for it. You need to use an array to store the numbers. You do not have a data type for the problem. These kind of questions are common in competitive programming sites. Here is a detailed tutorial.

Large Number in C/C++

You can also learn about bit manipulation. They are handy when you multiply by 2.

Please read this before using pow(2., 1000) as mentioned in another answer. c++ pow(2,1000) is normaly to big for double, but it's working. why?

As @6502 cleraly puts it in his answer, it can be used for this specific case of 2^1000. I missed that, be careful about that in case you are going to use this in a competitive programming site.