/* 
 * File:   main.c
 * Author: xxxx
 *
 * Created on 2013/02/12, 12:09
 */
#include <stdio.h>
#include <stdlib.h>
#define MAXDECIMAL      (24*1000000)
#define MAXBINARY       (60000000)
#define TABLEWIDTH      (1000000)

void makemultable();
int* makelongdecimal();
void calc(int);
void decans(void);
void clearmemory(void);
void dispans(void);
void dispans2(int);

char *b;
int *ans;
int blength = 0, anslength = 1;
int multable[TABLEWIDTH][2];// 2倍しかしない
int main(int argc, char** argv) {
    printf("start makemultable\n");
    makemultable();
    printf("start makelongdecimal(ans)\n");
    ans = makelongdecimal();
    printf("start calc(578851)\n");
    calc(578851);
    printf("start decans\n");
    decans();
    printf("start dispans\n");
    dispans();
    printf("start clearmemory\n");
    clearmemory();
    return (EXIT_SUCCESS);
}
void makemultable(void){
    int j, val;
        for(j = 0; j < TABLEWIDTH; j++){
            val = 2 * j;
            if(val > TABLEWIDTH){
                val -= TABLEWIDTH;
                multable[j][1] = 1;
            } else
                multable[j][1] = 0;
            multable[j][0] = val;
        }
}
int* makelongdecimal(){
    int *ptr;
    ptr = (int*)calloc(MAXDECIMAL / 6, sizeof(int));
    if(ptr == NULL){
        fprintf(stderr, "Can't allocate memory!\n");
        exit(-1);
    }
    return ptr;
}
void calc(int val){
    int i, j, flg = 0, *base, tmp;
    *ans = 1;
    for(j = 0; j < val; j++){
        //printf("Loop %d: ", j); dispans();
        // ansを2倍する
        base = ans;
        for(i = 0; i < anslength; i++) {
                tmp = multable[*base][0];  // *base = ans * 2; (6桁のみ)
                if(flg == 1)
                        ++tmp;
                flg   = multable[*base][1];
                if(flg == 1 && i == anslength - 1) //最上位桁があふれしたらansを一桁増やす
                        ++anslength;
                *base = tmp;
                ++base;
        }
    }
}
void decans(void){
    int i, *base = ans;
    for(i = 0; i < anslength; i++){
            if(*base == 0)
                *base = 999999;
            else{
                *base -= 1;
                break;
            }
            ++base;
    }
}
void dispans(){
    int i, k;
    for(i = anslength - 1; i >= 0; --i){
        k = *(ans + i);
        if(k > 9999){
            dispans2(k / 10000);
            k %= 10000;
        }else
            dispans2(0);
        if(k > 99){
            dispans2(k / 100);
            k %= 100;
        }else
            dispans2(0);
        dispans2(k);
    }
    printf(" length:%d \n", anslength);
}
void dispans2(int val){
    if(val > 9){
        printf("%d", val / 10);
        val %= 10;
    }else
        printf("0");
    printf("%d", val);
}
void clearmemory(void){
    free(b);
    free(ans);
}