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