Iterations Gone Awry

**DonFord81** · 09-29-2009

I'm currently in the process of writing a fairly complex program that iterates through a bit array, testing to see if certain combinations of bits are turned on or off. Up until I added the code for the function "check_last", it ran without problems. However, now, the initial matrix is all zeroes and remains zeroed out. Did I implement something incorrectly in "check_last"?

Code:

#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <limits.h>		/* for CHAR_BIT */
#include <math.h>
#include <combination.h>
#include <time.h>

#define DIM 18
#define LOWER 4
#define UPPER (DIM*(DIM-1)/2)
#define BITMASK(b) (1 << ((b) % CHAR_BIT))
#define BITSLOT(b) ((b) / CHAR_BIT)
#define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
#define BITCLEAR(a, b) ((a)[BITSLOT(b)] &= ~BITMASK(b))
#define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))
#define BITNSLOTS(nb) ((nb + CHAR_BIT - 1) / CHAR_BIT)

int factorial(int k);
void increment(char* bitarray, int u);
int test_all_ones(char* bitarray, int u);
void make_matrix(char [][BITNSLOTS(DIM)], char* U_array, int d);
void display(char [][BITNSLOTS(DIM)], int d);
int check_sum(char* bitarray, int u);
int check_K(char [][BITNSLOTS(DIM)], char* U_array, int* combination, int d, int l);
void invert(char* bitarray);
int check_last(char* bitarray, int l, int u);

int main(){
           clock_t tick1, tick2;
           int minutes_elapsed = 0;
           int hours_elapsed = 0;
           int days_elapsed = 0;
           char matrix_array[DIM][BITNSLOTS(DIM)] = {0};
	       char U_array[BITNSLOTS(UPPER)] = {0};
	       int combination[LOWER] = {0};
           int i,j;
           
           tick1 = clock();

           start:

           if ((UPPER-LOWER < LOWER) ||
               (UPPER < ((factorial((2*LOWER)-2))/(factorial(LOWER-1)*factorial(LOWER-1))))){
                      
/* TEST CODE LINE */
              printf("Out of bounds error.\n");
/* TEST CODE LINE */

              printf("r(%d, %d) > %d", LOWER, LOWER, DIM);
              getch();
              return (0);
              }

           while ((check_sum(U_array, UPPER) < (DIM-LOWER)+1) ||
                  (check_sum(U_array, UPPER) > (UPPER-(DIM-LOWER))) ||
                  (check_last(U_array, LOWER, UPPER) == 0)){
                  increment(U_array, UPPER);
                  if (test_all_ones(U_array, UPPER)){
                                             
/* TEST CODE LINE */
                     printf("All ones matrix achieved.\n");
/* TEST CODE LINE */

                     goto end;
                     }
/* TEST CODE LINE */
                  tick2 = clock();
                  if (((tick2-tick1)/CLOCKS_PER_SEC) >= 60){
                     tick1 = clock();
                     minutes_elapsed++;
                     if (minutes_elapsed >= 60){
                        minutes_elapsed = 0;
                        hours_elapsed++;
                        if (hours_elapsed >= 24){
                           hours_elapsed = 0;
                           days_elapsed++;
                           }
                        }
                     printf("Time elapsed: %d days, %d hours, %d minutes.\n", days_elapsed, hours_elapsed, minutes_elapsed);
                     display(matrix_array, DIM);
                     }
/* TEST CODE LINE */
                  }
              
           make_matrix(matrix_array, U_array, DIM);
               
           if (check_K(matrix_array, U_array, combination, DIM, LOWER)){
              increment(U_array, UPPER);
              goto start;
              }
           else{
                display(matrix_array, DIM);
                
/* TEST CODE LINE */
              printf("No complete graph found.\n");
              getch();
/* TEST CODE LINE */

                printf("\n");
                printf("r(%d, %d) > %d", LOWER, LOWER, DIM);
                getch();
                return (0);
                }
              
           end:
               
           printf("r(%d, %d) %c %d", LOWER, LOWER, 243, DIM);        
           getch();
           return (1);
}

void increment(char* bitarray, int u){
     int i = 0;
     while (i < u){
           if (!BITTEST(bitarray, i)){
              BITSET(bitarray, i);
              i = u;
              }
           else{
                BITCLEAR(bitarray, i);
                i++;
                }
           }
}
                
int test_all_ones(char* bitarray, int u){
    int i;
    int counter = 0;
    for (i=0; i<u; i++){
        if (BITTEST(bitarray, i)){
           counter++;
           }
        }
    if (counter == u){
       return (1);
       }
    else{
         return (0);
         }
}

int check_sum(char* bitarray, int u){
    int i;
    int sum = 0;
    for (i=0; i<u; i++){
        if (BITTEST(bitarray, i)){
           sum++;
           }
        }
    return (sum);
}

void make_matrix(char bitarray[][BITNSLOTS(DIM)], char* U_array, int d){
     int i,j,k;
     for (i=0,j=i+1,k=0; k<((d*(d-1))/2); j++,k++){
         if (j >= d){
            i++;
            j = i+1;
            }
         if (BITTEST(U_array, k)){
            BITSET(bitarray[i], j);
            BITSET(bitarray[j], i);
            }
         else{
              BITCLEAR(bitarray[i], j);
              BITCLEAR(bitarray[j], i);
              }
         }
}

