cannam@95: /* addition-chain optimizer */
cannam@95: #include <stdio.h>
cannam@95: #include <stdlib.h>
cannam@95: #include <unistd.h>
cannam@95: 
cannam@95: static int verbose;
cannam@95: static int mulcost = 18;
cannam@95: static int ldcost = 2;
cannam@95: static int sqcost = 10;
cannam@95: static int reflcost = 8;
cannam@95: #define INFTY 100000
cannam@95: 
cannam@95: static int *answer;
cannam@95: static int best_so_far;
cannam@95: 
cannam@95: static void print_answer(int n, int t)
cannam@95: {
cannam@95:      int i;
cannam@95:      printf("| (%d, %d) -> [", n, t);
cannam@95:      for (i = 0; i < t; ++i)
cannam@95: 	  printf("%d;", answer[i]);
cannam@95:      printf("] (* %d *)\n", best_so_far);
cannam@95: }
cannam@95: 
cannam@95: #define DO(i, j, k, cst)			\
cannam@95: if (k < n) {					\
cannam@95:      int c = A[i] + A[j] + cst;			\
cannam@95:      if (c < A[k]) {				\
cannam@95: 	  A[k] = c;				\
cannam@95: 	  changed = 1;				\
cannam@95:      }						\
cannam@95: }
cannam@95: 
cannam@95: #define DO3(i, j, l, k, cst)			\
cannam@95: if (k < n) {					\
cannam@95:      int c = A[i] + A[j] + A[l] + cst;		\
cannam@95:      if (c < A[k]) {				\
cannam@95: 	  A[k] = c;				\
cannam@95: 	  changed = 1;				\
cannam@95:      }						\
cannam@95: }
cannam@95: 
cannam@95: static int optimize(int n, int *A)
cannam@95: {
cannam@95:      int i, j, k, changed, cst, cstmax;
cannam@95: 
cannam@95:      do {
cannam@95: 	  changed = 0;
cannam@95: 	  for (i = 0; i < n; ++i) {
cannam@95: 	       k = i + i;
cannam@95: 	       DO(i, i, k, sqcost);
cannam@95: 	  }
cannam@95: 
cannam@95: 	  for (i = 0; i < n; ++i) {
cannam@95: 	       for (j = 0; j <= i; ++j) {
cannam@95: 		    k = i + j;
cannam@95: 		    DO(i, j, k, mulcost);
cannam@95: 		    k = i - j;
cannam@95: 		    DO(i, j, k, mulcost);
cannam@95: 
cannam@95: 		    k = i + j;
cannam@95: 		    DO3(i, j, i - j, k, reflcost);
cannam@95: 	       }
cannam@95: 	  }
cannam@95: 
cannam@95:      } while (changed);
cannam@95: 
cannam@95:      cst = cstmax = 0;
cannam@95:      for (i = 0; i < n; ++i) {
cannam@95: 	  cst += A[i];
cannam@95: 	  if (A[i] > cstmax) cstmax = A[i];
cannam@95:      }
cannam@95: /*     return cstmax; */
cannam@95:      return cst;
cannam@95: }
cannam@95: 
cannam@95: static void search(int n, int t, int *A, int *B, int depth)
cannam@95: {
cannam@95:      if (depth == 0) {
cannam@95: 	  int i, tc;
cannam@95: 	  for (i = 0; i < n; ++i)
cannam@95: 	       A[i] = INFTY;
cannam@95: 	  A[0] = 0;		/* always free */
cannam@95: 	  for (i = 1; i <= t; ++i)
cannam@95: 	       A[B[-i]] = ldcost;
cannam@95: 
cannam@95: 	  tc = optimize(n, A);
cannam@95: 	  if (tc < best_so_far) {
cannam@95: 	       best_so_far = tc;
cannam@95: 	       for (i = 1; i <= t; ++i)
cannam@95: 		    answer[t - i] = B[-i];
cannam@95: 	       if (verbose)
cannam@95: 		    print_answer(n, t);
cannam@95: 	  }
cannam@95:      } else {
cannam@95: 	  for (B[0] = B[-1] + 1; B[0] < n; ++B[0])
cannam@95: 	       search(n, t, A, B + 1, depth - 1);
cannam@95:      }
cannam@95: }
cannam@95: 
cannam@95: static void doit(int n, int t)
cannam@95: {
cannam@95:      int *A;
cannam@95:      int *B;
cannam@95: 
cannam@95:      A = malloc(n * sizeof(int));
cannam@95:      B = malloc((t + 1) * sizeof(int));
cannam@95:      answer = malloc(t * sizeof(int));
cannam@95: 
cannam@95:      B[0] = 0;
cannam@95:      best_so_far = INFTY;
cannam@95:      search(n, t, A, B + 1, t);
cannam@95: 
cannam@95:      print_answer(n, t);
cannam@95: 
cannam@95:      free(A); free(B); free(answer);
cannam@95: }
cannam@95: 
cannam@95: int main(int argc, char *argv[])
cannam@95: {
cannam@95:      int n = 32;
cannam@95:      int t = 3;
cannam@95:      int all;
cannam@95:      int ch;
cannam@95: 
cannam@95:      verbose = 0;
cannam@95:      all = 0;
cannam@95:      while ((ch = getopt(argc, argv, "n:t:m:l:r:s:va")) != -1) {
cannam@95: 	  switch (ch) {
cannam@95: 	  case 'n':
cannam@95: 	       n = atoi(optarg);
cannam@95: 	       break;
cannam@95: 	  case 't':
cannam@95: 	       t = atoi(optarg);
cannam@95: 	       break;
cannam@95: 	  case 'm':
cannam@95: 	       mulcost = atoi(optarg);
cannam@95: 	       break;
cannam@95: 	  case 'l':
cannam@95: 	       ldcost = atoi(optarg);
cannam@95: 	       break;
cannam@95: 	  case 's':
cannam@95: 	       sqcost = atoi(optarg);
cannam@95: 	       break;
cannam@95: 	  case 'r':
cannam@95: 	       reflcost = atoi(optarg);
cannam@95: 	       break;
cannam@95: 	  case 'v':
cannam@95: 	       ++verbose;
cannam@95: 	       break;
cannam@95: 	  case 'a':
cannam@95: 	       ++all;
cannam@95: 	       break;
cannam@95: 	  case '?':
cannam@95: 	       fprintf(stderr, "use the source\n");
cannam@95: 	       exit(1);
cannam@95: 	  }
cannam@95:      }
cannam@95: 
cannam@95:      if (all) {
cannam@95: 	  for (n = 4; n <= 64; n *= 2) {
cannam@95: 	       int n1 = n - 1; if (n1 > 7) n1 = 7;
cannam@95: 	       for (t = 1; t <= n1; ++t)
cannam@95: 		    doit(n, t);
cannam@95: 	  }
cannam@95:      } else {
cannam@95: 	  doit(n, t);
cannam@95:      }
cannam@95: 
cannam@95:      return 0;
cannam@95: }