//////////// Concise Hadamard Matrix generator by Warren D. Smith, March 2020 ///////////// //Compile with gcc -Wall -O3 HadaGen.c //2-page-long program to generate NxN Hadamard matrix; works for infinite set of N, //including all N<=256 with 4|N except 188 & 236. // If program were doubled or tripled in length (which I did not do) then ought to //be able to make it do every N=4yz with y<=70, z<=79, and y not 35,47,53,59,65,67. #include #include #include #include #include #include #define uint unsigned int #define uint32 uint32_t #define uint16 uint16_t #define uint64 uint64_t #define uint8 unsigned char #define int8 signed char #define real64 double const uint64 willmsn[][5] = { {40, 0xD6ULL, 0x345ULL, 0x393ULL, 0x1EFULL}, {52, 0x14F2ULL, 0x11F8ULL, 0x1A65ULL, 0x1090ULL}, {56, 0x164DULL, 0x1CA7ULL, 0x3CA7ULL, 0x1F1FULL}, {88, 0xE952EULL, 0x9DF72ULL, 0x3ACE6BULL, 0x1BE0FBULL}, {92, 0x7740BBULL, 0x71AD63ULL, 0x5B3F36ULL, 0x622D11ULL}, {96, 0x9CAA9CULL, 0x25F7D2ULL, 0xCE5D39ULL, 0x6FC1FBULL}, {100, 0x178661EULL, 0x1DC5A3BULL, 0x16EC376ULL, 0x13500ACULL}, {112, 0x16B76B4ULL, 0x6CC719BULL, 0xBC1DC1EULL, 0xFCD559FULL}, {116, 0x192EF749ULL, 0x1ED1F8B7ULL, 0x1465FA62ULL, 0x1C650A63ULL}, {120, 0x2D3F968ULL, 0x14CF1E65ULL, 0x3716AD1DULL, 0x3E65F4CFULL}, {136, 0x2865EF4C2ULL, 0xDD254976ULL, 0x3638FE38DULL, 0x1DBE82FB7ULL}, {144, 0x796A22B4FULL, 0xBE60D833EULL, 0x75A3762D7ULL, 0x9EEF07BBCULL}, {156, 0x7282619053ULL, 0x7898528647ULL, 0x73452128B3ULL, 0x46A0EDC158ULL}, {160, 0xC879AACF09ULL, 0xB746493176ULL, 0x4792F7A4F1ULL, 0x5EFE223FBDULL}, {172, 0x467AECDD798ULL, 0x6FC29B650FDULL, 0x7595E85EA6BULL, 0x63D260192F1ULL}, {176, 0x676D4215B73ULL, 0x3F589AC8D7EULL, 0x5D3EC21BE5DULL, 0x8F4FB8EF978ULL}, {184, 0x2AD90F1E136AULL, 0x2379564D53D8ULL, 0x25A31FFF18B4ULL, 0x33FCB913A7F9ULL}, {208, 0xB34ED4515B966ULL, 0x2F7487270977AULL, 0x785919FCC4D0FULL, 0x25C7FAFAFF1D2ULL}, {216, 0x2775B40A05B5DCULL, 0x213CDB953B6790ULL, 0x313E707BC1CF91ULL, 0x275D4BEEFA575CULL}, {232, 0x13E48AB39AA24F9ULL, 0x35E0BD30197A0F5ULL, 0x9CDEB5835AF672ULL, 0x4F1DBEEEFB71E4ULL}, {244, 0x1932BC820413D4C9ULL, 0x1932BC820413D4C9ULL, 0x115E32D1F8B4C7A8ULL, 0x1EA1CD2E074B3857ULL}, {248, 0x224F64EB1AE4DE48ULL, 0x3ABE5209F2094FABULL, 0x569F373B9D9F2D4ULL, 0x30F5CEFA0BEE75E1ULL}, {999,0,0,0,0} //sentinel }; bool NaiveIsPrime(int N){ for(int i=3; i*i<=N; i+=2){ if(N%i==0) return(0); } return( N==2 || (N%2) ); } #define HD (-1) //use -1 for real orthog, or use 0 for boolean version //Constructs NxN Hadamard {1,HD} matrix. Runtime O(N^2). Returns true if succeeded. //NxN Hadamards exist for N=1,2 and all N<1000 divisible by 4 except perhaps 668, 716, 892; //and for over 90% of the N<40000 divisible by 4. Conjecturally 4|N ==> NxN Hadamard exists. //This routine succeeds for every N<=256 with 4|N (& many N>256) except 188=47*4 & 236=59*4; //and also for 75% of the N with 4|N and 2560 && (N&(N-1))==0 ){ //N = 1,2,4,8,16,32,64,... is power of 2 for(i=0; i0 && N%4==0 && NaiveIsPrime(N-1)){ //Paley-I construction for 4,8,12,20,24,32,44,60,68,72,80,84... p=N-1; for(i=N*N-1; i>p; i--){ mat[i] = HD; } for( ; i>=0; i--){ mat[0*N+i] = 1; } for(k=0; k=0; i--){ j=(s+i)%p; mat[N*(i+1)+j+1]=1; } } return(true); } if(N>0 && N%8==4 && NaiveIsPrime( (p=(h=N/2)-1) )){ //Raymond Paley's constrctn II: N=12,28,36,56,60,76,84... #define PA(x,y,tl,tr,bl,br) mat[(y)*N+x]=tl; mat[(y)*N+x+h]=tr; mat[(y+h)*N+x]=bl; mat[(y+h)*N+x+h]=br for(k=1; k=0; i--){ j=(s+i)%p; PA(i+1,j+1,1,1,1,HD); }} for(i=0; i>(h+k-1-j)%h))&1)?1:HD; }} WC(a,0,0); WC( a,1,1); WC( a,2,2); WC( a,3,3); WC(b,0,1); WC(~b,1,0); WC(~b,2,3); WC( b,3,2); WC(c,0,2); WC( c,1,3); WC(~c,2,0); WC(~c,3,1); WC(d,0,3); WC(~d,1,2); WC( d,2,1); WC(~d,3,0); #undef WC return(true); } if( (h=N/2)%4==0 && h>10 && Hadamard(mat,h) ){ //doubling recursive hXh Hadamard for(i=N-1; i>=0; i--){ for(j=N-1; j>=0; j--){ p=mat[(i/2)*h+(j/2)]; mat[i*N+j] = ((i&j&1) ? (p==1 ? HD:1) : p); }} return(true); } return(false); } ///////////////////////////////////end of code (can snip here) ////////////////////////////////// ////////////////Notes about how to possibly extend program to generate more Hadamards://///////////// //If "base sequences" BS(k+1,k)=[A,B,C,D] exist (do when 0<=k<41) e.g. here's k=39 by D.Z.Dokovic: // A=++--++--+-+++--+--+-++--+-+-+++-++++-+-+, // B=+++---+------+++-+--+-+-++-+--+++-------, // C=++++++++--++--++-++-+-+++-+---+-+----++, // D=+++----+---+++-----+-++--+--+-+--+++-++, //then T-seqs with z=2k+1 exist: [(A+B)/2, 0_k; (A-B)/2, 0_k; 0_k+1, (C+D)/2; 0_k+1, (C-D)/2]. //"T-sequences" exist for every order z<103 except perhaps 97. Those yield four zXz "T-matrices" //A,B,C,D (not same as old) of circulant form - the T-sequence components give their first rows. //Then A'=aA+bB+cC+dD, B'=-bA+aB+dC-cD, C'=-cA-dB+aC+bD, D'=-dA+cB-bC+aD //may be plugged into the Goethals-Seidel 4x4 array to yield an OD(4z) aka a //4zX4z "Baumert-Hall-Welch array." Finally those yield NxN Hadamards //where N=4zw where w is the order of any quadruple of Williamson-type matrices. //If w=1 these Hadamards are 4x4 arrays of zXz blocks, each block either //circulant or back-circulant. //(Goethals-Seidel 4x4 array resembles Williamson & also yields 4wX4w Hadamards. //Base sequences tabulated by Christos Koukouvinos for 0<=k<=35.) // //Special constructions for our missing cases N=188 and 236: //N=188: A B C D, -B A -E F, -C E A G, -D -F -G A for certain circulant & back-circulant ABCDEFG, //see Annals of Statistics 6,6 (Nov.1978) pp.1225-1231; N=236: Discrete Maths 286,3 (Sept 2004) 251-253. //188 and 236 also can be constructed from a "T-matrix" of order 47 & 59 respectively, //R.J.Turyn: Hadamard matrices, Baumert-Hall units, four symbol sequences, pulse compression //and surface wave encodings, J. Combin. Theory A 16 (1974) 313-333, see p.326 for Had(236). // //Constructions for more missing cases: // 324: 3^d [Mukhopadhay: Some infinite classes of Hadamard matrices 1978; // Turyn: A special class of Williamson matrices and difference sets 1984. // 372: s(4s+3),s(4s-1) [J.S.Wallis: Construction of Williamson type matrices 1975] // 292: q=1(mod4) prime power: (q-1)/2=order of symmetric conference or Hadamard matrix [Miyamoto 1991] // 356: 2q+1=prime power; q=1(mod4) prime [J.S.Wallis: Hadamard matrices 1972] // 340: 2(q+1) where q=1(mod4) is a prime power [Paley, Goethals+Seidel] ///////////////////////Test driver://///////////////////////// bool VerifyHadamard(int8 mat[], uint N){ int i,j,k,s; bool y,x=Hadamard(mat, N); printf("VerifyHadamard(%d): claim=%d ", N, y=x); for(i=0; i