void invert(char* bitarray){
     int i;
     for (i=0; i<(UPPER/CHAR_BIT)+1; i++){
         bitarray[i] ^= 0xFF;
         }
}

void display(char bitarray[][BITNSLOTS(DIM)], int d){
     int i, j;
     for (i=0; i<d; i++){
         for (j=0; j<d; j++){
             if (BITTEST(bitarray[i], j)){
                printf("1");
                }
             else{
                  printf("0");
                  }
             }
         printf("\n");
         }
     printf("\n");
}

int check_K(char bitarray[][BITNSLOTS(DIM)], char* U_array, int* combination, int d, int l){
    int i, j;
    int counter = 0;
    int limit = (l*(l-1));
    for (i=0; i<LOWER; i++){
        combination[i] = i;
        }
    for (i=0; i<l; i++){
        for (j=0; j<l; j++){
            if ( (i != j) && (BITTEST(bitarray[combination[i]], combination[j])) ){
               counter++;
               if (counter < 1){
                  next_comb(combination, l, d);
                  goto loop;
                  }
               }
            if ( (i != j) && (!BITTEST(bitarray[combination[i]], combination[j])) ){
               counter--;
               if (counter > 1){
                  next_comb(combination, l, d);
                  goto loop;
                  }
               }
            }
        }
    if ( (counter == limit) || (counter == (-1*limit)) ){
         return (1);
         }
    while (next_comb(combination, l, d)){
          loop:
          counter = 0;
          for (i=0; i<l; i++){
              for (j=0; j<l; j++){
                  if ( (i != j) && (BITTEST(bitarray[combination[i]], combination[j])) ){
                     counter++;
                     if (counter < 1){
                        next_comb(combination, l, d);
                        goto loop;
                        }
                     }
                  if ( (i != j) && (!BITTEST(bitarray[combination[i]], combination[j])) ){
                     counter--;
                     if (counter > 1){
                        next_comb(combination, l, d);
                        goto loop;
                        }
                     }
                  }
              }
          if ( (counter == limit) || (counter == (-1*limit)) ){
             return (1);
             }
          }
    return (0);
}

int factorial(int k){
    int product;
    if ((k == 0) || (k == 1)){
       return (1);
       }
    else{
         for (product=1; k>1; k--){
             product *= k;
             }
         return (product);
         }
}
         
int check_last(char* bitarray, int l, int u){
    int i;
    int m = (factorial(l+1)/(2*factorial(l-1)));
    int sum = 0;
    for (i=(u-m); i<u; i++){
        if (BITTEST(bitarray, i)){
           sum++;
           }
        }
    return (sum);
}

**MK27** · 09-29-2009

Originally Posted by DonFord81

However, now, the initial matrix is all zeroes and remains zeroed out. Did I implement something incorrectly in "check_last"?

Don't think so. Are you sure that's it?

Couple of minor notes: you use unnecessary parantheses in some of your macros, eg:

Code:

#define BITMASK(b) (1 << ((b) % CHAR_BIT))
#define BITMASK(b) (1 << b % CHAR_BIT)

Modulus has a higher precedence than bitshifting.

Also, your use of goto makes main() very spagetti-esque. I would suggest you break this down into discrete functions, which will probably also make it easier to spot problems.

**laserlight** · 09-29-2009

Originally Posted by MK27

you use unnecessary parantheses in some of your macros
(...)
Modulus has a higher precedence than bitshifting.

It is good practice to use such "unnecessary" parentheses, at least around the macro parameter. Consider BITMASK(x + y), where (1 << ((x + y) % CHAR_BIT)) is not (necessarily) the same as (1 << x + y % CHAR_BIT).

**MK27** · 09-29-2009

Originally Posted by laserlight

It is good practice to use such "unnecessary" parentheses, at least around the macro parameter. Consider BITMASK(x + y), where (1 << ((x + y) % CHAR_BIT)) is not (necessarily) the same as (1 << x + y % CHAR_BIT).

Ah...point taken!

**DonFord81** · 09-29-2009

Yes. I use "unnecessary" parentheses to keep myself straight. Not for the program.

At any rate, I've also noticed that when I increase LOWER to 5 and UPPER to 45, the array zeroes out as well, regardless of whether or not I have "check_last" implemented in my program.

I agree that "goto" commands make the program very ... tacky and difficult, but for the life of me, I really couldn't think of another way to really make it do what I wanted it to do.

**MK27** · 09-29-2009

Originally Posted by DonFord81

I agree that "goto" commands make the program very ... tacky and difficult, but for the life of me, I really couldn't think of another way to really make it do what I wanted it to do.

Well you will just keeping thinking spaghetti until you try to do something else then!

I absolutely promise, the reason "goto" is nearing depreciation is because, logically it can NEVER be a necessity. And I really truly promise it is NOT necessary here. What you need to do is think more in terms of short, inter-related functions. That section should be split in two or three, some can perhaps be left in main the rest goes in seperate function. You may have to pass some parameters around, altho most of yours are global anyway.

In the process, maybe you will find your problem. If you have difficulty making the changes, someone will be able to help you pretty easily. I am just too lazy to re-organize the code for you...but like I said, I am positive it will not be that much work.

Thread: Iterations Gone Awry

Thread Tools

Search Thread

Display

Iterations Gone Awry

Similar Threads

How to sort a simple linked list using swap-sort method

Iterations with integers...

Iterations and convergence

Having trouble translating psudeo-code to real-code.

square and cubic functions in C++

Tags for this Thread