diff options
| -rw-r--r-- | charf.c | 50 |
1 files changed, 34 insertions, 16 deletions
@@ -155,24 +155,42 @@ void compute_maximalfunction(VALUETYPE* f, VALUETYPE* Mf, int D){ /*Generates all characteristic functions of length up N.*/ int generate_each_charf(VALUETYPE* f, int i){ int s=0; - int d=0; - while(d+2 <= N){ - /*number of strings of length d that are not all 0s or all 1s*/ - int powd = 1<<d; - if(i-s >= powd){ - s += powd; - d++; - } - else { - int t = i-s; - /*Set f to the values encoded in bit string t which is a value between 1 and powd = (1<<d)-2.*/ - f[0] = int_to_valuetype(1); - f[1] = int_to_valuetype(0); - for(int n=0; n<d; n++) f[2+n] = int_to_valuetype((t >> n) & 1); - return d+2; + int d=2; + /*number of strings of length d that begin with 1 but are not all 1*/ + for(s=0; i-s >= (1<<(d-1))-1; d++) s += (1<<(d-1))-1; + + if(d>N) return -1; + + /*t starts with 1 and then comes i-s.*/ + int t = (1 << d-1) + i-s; + + /*Indicates if we want to consider this t.*/ + bool is_representative = true; + + /*Check if t encodes a function that is made up of translations of a shorter function.*/ + for(int r = 1; r < d; r++){ + if(d % r == 0){ + bool is_r_copy = true; + int ones = 0; + for(int o = 0; o<r; o++) ones += 1<<o; + int tail = t & ones; + for(int n = 1; n < d/r; n++) if( ( (t>>n*r) & ones ) != tail ) is_r_copy = false; + if(is_r_copy) is_representative = false; } } - return -1; + + /*Check if t encodes the strictly largest of its equivalent translates.*/ + /*Such t which may equal its translates have already been filtered out by the previous step because they are copies of at least two shorter functions.*/ + int ones = 0; + for(int o = 0; o<d; o++) ones += 1<<o; + if(is_representative) for(int n=1; n<d; n++) if( t <= ( (t<<n) & ones ) + ((t>>(d-n)) & ones) ) is_representative = false; + + /*Set f to the values encoded in bit string t which is a value between 1 and powd = (1<<d)-2.*/ + if(is_representative){ + for(int n=0; n<d; n++) f[n] = int_to_valuetype((t >> (d-n-1)) & 1); + return d; + } + else return 0; } int generate_triangle(VALUETYPE* f, int i){ |