addchain.c

/* addition-chain optimizer */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

static int verbose;
static int mulcost = 18;
static int ldcost = 2;
static int sqcost = 10;
static int reflcost = 8;
#define INFTY 100000

static int *answer;
static int best_so_far;

static void print_answer(int n, int t)
{
     int i;
     printf("| (%d, %d) -> [", n, t);
     for (i = 0; i < t; ++i)
	  printf("%d;", answer[i]);
     printf("] (* %d *)\n", best_so_far);
}

#define DO(i, j, k, cst)			\
if (k < n) {					\
     int c = A[i] + A[j] + cst;			\
     if (c < A[k]) {				\
	  A[k] = c;				\
	  changed = 1;				\
     }						\
}

#define DO3(i, j, l, k, cst)			\
if (k < n) {					\
     int c = A[i] + A[j] + A[l] + cst;		\
     if (c < A[k]) {				\
	  A[k] = c;				\
	  changed = 1;				\
     }						\
}

static int optimize(int n, int *A)
{
     int i, j, k, changed, cst, cstmax;

     do {
	  changed = 0;
	  for (i = 0; i < n; ++i) {
	       k = i + i;
	       DO(i, i, k, sqcost);
	  }

	  for (i = 0; i < n; ++i) {
	       for (j = 0; j <= i; ++j) {
		    k = i + j;
		    DO(i, j, k, mulcost);
		    k = i - j;
		    DO(i, j, k, mulcost);

		    k = i + j;
		    DO3(i, j, i - j, k, reflcost);
	       }
	  }

     } while (changed);

     cst = cstmax = 0;
     for (i = 0; i < n; ++i) {
	  cst += A[i];
	  if (A[i] > cstmax) cstmax = A[i];
     }
/*     return cstmax; */
     return cst;
}

static void search(int n, int t, int *A, int *B, int depth)
{
     if (depth == 0) {
	  int i, tc;
	  for (i = 0; i < n; ++i)
	       A[i] = INFTY;
	  A[0] = 0;		/* always free */
	  for (i = 1; i <= t; ++i)
	       A[B[-i]] = ldcost;

	  tc = optimize(n, A);
	  if (tc < best_so_far) {
	       best_so_far = tc;
	       for (i = 1; i <= t; ++i)
		    answer[t - i] = B[-i];
	       if (verbose)
		    print_answer(n, t);
	  }
     } else {
	  for (B[0] = B[-1] + 1; B[0] < n; ++B[0])
	       search(n, t, A, B + 1, depth - 1);
     }
}

static void doit(int n, int t)
{
     int *A;
     int *B;

     A = malloc(n * sizeof(int));
     B = malloc((t + 1) * sizeof(int));
     answer = malloc(t * sizeof(int));

     B[0] = 0;
     best_so_far = INFTY;
     search(n, t, A, B + 1, t);

     print_answer(n, t);

     free(A); free(B); free(answer);
}

int main(int argc, char *argv[])
{
     int n = 32;
     int t = 3;
     int all;
     int ch;

     verbose = 0;
     all = 0;
     while ((ch = getopt(argc, argv, "n:t:m:l:r:s:va")) != -1) {
	  switch (ch) {
	  case 'n':
	       n = atoi(optarg);
	       break;
	  case 't':
	       t = atoi(optarg);
	       break;
	  case 'm':
	       mulcost = atoi(optarg);
	       break;
	  case 'l':
	       ldcost = atoi(optarg);
	       break;
	  case 's':
	       sqcost = atoi(optarg);
	       break;
	  case 'r':
	       reflcost = atoi(optarg);
	       break;
	  case 'v':
	       ++verbose;
	       break;
	  case 'a':
	       ++all;
	       break;
	  case '?':
	       fprintf(stderr, "use the source\n");
	       exit(1);
	  }
     }

     if (all) {
	  for (n = 4; n <= 64; n *= 2) {
	       int n1 = n - 1; if (n1 > 7) n1 = 7;
	       for (t = 1; t <= n1; ++t)
		    doit(n, t);
	  }
     } else {
	  doit(n, t);
     }

     return 0;
}