Line data Source code
1 : /* This is a suite of benchmarks that are relatively short, both in program
2 : size and execution time. It requires no input, and prints the execution
3 : time for each program, using the system- dependent routine Getclock,
4 : below, to find out the current CPU time. It does a rudimentary check to
5 : make sure each program gets the right output. These programs were
6 : gathered by John Hennessy and modified by Peter Nye. */
7 :
8 : #include <stdio.h>
9 : #include <stdlib.h>
10 : #include <time.h>
11 :
12 : #define nil 0
13 : #define false 0
14 : #define true 1
15 : #define bubblebase 1.61
16 : #define dnfbase 3.5
17 : #define permbase 1.75
18 : #define queensbase 1.83
19 : #define towersbase 2.39
20 : #define quickbase 1.92
21 : #define intmmbase 1.46
22 : #define treebase 2.5
23 : #define mmbase 0.73
24 : #define fpmmbase 2.92
25 : #define puzzlebase 0.5
26 : #define fftbase 1.11
27 : #define fpfftbase 4.44
28 : /* Towers */
29 : #define maxcells 18
30 :
31 : /* Intmm, Mm */
32 : #define rowsize 400
33 :
34 : /* Puzzle */
35 : #define size 511
36 : #define classmax 3
37 : #define typemax 12
38 : #define d 8
39 :
40 : /* Bubble, Quick */
41 : #define sortelements 300000
42 : #define srtelements 10000
43 :
44 : /* fft */
45 : #define fftsize 256
46 : #define fftsize2 129
47 :
48 : /* Perm */
49 : #define permrange 13
50 :
51 : /* tree */
52 : struct node {
53 : struct node *left,*right;
54 : int val;
55 : };
56 :
57 : /* Towers */
58 : #define stackrange 3
59 : #define discs 17
60 : struct element {
61 : int discsize;
62 : int next;
63 : };
64 :
65 : /* FFT */
66 : struct complex { float rp, ip; };
67 :
68 : float fixed,floated;
69 :
70 : /* global */
71 : int timer;
72 : int xtimes[11];
73 : int seed;
74 :
75 : /* Perm */
76 : int permarray[permrange+1];
77 : int pctr;
78 :
79 : /* tree */
80 : struct node *tree;
81 :
82 : /* Towers */
83 : int stack[stackrange+1];
84 : struct element cellspace[maxcells+1];
85 : int freelist, movesdone;
86 :
87 : /* Intmm, Mm */
88 : int ima[rowsize+1][rowsize+1],
89 : imb[rowsize+1][rowsize+1],
90 : imr[rowsize+1][rowsize+1];
91 : float rma[rowsize+1][rowsize+1],
92 : rmb[rowsize+1][rowsize+1],
93 : rmr[rowsize+1][rowsize+1];
94 :
95 : /* Puzzle */
96 : int piececount[classmax+1],
97 : class[typemax+1],
98 : piecemax[typemax+1],
99 : puzzl[size+1],
100 : p[typemax+1][size+1],
101 : n,
102 : kount;
103 :
104 : /* Bubble, Quick */
105 : int sortlist[sortelements+1],
106 : biggest, littlest,
107 : top;
108 :
109 : /* FFT */
110 : struct complex z[fftsize+1], w[fftsize+1], e[fftsize2+1];
111 : float zr, zi;
112 :
113 : /* global procedures */
114 :
115 20 : int Getclock()
116 : {
117 : /* time in milliseconds. */
118 20 : return 1000*clock() / (double)CLOCKS_PER_SEC;
119 : }
120 :
121 5 : void Initrand () {
122 5 : seed = 74755;
123 5 : }
124 :
125 1250000 : int Rand () {
126 1250000 : seed = (seed * 1309 + 13849) & 65535;
127 1250000 : return (seed);
128 : }
129 :
130 :
131 :
132 : /* Permutation program, heavily recursive, written by Denny Brown. */
133 :
134 21772794 : void Swap (a,b) int *a, *b; {
135 : int t;
136 21772794 : t = *a; *a = *b; *b = t;
137 21772794 : }
138 :
139 3 : void Initialize () {
140 : int i;
141 24 : for ( i = 1; i <= 7; i++ ) {
142 21 : permarray[i]=i-1;
143 : }
144 3 : }
145 :
146 18705903 : void Permute (n) int n; {
147 : int k;
148 18705903 : pctr = pctr + 1;
149 18705903 : if ( n!=1 ) {
150 7819503 : Permute(n-1);
151 18705900 : for ( k = n-1; k >= 1; k-- ) {
152 10886397 : Swap(&permarray[n],&permarray[k]);
153 10886397 : Permute(n-1);
154 10886397 : Swap(&permarray[n],&permarray[k]);
155 : }
156 : }
157 18705903 : }
158 :
159 1 : void Perm () {
160 : int i;
161 1 : pctr = 0;
162 4 : for ( i = 1; i <= 3; i++ ) {
163 3 : Initialize();
164 3 : Permute(permrange-3);
165 : }
166 1 : if ( pctr != 18705903 ) {
167 0 : printf(" Error in Perm. %d\n", pctr);
168 : }
169 1 : }
170 :
171 :
172 :
173 : /* Program to Solve the Towers of Hanoi */
174 :
175 0 : void Error (emsg) char *emsg; {
176 0 : printf(" Error in Towers: %s\n",emsg);
177 0 : }
178 :
179 300 : void Makenull (int s) {
180 300 : stack[s]=0;
181 300 : }
182 :
183 13108800 : int Getelement () {
184 13108800 : int temp = 0;
185 13108800 : if ( freelist>0 ) {
186 13108800 : temp = freelist;
187 13108800 : freelist = cellspace[freelist].next;
188 : } else {
189 0 : Error("out of space ");
190 : }
191 13108800 : return (temp);
192 : }
193 :
194 13108800 : void Push(i,s) int i, s; {
195 : int errorfound, localel;
196 13108800 : errorfound=false;
197 13108800 : if ( stack[s] > 0 ) {
198 13032100 : if ( cellspace[stack[s]].discsize<=i ) {
199 0 : errorfound=true;
200 0 : Error("disc size error");
201 : }
202 : }
203 13108800 : if ( ! errorfound ) {
204 13108800 : localel=Getelement();
205 13108800 : cellspace[localel].next=stack[s];
206 13108800 : stack[s]=localel;
207 13108800 : cellspace[localel].discsize=i;
208 : }
209 13108800 : }
210 :
211 100 : void Init (s,n) int s, n; {
212 : int discctr;
213 100 : Makenull(s);
214 1800 : for ( discctr = n; discctr >= 1; discctr-- ) {
215 1700 : Push(discctr,s);
216 : }
217 100 : }
218 :
219 13107100 : int Pop (s) int s; {
220 : int temp, temp1;
221 13107100 : if ( stack[s] > 0 ) {
222 13107100 : temp1 = cellspace[stack[s]].discsize;
223 13107100 : temp = cellspace[stack[s]].next;
224 13107100 : cellspace[stack[s]].next=freelist;
225 13107100 : freelist=stack[s];
226 13107100 : stack[s]=temp;
227 13107100 : return (temp1);
228 : } else {
229 0 : Error("nothing to pop ");
230 0 : return (-1);
231 : }
232 : }
233 :
234 13107100 : void Move (s1,s2) int s1, s2; {
235 13107100 : Push(Pop(s1),s2);
236 13107100 : movesdone=movesdone+1;
237 13107100 : }
238 :
239 13107100 : void tower(i,j,k) int i,j,k; {
240 : int other;
241 13107100 : if ( k==1 ) {
242 6553600 : Move(i,j);
243 : } else {
244 6553500 : other=6-i-j;
245 6553500 : tower(i,other,k-1);
246 6553500 : Move(i,j);
247 6553500 : tower(other,j,k-1);
248 : }
249 13107100 : }
250 :
251 :
252 1 : void Towers () {
253 : int i;
254 : int j;
255 101 : for (j = 0; j < 100; ++j) {
256 1900 : for ( i=1; i <= maxcells; i++ ) {
257 1800 : cellspace[i].next=i-1;
258 : }
259 100 : freelist=maxcells;
260 100 : Init(1,discs);
261 100 : Makenull(2);
262 100 : Makenull(3);
263 100 : movesdone=0;
264 100 : tower(1,2,discs);
265 100 : if ( movesdone != 131071 ) {
266 0 : printf (" Error in Towers: %d\n", movesdone);
267 : }
268 : }
269 1 : }
270 :
271 :
272 : /* The eight queens problem, solved 50 times. */
273 :
274 11300000 : void Try(i, q, a, b, c, x) int i, *q, a[], b[], c[], x[]; {
275 : int j;
276 11300000 : j = 0;
277 11300000 : *q = false;
278 98900000 : while ( (! *q) && (j != 8) ) {
279 87600000 : j = j + 1;
280 87600000 : *q = false;
281 87600000 : if ( b[j] && a[i+j] && c[i-j+7] ) {
282 11300000 : x[i] = j;
283 11300000 : b[j] = false;
284 11300000 : a[i+j] = false;
285 11300000 : c[i-j+7] = false;
286 11300000 : if ( i < 8 ) {
287 11200000 : Try(i+1,q,a,b,c,x);
288 11200000 : if ( ! *q ) {
289 10500000 : b[j] = true;
290 10500000 : a[i+j] = true;
291 10500000 : c[i-j+7] = true;
292 : }
293 : } else {
294 100000 : *q = true;
295 : }
296 : }
297 : }
298 11300000 : }
299 :
300 100000 : void Doit () {
301 : int i,q;
302 : int a[9], b[17], c[15], x[9];
303 100000 : i = 0 - 7;
304 2500000 : while ( i <= 16 ) {
305 2400000 : if ( (i >= 1) && (i <= 8) ) a[i] = true;
306 2400000 : if ( i >= 2 ) b[i] = true;
307 2400000 : if ( i <= 7 ) c[i+7] = true;
308 2400000 : i = i + 1;
309 : }
310 :
311 100000 : Try(1, &q, b, a, c, x);
312 100000 : if ( ! q ) {
313 0 : printf (" Error in Queens.\n");
314 : }
315 100000 : }
316 :
317 1 : void Queens () {
318 : int i;
319 100001 : for ( i = 1; i <= 100000; i++ ) Doit();
320 1 : }
321 :
322 : /* Multiplies two integer matrices. */
323 :
324 2 : void Initmatrix ( m ) int m[rowsize+1][rowsize+1]; {
325 : int temp, i, j;
326 802 : for ( i = 1; i <= rowsize; i++ ) {
327 320800 : for ( j = 1; j <= rowsize; j++ ) {
328 320000 : temp = Rand();
329 320000 : m[i][j] = temp - (temp/120)*120 - 60;
330 : }
331 : }
332 2 : }
333 :
334 : /* computes the inner product of A[row,*] and B[*,column] */
335 160000 : void Innerproduct( result,a,b, row,column)
336 : int *result,a[rowsize+1][rowsize+1],b[rowsize+1][rowsize+1],row,column;
337 : {
338 : int i;
339 160000 : *result = 0;
340 64160000 : for(i = 1; i <= rowsize; i++ ) {
341 64000000 : *result = *result+a[row][i]*b[i][column];
342 : }
343 160000 : }
344 :
345 1 : void Intmm () {
346 : int i, j;
347 1 : Initrand();
348 1 : Initmatrix (ima);
349 1 : Initmatrix (imb);
350 401 : for ( i = 1; i <= rowsize; i++ ) {
351 160400 : for ( j = 1; j <= rowsize; j++ ) {
352 160000 : Innerproduct(&imr[i][j],ima,imb,i,j);
353 : }
354 : }
355 1 : }
356 :
357 : /* Multiplies two real matrices. */
358 :
359 2 : void rInitmatrix ( m ) float m[rowsize+1][rowsize+1]; {
360 : int temp, i, j;
361 802 : for ( i = 1; i <= rowsize; i++ ) {
362 320800 : for ( j = 1; j <= rowsize; j++ ) {
363 320000 : temp = Rand();
364 320000 : m[i][j] = (temp - (temp/120)*120 - 60)/3;
365 : }
366 : }
367 2 : }
368 :
369 : /* computes the inner product of A[row,*] and B[*,column] */
370 160000 : void rInnerproduct(result,a,b,row,column)
371 : float *result,a[rowsize+1][rowsize+1],b[rowsize+1][rowsize+1];
372 : int row,column;
373 : {
374 : int i;
375 160000 : *result = 0.0;
376 64160000 : for (i = 1; i<=rowsize; i++) {
377 64000000 : *result = *result+a[row][i]*b[i][column];
378 : }
379 160000 : }
380 :
381 1 : void Mm () {
382 : int i, j;
383 1 : Initrand();
384 1 : rInitmatrix (rma);
385 1 : rInitmatrix (rmb);
386 401 : for ( i = 1; i <= rowsize; i++ ) {
387 160400 : for ( j = 1; j <= rowsize; j++ ) {
388 160000 : rInnerproduct(&rmr[i][j],rma,rmb,i,j);
389 : }
390 : }
391 1 : }
392 :
393 :
394 :
395 : /* A compute-bound program from Forest Baskett. */
396 :
397 4601700 : int Fit (i, j) int i, j; {
398 : int k;
399 162272100 : for ( k = 0; k <= piecemax[i]; k++ ) {
400 161670600 : if ( p[i][k] ) if ( puzzl[j+k] ) return (false);
401 : }
402 601500 : return (true);
403 : }
404 :
405 601500 : int Place (i, j) int i,j; {
406 : int k;
407 33929700 : for ( k = 0; k <= piecemax[i]; k++ ) {
408 33328200 : if ( p[i][k] ) puzzl[j+k] = true;
409 : }
410 601500 : piececount[class[i]] = piececount[class[i]] - 1;
411 6906900 : for ( k = j; k <= size; k++ ) {
412 6906600 : if ( ! puzzl[k] ) {
413 601200 : return (k);
414 : }
415 : }
416 300 : return (0);
417 : }
418 :
419 596100 : void Remove (i, j) int i, j; {
420 : int k;
421 33593400 : for ( k = 0; k <= piecemax[i]; k++ ) {
422 32997300 : if ( p[i][k] ) puzzl[j+k] = false;
423 : }
424 596100 : piececount[class[i]] = piececount[class[i]] + 1;
425 596100 : }
426 :
427 601500 : int Trial (j) int j; {
428 : int i, k;
429 601500 : kount = kount + 1;
430 8371500 : for ( i = 0; i <= typemax; i++ ) {
431 7775100 : if ( piececount[class[i]] != 0 ) {
432 4601400 : if ( Fit (i, j) ) {
433 601200 : k = Place (i, j);
434 601200 : if ( Trial(k) || (k == 0) ) {
435 5100 : return (true);
436 : } else {
437 596100 : Remove (i, j);
438 : }
439 : }
440 : }
441 : }
442 596400 : return (false);
443 : }
444 :
445 1 : void Puzzle () {
446 : int i, j, k, m, ii;
447 301 : for (ii = 0; ii < 300; ++ii) {
448 :
449 153900 : for ( m = 0; m <= size; m++ )
450 153600 : puzzl[m] = true;
451 46800 : for( i = 1; i <= 5; i++ )for( j = 1; j <= 5; j++ )for( k = 1; k <= 5; k++ )
452 37500 : puzzl[i+d*(j+d*k)] = false;
453 2001000 : for( i = 0; i <= typemax; i++ )for( m = 0; m<= size; m++ )
454 1996800 : p[i][m] = false;
455 6300 : for( i = 0; i <= 3; i++ )for( j = 0; j <= 1; j++ )for( k = 0; k <= 0; k++ )
456 2400 : p[0][i+d*(j+d*k)] = true;
457 300 : class[0] = 0;
458 300 : piecemax[0] = 3+d*1+d*d*0;
459 3900 : for( i = 0; i <= 1; i++ )for( j = 0; j <= 0; j++ )for( k = 0; k <= 3; k++ )
460 2400 : p[1][i+d*(j+d*k)] = true;
461 300 : class[1] = 0;
462 300 : piecemax[1] = 1+d*0+d*d*3;
463 4200 : for( i = 0; i <= 0; i++ )for( j = 0; j <= 3; j++ )for( k = 0; k <= 1; k++ )
464 2400 : p[2][i+d*(j+d*k)] = true;
465 300 : class[2] = 0;
466 300 : piecemax[2] = 0+d*3+d*d*1;
467 5700 : for( i = 0; i <= 1; i++ )for( j = 0; j <= 3; j++ )for( k = 0; k <= 0; k++ )
468 2400 : p[3][i+d*(j+d*k)] = true;
469 300 : class[3] = 0;
470 300 : piecemax[3] = 1+d*3+d*d*0;
471 5100 : for( i = 0; i <= 3; i++ )for( j = 0; j <= 0; j++ )for( k = 0; k <= 1; k++ )
472 2400 : p[4][i+d*(j+d*k)] = true;
473 300 : class[4] = 0;
474 300 : piecemax[4] = 3+d*0+d*d*1;
475 3600 : for( i = 0; i <= 0; i++ )for( j = 0; j <= 1; j++ )for( k = 0; k <= 3; k++ )
476 2400 : p[5][i+d*(j+d*k)] = true;
477 300 : class[5] = 0;
478 300 : piecemax[5] = 0+d*1+d*d*3;
479 3000 : for( i = 0; i <= 2; i++ )for( j = 0; j <= 0; j++ )for( k = 0; k <= 0; k++ )
480 900 : p[6][i+d*(j+d*k)] = true;
481 300 : class[6] = 1;
482 300 : piecemax[6] = 2+d*0+d*d*0;
483 2400 : for( i = 0; i <= 0; i++ )for( j = 0; j <= 2; j++ )for( k = 0; k <= 0; k++ )
484 900 : p[7][i+d*(j+d*k)] = true;
485 300 : class[7] = 1;
486 300 : piecemax[7] = 0+d*2+d*d*0;
487 1800 : for( i = 0; i <= 0; i++ )for( j = 0; j <= 0; j++ )for( k = 0; k <= 2; k++ )
488 900 : p[8][i+d*(j+d*k)] = true;
489 300 : class[8] = 1;
490 300 : piecemax[8] = 0+d*0+d*d*2;
491 3300 : for( i = 0; i <= 1; i++ )for( j = 0; j <= 1; j++ )for( k = 0; k <= 0; k++ )
492 1200 : p[9][i+d*(j+d*k)] = true;
493 300 : class[9] = 2;
494 300 : piecemax[9] = 1+d*1+d*d*0;
495 2700 : for( i = 0; i <= 1; i++ )for( j = 0; j <= 0; j++ )for( k = 0; k <= 1; k++ )
496 1200 : p[10][i+d*(j+d*k)] = true;
497 300 : class[10] = 2;
498 300 : piecemax[10] = 1+d*0+d*d*1;
499 2400 : for( i = 0; i <= 0; i++ )for( j = 0; j <= 1; j++ )for( k = 0; k <= 1; k++ )
500 1200 : p[11][i+d*(j+d*k)] = true;
501 300 : class[11] = 2;
502 300 : piecemax[11] = 0+d*1+d*d*1;
503 4500 : for( i = 0; i <= 1; i++ )for( j = 0; j <= 1; j++ )for( k = 0; k <= 1; k++ )
504 2400 : p[12][i+d*(j+d*k)] = true;
505 300 : class[12] = 3;
506 300 : piecemax[12] = 1+d*1+d*d*1;
507 300 : piececount[0] = 13;
508 300 : piececount[1] = 3;
509 300 : piececount[2] = 1;
510 300 : piececount[3] = 1;
511 300 : m = 1+d*(1+d*1);
512 300 : kount = 0;
513 300 : if ( Fit(0, m) ) {
514 300 : n = Place(0, m);
515 : } else {
516 0 : printf("Error1 in Puzzle\n");
517 : }
518 300 : if ( ! Trial(n) ) {
519 0 : printf ("Error2 in Puzzle.\n");
520 300 : } else if ( kount != 2005 ) {
521 0 : printf ( "Error3 in Puzzle.\n");
522 : }
523 : }
524 :
525 1 : }
526 :
527 : /* Sorts an array using quicksort */
528 :
529 1 : void Initarr() {
530 : int i, temp;
531 1 : Initrand();
532 1 : biggest = 0; littlest = 0;
533 300001 : for ( i = 1; i <= sortelements; i++ ) {
534 300000 : temp = Rand();
535 300000 : sortlist[i] = temp - (temp/100000)*100000 - 50000;
536 300000 : if ( sortlist[i] > biggest ) {
537 7 : biggest = sortlist[i];
538 299993 : } else if ( sortlist[i] < littlest ) {
539 4 : littlest = sortlist[i];
540 : }
541 : }
542 1 : }
543 :
544 : /* quicksort the array a from l to r */
545 244308 : void Quicksort( a,l,r) int a[], l, r; {
546 : int i,j,x,w;
547 :
548 244308 : i=l; j=r;
549 244308 : x=a[(l+r) / 2];
550 : do {
551 3550678 : while ( a[i]<x ) i = i+1;
552 3618962 : while ( x<a[j] ) j = j-1;
553 1472659 : if ( i<=j ) {
554 1428426 : w = a[i];
555 1428426 : a[i] = a[j];
556 1428426 : a[j] = w;
557 1428426 : i = i+1; j= j-1;
558 : }
559 1472659 : } while ( i<=j );
560 244308 : if ( l<j ) Quicksort(a,l,j);
561 244308 : if ( i<r ) Quicksort(a,i,r);
562 244308 : }
563 :
564 :
565 1 : void Quick () {
566 1 : Initarr();
567 1 : Quicksort(sortlist,1,sortelements);
568 1 : if ( (sortlist[1] != littlest) || (sortlist[sortelements] != biggest) ) {
569 0 : printf ( " Error in Quick.\n");
570 : }
571 1 : }
572 :
573 : /* Sorts an array using treesort */
574 :
575 1 : void tInitarr() {
576 : int i, temp;
577 1 : Initrand();
578 1 : biggest = 0; littlest = 0;
579 300001 : for ( i = 1; i <= sortelements; i++ ) {
580 300000 : temp = Rand();
581 300000 : sortlist[i] = temp - (temp/100000)*100000 - 50000;
582 300000 : if ( sortlist[i] > biggest ) {
583 7 : biggest = sortlist[i];
584 299993 : } else if ( sortlist[i] < littlest ) {
585 4 : littlest = sortlist[i];
586 : }
587 : }
588 1 : }
589 :
590 65535 : void CreateNode (t,n) struct node **t; int n; {
591 65535 : *t = (struct node *)malloc(sizeof(struct node));
592 65535 : (*t)->left = nil; (*t)->right = nil;
593 65535 : (*t)->val = n;
594 65535 : }
595 :
596 : /* insert n into tree */
597 5969660 : void Insert(n, t) int n; struct node *t; {
598 5969660 : if ( n > t->val ) {
599 3008286 : if ( t->left == nil ) {
600 32769 : CreateNode(&t->left,n);
601 : } else {
602 2975517 : Insert(n,t->left);
603 : }
604 2961374 : } else if ( n < t->val ) {
605 2726910 : if ( t->right == nil ) {
606 32766 : CreateNode(&t->right,n);
607 : } else {
608 2694144 : Insert(n,t->right);
609 : }
610 : }
611 5969660 : }
612 :
613 : /* check by inorder traversal */
614 1 : int Checktree(p) struct node *p; {
615 : int result;
616 1 : result = true;
617 1 : if ( p->left != nil ) {
618 1 : if ( p->left->val <= p->val ) {
619 0 : result=false;
620 : }
621 : } else {
622 0 : result = Checktree(p->left) && result;
623 : }
624 1 : if ( p->right != nil ) {
625 1 : if ( p->right->val >= p->val ) {
626 0 : result = false;
627 : }
628 : } else {
629 0 : result = Checktree(p->right) && result;
630 : }
631 1 : return( result);
632 : }
633 :
634 1 : void Trees() {
635 : int i;
636 1 : tInitarr();
637 1 : tree = (struct node *)malloc(sizeof(struct node));
638 1 : tree->left = nil; tree->right=nil; tree->val=sortlist[1];
639 300000 : for ( i = 2; i <= sortelements; i++ ) Insert(sortlist[i],tree);
640 1 : if ( ! Checktree(tree) ) printf ( " Error in Tree.\n");
641 1 : }
642 :
643 :
644 : /* Sorts an array using bubblesort */
645 :
646 1 : void bInitarr() {
647 : int i, temp;
648 1 : Initrand();
649 1 : biggest = 0; littlest = 0;
650 10001 : for ( i = 1; i <= srtelements; i++ ) {
651 10000 : temp = Rand();
652 10000 : sortlist[i] = temp - (temp/100000)*100000 - 50000;
653 10000 : if ( sortlist[i] > biggest ) {
654 6 : biggest = sortlist[i];
655 9994 : } else if ( sortlist[i] < littlest ) {
656 4 : littlest = sortlist[i];
657 : }
658 : }
659 1 : }
660 :
661 1 : void Bubble() {
662 : int i, j;
663 1 : bInitarr();
664 1 : top=srtelements;
665 :
666 10000 : while ( top>1 ) {
667 9999 : i=1;
668 50004999 : while ( i<top ) {
669 49995000 : if ( sortlist[i] > sortlist[i+1] ) {
670 25159018 : j = sortlist[i];
671 25159018 : sortlist[i] = sortlist[i+1];
672 25159018 : sortlist[i+1] = j;
673 : }
674 49995000 : i=i+1;
675 : }
676 9999 : top=top-1;
677 : }
678 1 : if ( (sortlist[1] != littlest) || (sortlist[srtelements] != biggest) ) {
679 0 : printf ( "Error3 in Bubble.\n");
680 : }
681 1 : }
682 :
683 :
684 : /* computes cos of x (x in radians) by an expansion */
685 25000 : float Cos (x) float x; {
686 : int i, factor;
687 : float result,power;
688 :
689 25000 : result = 1.0; factor = 1; power = x;
690 250000 : for ( i = 2; i <= 10; i++ ) {
691 225000 : factor = factor * i; power = power*x;
692 225000 : if ( (i & 1) == 0 ) {
693 125000 : if ( (i & 3) == 0 ) {
694 50000 : result = result + power/factor;
695 : } else {
696 75000 : result = result - power/factor;
697 : }
698 : }
699 : }
700 25000 : return (result);
701 : }
702 :
703 6000 : int Min0( arg1, arg2) int arg1, arg2; {
704 6000 : if ( arg1 < arg2 ) {
705 6000 : return (arg1);
706 : } else {
707 0 : return (arg2);
708 : }
709 : }
710 :
711 0 : void Printcomplex( arg1, arg2, zarray, start, finish, increment)
712 : int arg1, arg2, start, finish, increment;
713 : struct complex zarray[];
714 : {
715 : int i;
716 0 : printf("\n");
717 :
718 0 : i = start;
719 : do {
720 0 : printf(" %15.3e%15.3e",zarray[i].rp,zarray[i].ip);
721 0 : i = i + increment;
722 0 : printf(" %15.3e%15.3e",zarray[i].rp,zarray[i].ip);
723 0 : printf("\n");
724 0 : i = i + increment;
725 0 : } while ( i <= finish );
726 :
727 0 : }
728 :
729 512000 : void Uniform11(iy, yfl) int *iy; float *yfl; {
730 512000 : *iy = (4855* *iy + 1731) & 8191;
731 512000 : *yfl = *iy/8192.0;
732 512000 : }
733 :
734 1000 : void Exptab(n, e) int n; struct complex e[]; {
735 : float theta, divisor, h[26];
736 : int i, j, k, l, m;
737 :
738 1000 : theta = 3.1415926536;
739 1000 : divisor = 4.0;
740 26000 : for ( i=1; i <= 25; i++ ) {
741 25000 : h[i] = 1/(2*Cos( theta/divisor ));
742 25000 : divisor = divisor + divisor;
743 : }
744 :
745 1000 : m = n / 2;
746 1000 : l = m / 2;
747 1000 : j = 1;
748 1000 : e[1].rp = 1.0;
749 1000 : e[1].ip = 0.0;
750 1000 : e[l+1].rp = 0.0;
751 1000 : e[l+1].ip = 1.0;
752 1000 : e[m+1].rp = -1.0;
753 1000 : e[m+1].ip = 0.0;
754 :
755 : do {
756 6000 : i = l / 2;
757 6000 : k = i;
758 :
759 : do {
760 6000 : e[k+1].rp = h[j]*(e[k+i+1].rp+e[k-i+1].rp);
761 6000 : e[k+1].ip = h[j]*(e[k+i+1].ip+e[k-i+1].ip);
762 6000 : k = k+l;
763 6000 : } while ( k <= m );
764 :
765 6000 : j = Min0( j+1, 25);
766 6000 : l = i;
767 6000 : } while ( l > 1 );
768 :
769 1000 : }
770 :
771 20000 : void Fft( n, z, w, e, sqrinv)
772 : int n; struct complex z[], w[]; struct complex e[]; float sqrinv;
773 : {
774 : int i, j, k, l, m, index;
775 20000 : m = n / 2;
776 20000 : l = 1;
777 :
778 : do {
779 160000 : k = 0;
780 160000 : j = l;
781 160000 : i = 1;
782 : do {
783 : do {
784 5100000 : w[i+k].rp = z[i].rp+z[m+i].rp;
785 5100000 : w[i+k].ip = z[i].ip+z[m+i].ip;
786 5100000 : w[i+j].rp = e[k+1].rp*(z[i].rp-z[i+m].rp)
787 5100000 : -e[k+1].ip*(z[i].ip-z[i+m].ip);
788 5100000 : w[i+j].ip = e[k+1].rp*(z[i].ip-z[i+m].ip)
789 5100000 : +e[k+1].ip*(z[i].rp-z[i+m].rp);
790 5100000 : i = i+1;
791 5100000 : } while ( i <= j );
792 5100000 : k = j;
793 5100000 : j = k+l;
794 5100000 : } while ( j <= m );
795 160000 : index = 1;
796 : do {
797 160000 : z[index] = w[index];
798 160000 : index = index+1;
799 160000 : } while ( index <= n );
800 160000 : l = l+l;
801 160000 : } while ( l <= m );
802 :
803 5140000 : for ( i = 1; i <= n; i++ ) {
804 5120000 : z[i].rp = sqrinv*z[i].rp;
805 5120000 : z[i].ip = -sqrinv*z[i].ip;
806 : }
807 :
808 20000 : }
809 :
810 1 : void Oscar() {
811 : int i, j;
812 1001 : for (j = 0; j < 1000; ++j) {
813 1000 : Exptab(fftsize,e);
814 1000 : seed = 5767;
815 257000 : for ( i = 1; i <= fftsize; i++ ) {
816 256000 : Uniform11( &seed, &zr );
817 256000 : Uniform11( &seed, &zi );
818 256000 : z[i].rp = 20.0*zr - 10.0;
819 256000 : z[i].ip = 20.0*zi - 10.0;
820 : }
821 :
822 21000 : for ( i = 1; i <= 20; i++ ) {
823 20000 : Fft(fftsize,z,w,e,0.0625);
824 : /* Printcomplex( 6, 99, z, 1, 256, 17 ); */
825 : }
826 : }
827 1 : }
828 :
829 1 : int main() {
830 : int i;
831 1 : fixed = 0.0; floated = 0.0;
832 :
833 :
834 1 : printf(" Perm"); timer = Getclock(); Perm(); xtimes[1] = Getclock()-timer;
835 1 : fixed = fixed + permbase*xtimes[1];
836 1 : floated = floated + permbase*xtimes[1];
837 1 : printf(" Towers"); timer = Getclock(); Towers(); xtimes[2] = Getclock()-timer;
838 1 : fixed = fixed + towersbase*xtimes[2];
839 1 : floated = floated + towersbase*xtimes[2];
840 1 : printf(" Queens"); timer = Getclock(); Queens(); xtimes[3] = Getclock()-timer;
841 1 : fixed = fixed + queensbase*xtimes[3];
842 1 : floated = floated + queensbase*xtimes[3];
843 1 : printf(" Intmm"); timer = Getclock(); Intmm(); xtimes[4] = Getclock()-timer;
844 1 : fixed = fixed + intmmbase*xtimes[4];
845 1 : floated = floated + intmmbase*xtimes[4];
846 1 : printf(" Mm"); timer = Getclock(); Mm(); xtimes[5] = Getclock()-timer;
847 1 : fixed = fixed + mmbase*xtimes[5];
848 1 : floated = floated + fpmmbase*xtimes[5];
849 1 : printf(" Puzzle"); timer = Getclock(); Puzzle(); xtimes[6] = Getclock()-timer;
850 1 : fixed = fixed + puzzlebase*xtimes[6];
851 1 : floated = floated + puzzlebase*xtimes[6];
852 1 : printf(" Quick"); timer = Getclock(); Quick(); xtimes[7] = Getclock()-timer;
853 1 : fixed = fixed + quickbase*xtimes[7];
854 1 : floated = floated + quickbase*xtimes[7];
855 1 : printf(" Bubble"); timer = Getclock(); Bubble(); xtimes[8] = Getclock()-timer;
856 1 : fixed = fixed + bubblebase*xtimes[8];
857 1 : floated = floated + bubblebase*xtimes[8];
858 1 : printf(" Tree"); timer = Getclock(); Trees(); xtimes[9] = Getclock()-timer;
859 1 : fixed = fixed + treebase*xtimes[9];
860 1 : floated = floated + treebase*xtimes[9];
861 1 : printf(" FFT"); timer = Getclock(); Oscar(); xtimes[10] = Getclock()-timer;
862 1 : fixed = fixed + fftbase*xtimes[10];
863 1 : floated = floated + fpfftbase*xtimes[10];
864 1 : printf("\n");
865 11 : for ( i = 1; i <= 10; i++ ) printf("%8d", xtimes[i]);
866 1 : printf("\n");
867 :
868 1 : return 0;
869 : }
|
