/***********************************************************************/
/*                                                                     */
/* This program is free to copy !                                      */
/*                                                                     */
/* Program: coin.c                                                     */
/*                                                                     */
/* Description:                                                        */
/*                                                                     */
/* Take a pile of n coins, all with the same side upp. Then turn the   */
/* uppermost coin, the 2 uppermost coins, the 3 uppermost coins and    */
/* so on. When you have turned all n coins you start to turn the       */
/* uppermost coin again and so on.                                     */
/*                                                                     */
/* The question is: How many turns are nedded before all coins have    */
/* the same side upp again?                                            */
/*                                                                     */
/* Answer: Run the program!                                            */
/*                                                                     */
/* Algorithm and program by: Stefan Spaennare, Lund, Sweden            */
/*                                                                     */
/* E-mail:                   stefan@spaennare.se                       */
/*                                                                     */
/* First version:            October 1994                              */
/* Latest update:            2003-02-19                                */
/*                                                                     */
/*                                                                     */
/* Benchmark                                                           */
/* =========                                                           */
/*                                                                     */
/* The test was run on a Intel Celeron (Tualatin core) computer        */
/* with 256 kbyte cache memory and 512 Mbyte primary memory.           */
/* The operating system was Red Hat 7.2 Linux. Compiler tested         */
/* was GNU GCC 2.96 (gcc) for Linux. Under Windows XP the compiler     */
/* GNU DJGPP 3.0.4 (gcc, djgpp) for DOS was used.                      */
/*                                                                     */
/* Numbers tested:                                                     */
/* ---------------                                                     */
/*                                                                     */
/* nmin = 1                                                            */
/*                                                                     */
/* na = nmax = 200                                                     */
/*                                                                     */
/* nb = nmax = 400                                                     */
/*                                                                     */
/* Results:                                                            */
/* --------                                                            */
/*                                                                     */
/* n:  Computer:         CPU-time (s):  Compiler options:              */
/* ================================================================    */
/*                                                                     */
/* na  Celeron 1200 MHz       1.21      gcc -O3                        */
/* na  Celeron 1200 MHz       0.88      gcc -O2 (djgpp)                */
/*                                                                     */
/* nb  Celeron 1200 MHz      15.83      gcc -O3                        */
/* nb  Celeron 1200 MHz      12.80      gcc -O2 (djgpp)                */
/*                                                                     */
/*                                                                     */
/*                                                                     */ 
/* Old enchmark                                                        */
/* ============                                                        */
/*                                                                     */
/* nmin=1, nmax=200                                                    */
/*                                                                     */
/* Processor:             CPU-time (s):            Compilation:        */
/*                                                                     */
/* Pentium 180 MHz           10.66                    gcc -O3          */ 
/*                                                                     */
/***********************************************************************/

/********************************************************************************/
/*                                                                              */
/* Notice                                                                       */
/* ======                                                                       */
/*                                                                              */
/* I make no warranties that this program is (1) free of errors, (2) consistent */
/* with any standard merchantability, or (3) meeting the requirements of a      */
/* particular application. This software shall not, partly or as a whole,       */
/* participate in a process, whose outcome can result in injury to a person or  */
/* loss of property. It is solely designed for analytical work. Permission to   */
/* use, copy and distribute is hereby granted without fee, providing that the   */
/* header above including this notice appears in all copies.                    */
/*                                                                              */
/*                                                            Stefan Spaennare  */
/*                                                                              */
/********************************************************************************/


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


double timetic=(double)(CLOCKS_PER_SEC);

int main(argc,argv) 
int argc;
char *argv[];
{

   int i,k,sum,m,s,nmin,nmax,m2,temp;

   double ftime;

   clock_t time1,timediff;

   int *v;

   if (argc != 3) {
      printf("Usage: %s nmini nmaxi\n",argv[0]);
      exit(0);
   } /* if */

   nmin=atoi(argv[1]);
   nmax=atoi(argv[2]);

   v = (int *)calloc(nmax+1,sizeof(int));

   time1=clock();

   for (i=1; i<=nmax; i++) {
      v[i]=1;
   } /* for i */

   for (k=nmin; k<=nmax; k++) {

      s=0;
      m=1;

      do {

	 m2=m/2;

	 for (i=1; i<=m2; i++) {
	    temp=v[i];
	    v[i]=-v[m-i+1];
	    v[m-i+1]=-temp;
	 } /* for i */

	 if ((m % 2) == 1) {
	    v[m2+1]=-v[m2+1];
	 } /* if */

	 sum=0;

	 for (i=1; i<=k; i++) {
	    sum=sum+v[i];
	 } /* for i */

	 m++;
	 s++;

	 if (m > k) {
	    m=1;
	 } /* if */

      } while (sum != k);

      printf("%6d %9d |",k,s);

      if ((k % 4) == 0) {
	 printf("\n");
      } /* if */

   } /* for k */


   timediff=clock()-time1;

   ftime=(double)(timediff)/timetic;

   printf("\n%12.2f\n",ftime);

} /* end */