\datethis @*Intro. I'm hurriedly experimenting with a new(?) way to explore the complexity of 4-variable Boolean functions. Namely, I calculate the footprint'' of each function, the set of all first steps by which I know how to evaluate the function in $k$ steps. Then, if the footprints of $f$ and $g$ overlap, I can compute $f\circ g$ in ${\rm cost}(f)+{\rm cost}(g)$ steps. I can restrict consideration to the $2^{15}$ functions that take $(0,0,0,0)\mapsto0$. This program extends {\mc FCHAINS4} by allowing several additional functions to be precomputed. Those functions appear on the command line, in hexadecimal form. @d footsize 100 @c #include #include typedef struct node_struct { unsigned int footprint[footsize]; int parent; int cost; struct node_struct *prev, *next; } node; node func[1<<15]; node head[9]; int x[100]; char buf[100]; /* lines of input */ char name[32*footsize][16]; unsigned int ttt; /* truth table found in input line */ main(int argc,char *argv[]) { register int c,j,k,r,t,m,mm,s; register unsigned int u; register node *p,*q,*pp; @; @; for (r=2;c;r++) for (k=(r-1)>>1;k>=0;k--) @; @; } @ @= m=argc+3; for (k=1;k<=m;k++) { if (k<=4) x[k]=0xffff/((1<<(1<<(4-k)))+1); else if (sscanf(argv[k-4],"%x",&x[k])!=1) { fprintf(stderr,"Parameter %s should have been hexadecimal!\n",argv[k-4]); exit(-1); } if (x[k]>0xffff) { fprintf(stderr,"Parameter %s is too big!\n",argv[k-4]); exit(-1); } if (x[k]>=0x8000) x[k]^=0xffff; } @ @= for (p=head[k].next;p->parent>=0;p=p->next) for (q=head[r-1-k].next;q->parent>=0;q=q->next) { for (j=0;jfootprint[j] & q->footprint[j]) @@; @; pqdone: continue; } @ @d fun(p) ((p)-func) @= { t=fun(p)&fun(q); if (func[t].cost>=r) @; t=fun(p)&(~fun(q)); if (func[t].cost>=r) @; t=(~fun(p))&fun(q); if (func[t].cost>=r) @; t=fun(p)|fun(q); if (func[t].cost>=r) @; t=fun(p)^fun(q); if (func[t].cost>=r) @; } @ @= { pp=&func[t]; if (pp->cost>r) { if (pp->cost==8) c--; pp->next->prev=pp->prev, pp->prev->next=pp->next; pp->cost=r, pp->parent=(fun(p)<<16)+fun(q); for (j=0;jfootprint[j]=0; pp->next=head[r].next, pp->prev=&head[r]; pp->next->prev=pp, pp->prev->next=pp; } for (j=0;jfootprint[j]|=p->footprint[j]|q->footprint[j]; } @ @= { t=fun(p)&fun(q); if (func[t].cost>=r-1) @; t=fun(p)&(~fun(q)); if (func[t].cost>=r-1) @; t=(~fun(p))&fun(q); if (func[t].cost>=r-1) @; t=fun(p)|fun(q); if (func[t].cost>=r-1) @; t=fun(p)^fun(q); if (func[t].cost>=r-1) @; goto pqdone; } @ This code is not executed when $k=0$, because |q|'s footprint is zero in that case. @= { pp=&func[t]; if (pp->cost>r-1) { if (pp->cost==8) c--; pp->next->prev=pp->prev, pp->prev->next=pp->next; pp->cost=r-1, pp->parent=(fun(p)<<16)+fun(q); for (j=0;jfootprint[j]=0; pp->next=head[r-1].next, pp->prev=&head[r-1]; pp->next->prev=pp, pp->prev->next=pp; } for (j=0;jfootprint[j]|=p->footprint[j]&q->footprint[j]; } @ @= for (p=&func[2];p<&func[0x8000];p++) (p-1)->next=p, p->prev=p-1, p->cost=8; func[1].cost=8; for (k=0;k<=8;k++) head[k].parent=-1, head[k].next=head[k].prev=&head[k]; head[0].next=head[0].prev=&func[0]; func[0].next=func[0].prev=&head[0]; head[8].next=&func[1], func[1].prev=&head[8]; head[8].prev=&func[0x7fff], func[0x7fff].next=&head[8]; @; @; @ @= for (k=1;k<=m;k++) { p=&func[x[k]]; if (p->cost==0) continue; p->next->prev=p->prev, p->prev->next=p->next; p->cost=0; p->next=head[0].next, p->prev=&head[0]; p->next->prev=p, p->prev->next=p; } c=(1<<15)-1-m; @ @= s=0; for (r=2;r<=m;r++) for (k=1;k; t=x[k]&(~x[r]), sprintf(name[s],"%d>%d(%04x)",k,r,t); @; t=(~x[k])&x[r], sprintf(name[s],"%d<%d(%04x)",k,r,t); @; t=x[k]|x[r], sprintf(name[s],"%d|%d(%04x)",k,r,t); @; t=x[k]^x[r], sprintf(name[s],"%d^%d(%04x)",k,r,t); @; } mm=(s+31)/32; @ @= p=&func[t]; if (p->cost>1) { if (s>=32*footsize) { fprintf(stderr,"Too many special functions (footsize=%d)!\n",footsize); exit(-3); } p->next->prev=p->prev, p->prev->next=p->next; p->cost=1, p->parent=(x[k]<<16)+x[r]; p->footprint[s>>5]=1<<(s&0x1f); p->next=head[1].next, p->prev=&head[1]; p->next->prev=p, p->prev->next=p; s++; c--; } @ @= while (1) { printf("Truth table (hex): "); fflush(stdout); if (!fgets(buf,100,stdin)) break; if (sscanf(buf,"%x",&ttt)!=1) break; printf("%04x has cost ",ttt); if (ttt&0x8000) ttt^=0xffff; printf("%d, parents (%04x,%04x), and footprint", func[ttt].cost,func[ttt].parent>>16,func[ttt].parent&0xffff); for (j=0;j>=1, s++) if (u&1) printf(" %s",name[s]); } printf("\n"); } @*Index.