Orginal: http://ailab.kangwon.ac.kr/?module=file&act=procFileDownload&file_srl=22...

/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */ 
/* rotate.c -- time algorithms for rotating a vector

      Input lines:
             algnum numtests n rotdist

             algnum:

              1: reversal algorithm

              2: juggling algorithm

              22:  juggling algorithm with mod rather than if

              3: gcd algorithm

              4: slide (don't rotate): baseline alg for timing

      To test the algorithms, recompile and change main to call testrot

*/ 

#include <stdio.h>

#include <stdlib.h>

#include <time.h> 

#define MAXN 10000000 

int x[MAXN];

int rotdist, n; 

/* Alg 1: Rotate by reversal */ 

void reverse(int i, int j)

{ int t;

      while (i < j) {

             t = x[i]; x[i] = x[j]; x[j] = t;

             i++;

             j--;

      }

} 

void revrot(int rotdist, int n)

{ reverse(0, rotdist-1);

      reverse(rotdist, n-1);

      reverse(0, n-1);

} 

/* Alg 2: Juggling (dolphin) rotation */ 

int gcd(int i, int j)

{ int t;

      while (i != 0) {

             if (j >= i)

                   j -= i;

             else {

                   t = i; i = j; j = t;

             }

      }

      return j;

} 

void jugglerot(int rotdist, int n)

{ int cycles, i, j, k, t;

      cycles = gcd(rotdist, n);

      for (i = 0; i < cycles; i++) {

             /* move i-th values of blocks */

             t = x[i];

             j = i;

             for (;;) {

                   k = j + rotdist;

                   if (k >= n)

                         k -= n;

                   if (k == i)

                         break;

                   x[j] = x[k];

                   j = k;

             }

             x[j] = t;

      }

} 

void jugglerot2(int rotdist, int n)

{ int cycles, i, j, k, t;

      cycles = gcd(rotdist, n);

      for (i = 0; i < cycles; i++) {

             /* move i-th values of blocks */

             t = x[i];

             j = i;

             for (;;) {

          /* Replace with mod below

                   k = j + rotdist;

                   if (k >= n)

                         k -= n;

           */

            k = (j + rotdist) % n;

                   if (k == i)

                         break;

                   x[j] = x[k];

                   j = k;

             }

             x[j] = t;

      }

} 

/* Alg 3: Recursive rotate (using gcd structure) */ 

void swap(int i, int j, int k) /* swap x[i..i+k-1] with x[j..j+k-1] */

{ int t;

      while (k-- > 0) {

             t = x[i]; x[i] = x[j]; x[j] = t;

             i++;

             j++;

      } 

} 

void gcdrot(int rotdist, int n)

{ int i, j, p;

      if (rotdist == 0 || rotdist == n)

             return;

      i = p = rotdist;

      j = n - p;

      while (i != j) {

             /* invariant:

                   x[0  ..p-i  ] is in final position

                   x[p-i..p-1  ] = a (to be swapped with b)

                   x[p  ..p+j-1] = b (to be swapped with a)

                   x[p+j..n-1  ] in final position

             */

             if (i > j) {

                   swap(p-i, p, j);

                   i -= j;

             } else {

                   swap(p-i, p+j-i, i);

                   j -= i;

             }

      }

      swap(p-i, p, i);

} 

int isogcd(int i, int j)

{ if (i == 0) return j;

      if (j == 0) return i;

      while (i != j) {

             if (i > j)

                   i -= j;

             else

                   j -= i;

      }

      return i;

} 

void testgcd()

{

      int i,j;

      while (scanf("%d %d", &i, &j) != EOF)

             printf("%d\n", isogcd(i,j) );

} 

/* Test all algs */ 

void slide(int rotdist, int n) /* Benchmark: slide left rotdist (lose 0..rotdist-1) */

{ int i; 

      for (i = rotdist; i < n; i++)

             x[i-rotdist] = x[i];

} 

void initx()

{

      int i;

      for (i = 0; i < n; i++)

             x[i] = i;

} 

void printx()

{ int i;

      for (i = 0; i < n; i++)

             printf(" %d", x[i]);

      printf("\n");

} 

void roterror()

{

      fprintf(stderr, " rotate bug %d %d\n", n, rotdist);

      printx();

      exit (1);

} 

void checkrot()

{ int i;

      for (i = 0; i < n-rotdist; i++)

             if (x[i] != i+rotdist)

                   roterror();

      for (i = 0; i < rotdist; i++)

             if (x[n-rotdist+i] != i)

                   roterror();

} 

void testrot()

{ for (n = 1; n <= 20; n++) {

             printf(" testing n=%d\n", n);

             for (rotdist = 0; rotdist <= n; rotdist++) {

                   /* printf("  testing rotdist=%d\n", rotdist); */

                   initx(); revrot(rotdist, n);     checkrot();

                   initx(); jugglerot(rotdist, n);  checkrot();

                   initx(); jugglerot2(rotdist, n); checkrot();

                   initx(); gcdrot(rotdist, n);     checkrot();

             }

      }

} 

/* Timing */ 

void timedriver()

{ int i, algnum, numtests, start, clicks;

      while (scanf("%d %d %d %d", &algnum, &numtests, &n, &rotdist) != EOF) {

             initx();

             start = clock();

             for (i = 0; i < numtests; i++) {

                   if (algnum == 1)

                         revrot(rotdist, n);

                   else if (algnum == 2)

                         jugglerot(rotdist, n);

                   else if (algnum == 22)

                         jugglerot2(rotdist, n);

                   else if (algnum == 3)

                         gcdrot(rotdist, n);

                   else if (algnum == 4)

                         slide(rotdist, n);

             }

             clicks = clock() - start;

             printf("%d\t%d\t%d\t%d\t%d\t%g\n",

                   algnum, numtests, n, rotdist, clicks,

                   1e9*clicks/((float) CLOCKS_PER_SEC*n*numtests));

      }

} 

/* Main */ 

int main()

{ /*testrot();*/

      timedriver();

      return 0;

}