/******************************************************************************/
/*									      */
/*  CHECK PARITY VECTOR (to determine if it is a rotation of the parity       */
/*			 vector p)					      */
/*  07/09/13 (dkc)							      */
/*									      */
/******************************************************************************/
#include <stdio.h>
#include <math.h>
#include "ln.h"
#include "sv.h"

unsigned int lastl[285]={ // last of the group of l values with a difference of 3
	  30,38,49,57,68,76,95,103,114,122,133,141,152,160,168,179,187,198,206,
	  217,225,236,244,252,263,271,282,290,301,309,320,328,336,347,355,366,
	  374,385,393,404,412,420,431,439,450,458,469,477,488,496,504,515,523,
	  534,542,553,561,580,588,599,607,618,626,637,645,653,664,672,683,691,
	  702,710,721,729,737,748,756,767,775,786,794,805,813,821,832,840,851,
	  859,870,878,889,897,905,916,924,935,943,954,962,973,981,989,1000,
	  1008,1019,1027,1038,1046,1065,1073,1084,1092,1103,1111,1122,1130,
	  1138,1149,1157,1168,1176,1187,1195,1206,1214,1222,1233,1241,1252,
	  1260,1271,1279,1290,1298,1306,1317,1325,1336,1344,1355,1363,1374,
	  1382,1390,1401,1409,1420,1428,1439,1447,1458,1466,1474,1485,1493,1504,
	  1512,1523,1531,1542,1550,1558,1569,1577,1588,1596,1607,1615,1623,
	  1634,1642,1653,1661,1672,1680,1691,1699,1707,1718,1726,1737,1745,1756,
	  1764,1775,1783,1791,1802,1810,1821,1829,1840,1848,1859,1867,1875,1886,
	  1894,1905,1913,1924,1932,1943,1951,1959,1970,1978,1989,1997,2008,2016,
	  2027,2035,2043,2054,2062,2073,2081,2092,2100,2108,2119,2127,2138,2146,
	  2157,2165,2176,2184,2192,2203,2211,2222,2230,2241,2249,2260,2268,2276,
	  2287,2295,2306,2314,2325,2333,2344,2352,2360,2371,2379,2390,2398,2409,
	  2417,2428,2436,2444,2455,2463,2474,2482,2493,2501,2512,2520,2528,2539,
	  2547,2558,2566,2577,2585,2596,2604,2612,2623,2631,2642,2650,2661,2669,
	  2677,2688,2696,2707};

unsigned int conv[75*2]={ // generalized continued-fraction convergents of log(3)/log(2)
 5, 3, 6, 4, 8, 5, 9, 6, 11, 7, 16, 10, 19, 12, 24, 15, 27, 17, 38, 24, 46, 29, 
 57, 36, 65, 41, 76, 48, 84, 53, 130, 82, 149, 94, 168, 106, 233, 147, 252, 159, 
 317, 200, 336, 212, 401, 253, 420, 265, 485, 306, 504, 318, 569, 359, 970, 612, 
 1054, 665, 1455, 918, 1539, 971, 2108, 1330, 2593, 1636, 3162, 1995, 3647, 2301, 
 4216, 2660, 4701, 2966, 5270, 3325, 5755, 3631, 6324, 3990, 6809, 4296, 7378, 4655, 
 7863, 4961, 8432, 5320, 8917, 5626, 9486, 5985, 9971, 6291, 10540, 6650, 11025, 6956, 
 11594, 7315, 12079, 7621, 12648, 7980, 13133, 8286, 13702, 8645, 14187, 8951, 
 14756, 9310, 15241, 9616, 15810, 9975, 16295, 10281, 16864, 10640, 17349, 10946, 
 17918, 11305, 18403, 11611, 18972, 11970, 19457, 12276, 20026, 12635, 20511, 12941, 
 21080, 13300, 21565, 13606, 22134, 13965, 22619, 14271, 23188, 14630, 23673, 14936, 
 24242, 15295, 24727, 15601};
//l=3;		       // continued-fraction convergents of log(3)/log(2)
//n=2;
//l=8;
//n=5;
//l=19;
//n=12;
//l=65;
//n=41;
//l=84;
//n=53;
//l=485;
//n=306;
//l=1054;
//n=665;
//l=24727;
//n=15601;

int main () {
unsigned int l,lp,a,b,h,i,j,k,n,np,flag;
unsigned int pv[25000],qv[25000];
FILE *Outfp;
Outfp = fopen("out14db.dat","w");
for (h=4; h<75; h++) {
   l=conv[2*h];
   n=conv[2*h+1];
   printf("l=%d, n=%d \n",l,n);
   fprintf(Outfp,"l=%d, n=%d \n",l,n);
   for (j=1; j<=l; j++) {
      a=j*n;
      if (a==((a/l)*l)) 		// a=(j*n)/l
	 a=a/l;
      else
	 a=(a/l)+1;
      b=(j-1)*n;
      if (b==((b/l)*l)) 		// b=((j-1)*n)/l
	 b=b/l;
      else
	 b=(b/l)+1;
      if (j!=1) 			// skip first element
	qv[j-2]=a-b;
      }
   qv[l-1]=0;
   lp=l;
//
// check if a rotation of parity vector matches parity vector p
//
   for (i=0; i<1000; i++) {
      l=ln[i]>>16;
      for (k=0; k<lp; k++)     // copy parity vector
	 pv[k]=qv[k];
      flag=0;		       // check for required element swaps
      for (k=0; k<285; k++) {
	 if (l==lastl[k]) {
	    flag=1;
	    break;
	    }
	 if (lastl[k]>l)
	    break;
	 }
      if (flag!=0) {	       // switch last two elements
	 a=pv[l-2];
	 pv[l-2]=pv[l-1];
	 pv[l-1]=a;
	 }
      n=0;		       // check if number of odd elements match
      np=0;
      for (k=0; k<l; k++) {
	 n=n+pv[k];
	 np=np+sv[k];
	 }
      if ((n!=np)||(n!=(ln[i]&0xffff))) {
	 if ((n+1)!=conv[2*h+1]) {
	    printf("number of odd elements not equal: n=%d, np=%d \n",n,np);
	    fprintf(Outfp,"number of odd elements not equal: n=%d, np=%d \n",n,np);
	    goto zskip;
	    }
	 else
	    goto cskip;
	 }
      for (k=0; k<l; k++) {    // compare parity vectors
	 for (j=0; j<l; j++) {
	    if (pv[j]!=sv[j])
	       goto askip;
	    }
	 if (k!=3) {
	    printf("l=%d, n=%d, k=%d \n",l,n,k);
	    fprintf(Outfp,"l=%d, n=%d, k=%d \n",l,n,k);
	    }
	 goto bskip;
askip:
	 a=pv[l-1];	       // rotate parity vector
	 for (j=(l-1); j>0; j--)
	    pv[j]=pv[j-1];
	 pv[0]=a;
	 }
      printf("l=%d, n=%d, no match \n",l,n);
      fprintf(Outfp,"l=%d, n=%d, no match \n",l,n);
      if (((l+3)==conv[h*2])&&((n+2)==conv[h*2+1]))
	 break;
      else {
	 if ((l==conv[h*2])&&(n==conv[h*2+1]))
	    break;
	 else {
	    printf("error: l=%d, n=%d \n",l,n);
	    break;
	    }
	 }
bskip:
      k=0;
      }
cskip:
   printf("\n");
   fprintf(Outfp,"\n");
   }
zskip:
fclose(Outfp);
return(0);
}