2^1000000

2pow.c

enum {
    BASE = 1000000000,  // nine decimals per limb
    NUMCAP = 1<<16,     // capacity just over a half million decimals
};

typedef struct {
    int *digits;
    int  len;
} num;

static num newnum(int **arena)
{
    num r = {0};
    r.digits = *arena;
    *arena += NUMCAP;
    return r;
}

static num set(num dst, long long x)
{
    for (dst.len = 0; x; dst.len++, x/=BASE) {
        dst.digits[dst.len] = (int)(x % BASE);
    }
    return dst;
}

static num copy(num dst, num src)
{
    for (int i = 0; i < src.len; i++) {
        dst.digits[i] = src.digits[i];
    }
    dst.len = src.len;
    return dst;
}

static num multiply(num dst, num a, num b)
{
    dst.len = a.len + b.len;
    for (int i = 0; i < dst.len; i++) {
        dst.digits[i] = 0;
    }

    for (int j = 0; j < a.len; j++) {
        int mc=0, ac=0, i=0;
        for (; i < b.len; i++) {
            long long mr = (long long)a.digits[j]*b.digits[i] + mc;
            mc = (int)(mr / BASE);
            int ar = dst.digits[i+j] + (int)(mr%BASE) + ac;
            ac = ar / BASE;
            dst.digits[i+j] = (int)(ar % BASE);
        }
        for (ac += mc; ac; i++) {
            int ar = dst.digits[i+j] + ac;
            ac = ar / BASE;
            dst.digits[i+j] = (int)(ar % BASE);
        }
    }

    for (; dst.len && !dst.digits[dst.len-1]; dst.len--) {};
    return dst;
}

static num power(num dst, num a, long long pow, int *arena)
{
    num tmp = newnum(&arena);
    if (pow == 0) {
        dst = set(dst, 1);
    } else if (pow == 1) {
        dst = copy(dst, a);
    } else if (pow%2 == 0) {
        tmp = multiply(tmp, a, a);
        dst = power(dst, tmp, pow/2, arena);
    } else {
        dst = multiply(dst, a, a);
        tmp = power(tmp, dst, pow/2, arena);
        dst = multiply(dst, a, tmp);
    }
    return dst;
}


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

int main(void)
{
    int *arena = malloc(1<<26);
    num two = set(newnum(&arena), 2);
    num dst = newnum(&arena);
    dst = power(dst, two, 1000000, arena);
    for (int i = dst.len-1; i >= 0; i--) {
        printf(i==dst.len-1?"%d":"%09d", dst.digits[i]);
    }
    putchar('\n');
}