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