#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/time.h>
#include <time.h>

int main(int argc, char * argv[])
{
        register int i;
        register long long n;
        int k, l, x, size, page;
	long long int round;
        volatile  int **mem;
	struct timeval tv_debut;
	struct timeval tv_fin;
	long long int duree;
        size  = atoi(argv[1]);
	round = 1ULL << atoi(argv[2]);
        page = getpagesize( );
	srandom( time(NULL ) );
	mem = (volatile int**) calloc( size , sizeof(int*));
        for( k = 0; k < size; k++){
       		mem[k] = mmap(NULL, page, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);
		if ( mem[k] == MAP_FAILED) {
			perror("mmap");
			exit(1);
		}
	}
        for( k = 0; k < size ; k++)
           mem[k][0] = -1;
        // randomization  
        x = 0;     
        for( k = 0; k <  size-1; k++) {
                l = random() % size;
		while ( mem[l][0] >= 0 || l == x)
       	            l = (l+1) % size;
		mem[x][0] = l;
		x = l;
                }

	gettimeofday(& tv_debut, NULL);
       
        for (n = 0; n < round; n++) {
             i = 0;
             do
               i = mem[i][0];
             while ( i >=0 );
             }
	gettimeofday(& tv_fin, NULL);
	duree  = tv_fin.tv_sec - tv_debut.tv_sec;
	duree *= 1000000;
	duree += tv_fin.tv_usec - tv_debut.tv_usec;
        duree /= size;      
	fprintf(stdout, " %3lld.%02lld\n", duree/100, duree%100);
       
	return 0;
}