How can I calculate 2^n for large n?

Question

I am trying to write a program that takes a number, n, as input, and outputs the result of 2 to the power of n. The problem is, n can be very large (up to 100,000). Essentially, I am trying to calculate pow(2, n); for very large numbers.

I think the way to do this is to store the digits in an array, since there is no built-in numeric type that can hold values that are this large.

The digits are in decimal format (base 10).

I am using C, not C++, so I cannot use STL vectors and other C++ containers. I also cannot use external libraries, like GMP. I need to implement the algorithm manually in pure C.

Answer 1

The problem is not to compute 2 to a high power, but to convert this number to a decimal representation:

• Let's represent large numbers with arrays of unsigned 32-bit integers.
• Computing 2ⁿ is as easy as setting a single bit.
• Converting to binary can be performed by repeatedly dividing this number by 1000000000, producing 9 digits at a time.

Here is a simple but fast implementation:

#include <stdint.h>
#include <stdio.h>

void print_2_pow_n(int n) {
    int i, j, blen = n / 32 + 1, dlen = n / 29 + 1;
    uint32_t bin[blen], dec[dlen];
    uint64_t num;

    for (i = 0; i < blen; i++)
        bin[i] = 0;
    bin[n / 32] = (uint32_t)1 << (n % 32);

    for (j = 0; blen > 0; ) {
        for (num = 0, i = blen; i-- > 0;) {
            num = (num << 32) | bin[i];
            bin[i] = num / 1000000000;
            num = num % 1000000000;
        }
        dec[j++] = (uint32_t)num;
        while (blen > 0 && bin[blen - 1] == 0)
            blen--;
    }
    printf("2^%d = %u", n, dec[--j]);
    while (j-- > 0)
        printf("%09u", dec[j]);
    printf("\n");
}

int main() {
    int i;
    for (i = 0; i <= 100; i += 5)
        print_2_pow_n(i);
    print_2_pow_n(1000);
    print_2_pow_n(10000);
    print_2_pow_n(100000);
    return 0;
}

Output:

2^0 = 1
2^5 = 32
2^10 = 1024
2^15 = 32768
2^20 = 1048576
2^25 = 33554432
2^30 = 1073741824
2^35 = 34359738368
2^40 = 1099511627776
2^45 = 35184372088832
2^50 = 1125899906842624
2^55 = 36028797018963968
2^60 = 1152921504606846976
2^65 = 36893488147419103232
2^70 = 1180591620717411303424
2^75 = 37778931862957161709568
2^80 = 1208925819614629174706176
2^85 = 38685626227668133590597632
2^90 = 1237940039285380274899124224
2^95 = 39614081257132168796771975168
2^100 = 1267650600228229401496703205376
2^1000 = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
2^10000 = 1995063116880758384883742<...>91511681774304792596709376
2^100000 = 9990020930143845079440327<...>97025155304734389883109376

2¹⁰⁰⁰⁰⁰ has 30103 digits, which is exactly floor(100000 * log10(2)). It executes in 33 milliseconds on my old laptop.