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