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

long long TimeValue=0;

unsigned long long time_RDTSC(){ 
  union ticks{ 
  	unsigned long long tx;
    struct dblword { long tl,th; } dw; // little endian
  } t;
  asm("rdtsc\n": "=a"(t.dw.tl),"=d"(t.dw.th));
  return t.tx;
} // for x86 only!

void time_start() { TimeValue=time_RDTSC(); }

long long time_stop() { return time_RDTSC()-TimeValue; }

void swap(int *a, int *b){
  	int c = *a;
	*a = *b;
	*b = c;
}
void Snuffle(int array[], int n){
	int i;
	for (i = 0; i < n; i++)
		swap(array + i, array + (rand() % n)); 
}

void ForwardInit(int array[], int n){
 	int i;
	array[n-1] = 0;
	for(i = 0; i < n -1; i++)
		array[i]=i+1;
}

void BackwardInit(int array[], int n){
	int i;
  	array[0] = n-1;
	for (i = 0; i < n; i++)
		array[i+1] = i; 
}

void RandomInit(int array[],  int n){
	int i;
	int *TempArray;
	TempArray = (int *)calloc(n,  sizeof(int));
	ForwardInit(TempArray, n);
	Snuffle(TempArray, n);
	for(i = 0; i < n; i++)
		array[TempArray[i]] = TempArray[i+1];
	array[TempArray[n-1]] = TempArray[0];
	free(TempArray);
}

long long CalculateSum(int array[], int n){
 	long long sum = 0;
	long long x = array[0];
	int count = 0;
	while(count < n){
	  sum+=array[x];
	  x = array[x];
	  if (x==array[0])
		count++;
	}
	return sum;
}

int main(){
  	int cycles = 10; 
	int n=10;
	long long sum;
	long long time;
	int i;
	int *array;
	for(n = 1024/sizeof(int); n <1024*1024/(sizeof(int)); n+=1024/sizeof(int)){
		array = (int *)calloc(n, sizeof(int));
	
		CalculateSum(array,  1);

		ForwardInit(array, n);
		time_start();
		sum = CalculateSum(array, cycles);
		time = time_stop();
		printf("%lld ",  time/(n*sizeof(int)));
		printf("%lld ", sum);

		BackwardInit(array, n);
		time_start();
		sum = CalculateSum(array, cycles);
		time = time_stop();
		printf("%lld ",  time/(n*sizeof(int)));
		printf("%lld ", sum);

		RandomInit(array, n);
		time_start();
		sum = CalculateSum(array, cycles);
		time = time_stop();
		printf("%d %lld ",  n, time/(n*sizeof(int)));
		printf("%lld\n", sum);

		free(array);
	}
	for(;n < 4*1024*1024/(sizeof(int)); n+=256*1024/sizeof(int)){
		array = (int *)calloc(n, sizeof(int));
	
		CalculateSum(array,  1);

		ForwardInit(array, n);
		time_start();
		sum = CalculateSum(array, cycles);
		time = time_stop();
		printf("%lld ",  time/(n*sizeof(int)));
		printf("%lld ", sum);

		BackwardInit(array, n);
		time_start();
		sum = CalculateSum(array, cycles);
		time = time_stop();
		printf("%lld ",  time/(n*sizeof(int)));
		printf("%lld ", sum);

		RandomInit(array, n);
		time_start();
		sum = CalculateSum(array, cycles);
		time = time_stop();
		printf("%d %lld ",  n, time/(n*sizeof(int)));
		printf("%lld\n", sum);

		free(array);
	}
	return 0;
}