Collatz 1

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

typedef unsigned long long bignumber;
typedef unsigned short gtype;

void init_leap_table(int bits, bignumber *atable, bignumber *btable, gtype *gtable)
{
    int i;

    for (i=0; i< (1<<bits); i++)
    {
	int a = (1<<bits);
	int b = i;
	int g = 0;
	// transform a*m+b (m>0) as many times as bossible

	while((a&1)==0)
	{
	    if (b&1) //odd
	    {
		a = 3*a;
		b = 3*b + 1;
	    }
	    else
	    {
		a /= 2;
		b /= 2;
	    }
	    g++;
	}
	atable[i] = a;
	btable[i] = b;
	gtable[i] = g;
    }
}

int  main(int argc, char **argv)
{
    bignumber n = atoll(argv[1]);
    bignumber k, i, n2;
    gtype gmax, gmax_last;
    bignumber kmax;

    #define LBITS 10
    #define LMASK ((1<<LBITS)-1)
    bignumber atab[1<<LBITS];
    bignumber btab[1<<LBITS];
    gtype gtab[1<<LBITS];

    #define H_BUFSIZE (1<<16)
    bignumber x_log[H_BUFSIZE];
    gtype g_log[H_BUFSIZE];

    gtype *gtable;
    bignumber gtable_size = n;

    if (argc==3) gtable_size = (bignumber)(n * atof(argv[2]));

    #define GTABLE_MAX 60000000
    if (gtable_size > GTABLE_MAX) gtable_size = GTABLE_MAX;
    gtable = (gtype *)malloc(gtable_size * sizeof(gtype));
    if (gtable == NULL)
    {
	printf("Not enough memory\n");
	exit(1);
    }
    printf("#Buffer size ratio %f\n",1.0*gtable_size/n);

    gtable[0] = 1;
    for(i=1;i<gtable_size;i++)
	gtable[i] = 0;

    gmax = 1;
    kmax = 1;

    init_leap_table(LBITS, atab,btab,gtab);

    for(k=n/2;k<=n;k++)
    {
	int g=0;
	int n_log = 0;
	bignumber x = k;

	// Hot Spot
        while(1)
	{
	    if (x <= gtable_size)
	    {
		if (gtable[x-1] != 0) break;
	        x_log[n_log] = x;
	        g_log[n_log] = g;
	        n_log++;
                if (x & 1) x = x*3+1;
	        else x >>=1;
	        g++;
	    }
	    else
	    {
		bignumber m = x>>LBITS;
		int c = x & LMASK;
		x = m*atab[c]+btab[c];
		g += gtab[c];
	    }
	}

	g += gtable[x-1];

	for(i=0;i<n_log;i++)
	{
	    int g0 = g_log[i];
	    x = x_log[i];
	    gtable[x-1] = g-g0;
	}

	if (g>gmax)
	{
	    gmax_last = gmax;
	    gmax = g;
	    kmax = k;
	}

    }//i
    printf("g(%lld) = %d\n", kmax, gmax);
}