Mercurial > hg > sv-dependency-builds

comparison src/fftw-3.3.3/support/addchain.c @ 10:37bf6b4a2645

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add FFTW3
author Chris Cannam
date Wed, 20 Mar 2013 15:35:50 +0000
parents
children
comparison
equal deleted inserted replaced
9:c0fb53affa76 10:37bf6b4a2645
1 /* addition-chain optimizer */
2 #include <stdio.h>
3 #include <stdlib.h>
4 #include <unistd.h>
5
6 static int verbose;
7 static int mulcost = 18;
8 static int ldcost = 2;
9 static int sqcost = 10;
10 static int reflcost = 8;
11 #define INFTY 100000
12
13 static int *answer;
14 static int best_so_far;
15
16 static void print_answer(int n, int t)
17 {
18 int i;
19 printf("| (%d, %d) -> [", n, t);
20 for (i = 0; i < t; ++i)
21 printf("%d;", answer[i]);
22 printf("] (* %d *)\n", best_so_far);
23 }
24
25 #define DO(i, j, k, cst) \
26 if (k < n) { \
27 int c = A[i] + A[j] + cst; \
28 if (c < A[k]) { \
29 A[k] = c; \
30 changed = 1; \
31 } \
32 }
33
34 #define DO3(i, j, l, k, cst) \
35 if (k < n) { \
36 int c = A[i] + A[j] + A[l] + cst; \
37 if (c < A[k]) { \
38 A[k] = c; \
39 changed = 1; \
40 } \
41 }
42
43 static int optimize(int n, int *A)
44 {
45 int i, j, k, changed, cst, cstmax;
46
47 do {
48 changed = 0;
49 for (i = 0; i < n; ++i) {
50 k = i + i;
51 DO(i, i, k, sqcost);
52 }
53
54 for (i = 0; i < n; ++i) {
55 for (j = 0; j <= i; ++j) {
56 k = i + j;
57 DO(i, j, k, mulcost);
58 k = i - j;
59 DO(i, j, k, mulcost);
60
61 k = i + j;
62 DO3(i, j, i - j, k, reflcost);
63 }
64 }
65
66 } while (changed);
67
68 cst = cstmax = 0;
69 for (i = 0; i < n; ++i) {
70 cst += A[i];
71 if (A[i] > cstmax) cstmax = A[i];
72 }
73 /* return cstmax; */
74 return cst;
75 }
76
77 static void search(int n, int t, int *A, int *B, int depth)
78 {
79 if (depth == 0) {
80 int i, tc;
81 for (i = 0; i < n; ++i)
82 A[i] = INFTY;
83 A[0] = 0; /* always free */
84 for (i = 1; i <= t; ++i)
85 A[B[-i]] = ldcost;
86
87 tc = optimize(n, A);
88 if (tc < best_so_far) {
89 best_so_far = tc;
90 for (i = 1; i <= t; ++i)
91 answer[t - i] = B[-i];
92 if (verbose)
93 print_answer(n, t);
94 }
95 } else {
96 for (B[0] = B[-1] + 1; B[0] < n; ++B[0])
97 search(n, t, A, B + 1, depth - 1);
98 }
99 }
100
101 static void doit(int n, int t)
102 {
103 int *A;
104 int *B;
105
106 A = malloc(n * sizeof(int));
107 B = malloc((t + 1) * sizeof(int));
108 answer = malloc(t * sizeof(int));
109
110 B[0] = 0;
111 best_so_far = INFTY;
112 search(n, t, A, B + 1, t);
113
114 print_answer(n, t);
115
116 free(A); free(B); free(answer);
117 }
118
119 int main(int argc, char *argv[])
120 {
121 int n = 32;
122 int t = 3;
123 int all;
124 int ch;
125
126 verbose = 0;
127 all = 0;
128 while ((ch = getopt(argc, argv, "n:t:m:l:r:s:va")) != -1) {
129 switch (ch) {
130 case 'n':
131 n = atoi(optarg);
132 break;
133 case 't':
134 t = atoi(optarg);
135 break;
136 case 'm':
137 mulcost = atoi(optarg);
138 break;
139 case 'l':
140 ldcost = atoi(optarg);
141 break;
142 case 's':
143 sqcost = atoi(optarg);
144 break;
145 case 'r':
146 reflcost = atoi(optarg);
147 break;
148 case 'v':
149 ++verbose;
150 break;
151 case 'a':
152 ++all;
153 break;
154 case '?':
155 fprintf(stderr, "use the source\n");
156 exit(1);
157 }
158 }
159
160 if (all) {
161 for (n = 4; n <= 64; n *= 2) {
162 int n1 = n - 1; if (n1 > 7) n1 = 7;
163 for (t = 1; t <= n1; ++t)
164 doit(n, t);
165 }
166 } else {
167 doit(n, t);
168 }
169
170 return 0;
171 }