?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
barvinok.cc: stop using Polyhedron2Param_SimplifiedDomain
[barvinok.git] / test_approx.c
blobef9472ea2c97827e50b00e0b90e5466265ddfa42
1 #include <limits.h>
2 #include <sys/times.h>
3 #include <barvinok/barvinok.h>
4 #include "verify.h"
5
6 struct {
7 int sign;
8 int method;
9 int flags;
10 } methods[] = {
11 { BV_APPROX_SIGN_NONE, BV_APPROX_NONE, 0 },
12 { BV_APPROX_SIGN_APPROX, BV_APPROX_DROP, 0 },
13 { BV_APPROX_SIGN_APPROX, BV_APPROX_VOLUME, 0 },
14 { BV_APPROX_SIGN_APPROX, BV_APPROX_SCALE, 0 },
15 { BV_APPROX_SIGN_APPROX, BV_APPROX_SCALE, BV_APPROX_SCALE_CHAMBER },
16 { BV_APPROX_SIGN_APPROX, BV_APPROX_SCALE, BV_APPROX_SCALE_FAST },
17 { BV_APPROX_SIGN_APPROX, BV_APPROX_SCALE, BV_APPROX_SCALE_FAST | BV_APPROX_SCALE_CHAMBER },
18 { BV_APPROX_SIGN_LOWER, BV_APPROX_DROP, 0 },
19 { BV_APPROX_SIGN_LOWER, BV_APPROX_VOLUME, 0 },
20 { BV_APPROX_SIGN_LOWER, BV_APPROX_SCALE, 0 },
21 { BV_APPROX_SIGN_LOWER, BV_APPROX_SCALE, BV_APPROX_SCALE_CHAMBER },
22 { BV_APPROX_SIGN_LOWER, BV_APPROX_SCALE, BV_APPROX_SCALE_FAST },
23 { BV_APPROX_SIGN_LOWER, BV_APPROX_SCALE, BV_APPROX_SCALE_FAST | BV_APPROX_SCALE_CHAMBER },
24 { BV_APPROX_SIGN_LOWER, BV_APPROX_SCALE, BV_APPROX_SCALE_NARROW },
25 { BV_APPROX_SIGN_LOWER, BV_APPROX_SCALE, BV_APPROX_SCALE_NARROW | BV_APPROX_SCALE_CHAMBER},
26 { BV_APPROX_SIGN_LOWER, BV_APPROX_SCALE, BV_APPROX_SCALE_FAST | BV_APPROX_SCALE_NARROW },
27 { BV_APPROX_SIGN_LOWER, BV_APPROX_SCALE, BV_APPROX_SCALE_FAST | BV_APPROX_SCALE_NARROW | BV_APPROX_SCALE_CHAMBER },
28 { BV_APPROX_SIGN_LOWER, BV_APPROX_SCALE, BV_APPROX_SCALE_NARROW2 },
29 { BV_APPROX_SIGN_LOWER, BV_APPROX_SCALE, BV_APPROX_SCALE_NARROW2 | BV_APPROX_SCALE_CHAMBER },
30 { BV_APPROX_SIGN_LOWER, BV_APPROX_SCALE, BV_APPROX_SCALE_FAST | BV_APPROX_SCALE_NARROW2 },
31 { BV_APPROX_SIGN_LOWER, BV_APPROX_SCALE, BV_APPROX_SCALE_FAST | BV_APPROX_SCALE_NARROW2 | BV_APPROX_SCALE_CHAMBER },
32 { BV_APPROX_SIGN_UPPER, BV_APPROX_DROP, 0 },
33 { BV_APPROX_SIGN_UPPER, BV_APPROX_VOLUME, 0 },
34 { BV_APPROX_SIGN_UPPER, BV_APPROX_SCALE, 0 },
35 { BV_APPROX_SIGN_UPPER, BV_APPROX_SCALE, BV_APPROX_SCALE_CHAMBER },
36 { BV_APPROX_SIGN_UPPER, BV_APPROX_SCALE, BV_APPROX_SCALE_FAST },
37 { BV_APPROX_SIGN_UPPER, BV_APPROX_SCALE, BV_APPROX_SCALE_FAST | BV_APPROX_SCALE_CHAMBER },
38 { BV_APPROX_SIGN_UPPER, BV_APPROX_SCALE, BV_APPROX_SCALE_NARROW },
39 { BV_APPROX_SIGN_UPPER, BV_APPROX_SCALE, BV_APPROX_SCALE_NARROW | BV_APPROX_SCALE_CHAMBER },
40 { BV_APPROX_SIGN_UPPER, BV_APPROX_SCALE, BV_APPROX_SCALE_FAST | BV_APPROX_SCALE_NARROW },
41 { BV_APPROX_SIGN_UPPER, BV_APPROX_SCALE, BV_APPROX_SCALE_FAST | BV_APPROX_SCALE_NARROW | BV_APPROX_SCALE_CHAMBER },
42 { BV_APPROX_SIGN_UPPER, BV_APPROX_SCALE, BV_APPROX_SCALE_NARROW2 },
43 { BV_APPROX_SIGN_UPPER, BV_APPROX_SCALE, BV_APPROX_SCALE_NARROW2 | BV_APPROX_SCALE_CHAMBER },
44 { BV_APPROX_SIGN_UPPER, BV_APPROX_SCALE, BV_APPROX_SCALE_FAST | BV_APPROX_SCALE_NARROW2 },
45 { BV_APPROX_SIGN_UPPER, BV_APPROX_SCALE, BV_APPROX_SCALE_FAST | BV_APPROX_SCALE_NARROW2 | BV_APPROX_SCALE_CHAMBER },
46 };
47
48 #define nr_methods (sizeof(methods)/sizeof(*methods))
49
50 struct argp_option argp_options[] = {
51 { "quiet", 'q' },
52 { 0 }
53 };
54
55 struct options {
56 int quiet;
57 struct verify_options verify;
58 };
59
60 static error_t parse_opt(int key, char *arg, struct argp_state *state)
61 {
62 struct options *options = (struct options*) state->input;
63
64 switch (key) {
65 case ARGP_KEY_INIT:
66 state->child_inputs[0] = options->verify.barvinok;
67 state->child_inputs[1] = &options->verify;
68 options->quiet = 0;
69 break;
70 case 'q':
71 options->quiet = 1;
72 break;
73 default:
74 return ARGP_ERR_UNKNOWN;
75 }
76 return 0;
77 }
78
79 struct result_data {
80 Value n;
81 double RE_sum[nr_methods];
82
83 clock_t ticks[nr_methods];
84 size_t size[nr_methods];
85 };
86
87 void result_data_init(struct result_data *result)
88 {
89 int i;
90 for (i = 0; i < nr_methods; ++i) {
91 result->RE_sum[i] = 0;
92 result->ticks[i] = 0;
93 result->size[i] = 0;
94 }
95 value_init(result->n);
96 }
97
98 void result_data_clear(struct result_data *result)
99 {
100 int i;
101 value_clear(result->n);
102 }
103
104 void result_data_print(struct result_data *result, int n)
105 {
106 int i;
107
108 fprintf(stderr, "%d", result->ticks[0]/n);
109 for (i = 1; i < nr_methods; ++i)
110 fprintf(stderr, ", %d", result->ticks[i]/n);
111 fprintf(stderr, "\n");
112
113 fprintf(stderr, "%d", result->size[0]/n);
114 for (i = 1; i < nr_methods; ++i)
115 fprintf(stderr, ", %d", result->size[i]/n);
116 fprintf(stderr, "\n");
117
118 fprintf(stderr, "%g\n", VALUE_TO_DOUBLE(result->n));
119 fprintf(stderr, "%g", result->RE_sum[0]/VALUE_TO_DOUBLE(result->n));
120 for (i = 1; i < nr_methods; ++i)
121 fprintf(stderr, ", %g", result->RE_sum[i]/VALUE_TO_DOUBLE(result->n));
122 fprintf(stderr, "\n");
123 }
124
125 struct test_approx_data {
126 struct check_poly_data cp;
127 evalue **EP;
128 struct result_data *result;
129 };
130
131 static void eval(const evalue *EP, Value *z, int sign, Value *v)
132 {
133 evalue *res;
134
135 res = evalue_eval(EP, z);
136 if (sign == BV_APPROX_SIGN_LOWER)
137 mpz_cdiv_q(*v, res->x.n, res->d);
138 else if (sign == BV_APPROX_SIGN_UPPER)
139 mpz_fdiv_q(*v, res->x.n, res->d);
140 else if (sign == BV_APPROX_SIGN_APPROX)
141 mpz_tdiv_q(*v, res->x.n, res->d);
142 else {
143 assert(value_one_p(res->d));
144 value_assign(*v, res->x.n);
145 }
146 free_evalue_refs(res);
147 free(res);
148 }
149
150 static int test_approx(const struct check_poly_data *data, int nparam, Value *z,
151 const struct verify_options *options)
152 {
153 struct test_approx_data* ta_data = (struct test_approx_data*) data;
154 Value exact, approx;
155 int i;
156
157 value_init(exact);
158 value_init(approx);
159
160 eval(ta_data->EP[0], z, BV_APPROX_SIGN_NONE, &exact);
161
162 /*
163 value_print(stderr, VALUE_FMT, exact);
164 */
165
166 value_increment(ta_data->result->n, ta_data->result->n);
167 for (i = 1; i < nr_methods; ++i) {
168 double error;
169 eval(ta_data->EP[i], z, methods[i].sign, &approx);
170 /*
171 fprintf(stderr, ", ");
172 value_print(stderr, VALUE_FMT, approx);
173 */
174 if (methods[i].sign == BV_APPROX_SIGN_LOWER)
175 assert(value_le(approx, exact));
176 if (methods[i].sign == BV_APPROX_SIGN_UPPER)
177 assert(value_ge(approx, exact));
178 value_subtract(approx, approx, exact);
179 if (value_zero_p(exact))
180 error = abs(VALUE_TO_DOUBLE(approx));
181 else
182 error = abs(VALUE_TO_DOUBLE(approx)) / VALUE_TO_DOUBLE(exact);
183 ta_data->result->RE_sum[i] += error;
184 }
185
186 /*
187 fprintf(stderr, "\n");
188 */
189
190 value_clear(exact);
191 value_clear(approx);
192 return 1;
193 }
194
195 static void test(Polyhedron *P, Polyhedron *C, evalue **EP,
196 struct result_data *result,
197 struct verify_options *options)
198 {
199 Polyhedron *CS;
200 Vector *p;
201 unsigned nparam = C->Dimension;
202 struct test_approx_data data;
203
204 CS = check_poly_context_scan(P, &C, C->Dimension, options);
205
206 p = Vector_Alloc(P->Dimension+2);
207 value_set_si(p->p[P->Dimension+1], 1);
208
209 check_poly_init(C, options);
210
211 data.cp.z = p->p;
212 data.cp.check = test_approx;
213 data.EP = EP;
214 data.result = result;
215 check_poly(CS, &data.cp, nparam, 0, p->p+P->Dimension-nparam+1,
216 options);
217 if (!options->print_all)
218 printf("\n");
219
220 Vector_Free(p);
221 if (CS) {
222 Domain_Free(CS);
223 Domain_Free(C);
224 }
225 }
226
227 void Matrix_File_Read_Input(FILE *in, Matrix *Mat)
228 {
229 Value *p;
230 int i,j,n;
231 char *c, s[1024],str[1024];
232
233 p = Mat->p_Init;
234 for (i=0;i<Mat->NbRows;i++) {
235 do {
236 c = fgets(s, 1024, in);
237 while(isspace(*c) && *c!='\n')
238 ++c;
239 } while(c && (*c =='#' || *c== '\n'));
240
241 if (!c) {
242 errormsg1( "Matrix_Read", "baddim", "not enough rows" );
243 break;
244 }
245 for (j=0;j<Mat->NbColumns;j++) {
246 if(!c || *c=='\n' || *c=='#') {
247 errormsg1("Matrix_Read", "baddim", "not enough columns");
248 break;
249 }
250 if (sscanf(c,"%s%n",str,&n) == 0) {
251 errormsg1( "Matrix_Read", "baddim", "not enough columns" );
252 break;
253 }
254 value_read(*(p++),str);
255 c += n;
256 }
257 }
258 } /* Matrix_Read_Input */
259
260 /*
261 * Read the contents of the matrix 'Mat' from standard input.
262 * A '#' in the first column is a comment line
263 */
264 Matrix *Matrix_File_Read(FILE *in)
265 {
266 Matrix *Mat;
267 unsigned NbRows, NbColumns;
268 char s[1024];
269
270 fgets(s, 1024, in);
271 while ((*s=='#' || *s=='\n') ||
272 (sscanf(s, "%d %d", &NbRows, &NbColumns)<2))
273 fgets(s, 1024, in);
274 Mat = Matrix_Alloc(NbRows,NbColumns);
275 if(!Mat) {
276 errormsg1("Matrix_Read", "outofmem", "out of memory space");
277 return(NULL);
278 }
279 Matrix_File_Read_Input(in, Mat);
280 return Mat;
281 } /* Matrix_Read */
282
283 void handle(FILE *in, struct result_data *result, struct verify_options *options)
284 {
285 int i;
286 Polyhedron *A, *C;
287 Matrix *M;
288 char **param_name;
289 evalue *EP[nr_methods];
290
291 M = Matrix_File_Read(in);
292 A = Constraints2Polyhedron(M, options->barvinok->MaxRays);
293 Matrix_Free(M);
294 M = Matrix_File_Read(in);
295 C = Constraints2Polyhedron(M, options->barvinok->MaxRays);
296 Matrix_Free(M);
297 param_name = Read_ParamNames(in, C->Dimension);
298
299 for (i = 0; i < nr_methods; ++i) {
300 struct tms st_cpu;
301 struct tms en_cpu;
302 options->barvinok->polynomial_approximation = methods[i].sign;
303 options->barvinok->approximation_method = methods[i].method;
304 options->barvinok->scale_flags = methods[i].flags;
305
306 times(&st_cpu);
307 EP[i] = barvinok_enumerate_with_options(A, C, options->barvinok);
308 times(&en_cpu);
309 result->ticks[i] = en_cpu.tms_utime - st_cpu.tms_utime;
310 /*
311 print_evalue(stdout, EP[i], param_name);
312 */
313 }
314 for (i = 0; i < nr_methods; ++i)
315 result->size[i] = evalue_size(EP[i])/4;
316 test(A, C, EP, result, options);
317 for (i = 0; i < nr_methods; ++i) {
318 free_evalue_refs(EP[i]);
319 free(EP[i]);
320 }
321
322 Free_ParamNames(param_name, C->Dimension);
323 Polyhedron_Free(A);
324 Polyhedron_Free(C);
325 }
326
327 int main(int argc, char **argv)
328 {
329 struct barvinok_options *bv_options = barvinok_options_new_with_defaults();
330 char path[PATH_MAX+1];
331 struct result_data all_result;
332 int n = 0;
333 static struct argp_child argp_children[] = {
334 { &barvinok_argp, 0, 0, 0 },
335 { &verify_argp, 0, "verification", BV_GRP_LAST+1 },
336 { 0 }
337 };
338 static struct argp argp = { argp_options, parse_opt, 0, 0, argp_children };
339 struct options options;
340
341 options.verify.barvinok = bv_options;
342 argp_parse(&argp, argc, argv, 0, 0, &options);
343
344 if (options.verify.M == INT_MIN)
345 options.verify.M = 100;
346 if (options.verify.m == INT_MAX)
347 options.verify.m = -100;
348
349 result_data_init(&all_result);
350
351 while (fgets(path, sizeof(path), stdin)) {
352 struct result_data result;
353 FILE *in;
354 int i;
355
356 ++n;
357 result_data_init(&result);
358 fprintf(stderr, "%s", path);
359 *strchr(path, '\n') = '\0';
360 in = fopen(path, "r");
361 assert(in);
362 handle(in, &result, &options.verify);
363 fclose(in);
364
365 if (!options.quiet)
366 result_data_print(&result, 1);
367
368 value_addto(all_result.n, all_result.n, result.n);
369 for (i = 0; i < nr_methods; ++i) {
370 all_result.RE_sum[i] += result.RE_sum[i];
371 all_result.ticks[i] += result.ticks[i];
372 all_result.size[i] += result.size[i];
373 }
374
375 result_data_clear(&result);
376
377 if (!options.quiet) {
378 fprintf(stderr, "average\n");
379 result_data_print(&all_result, n);
380 }
381 }
382
383 result_data_clear(&all_result);
384
385 barvinok_options_free(bv_options);
386
387 return 0;
388 }
lattice point enumeration library