OLD | NEW |
1 /* | 1 /* |
2 * Simple test driver for MPI library | 2 * Simple test driver for MPI library |
3 * | 3 * |
4 * Test 5a: Greatest common divisor speed test, binary vs. Euclid | 4 * Test 5a: Greatest common divisor speed test, binary vs. Euclid |
5 * | 5 * |
6 * This Source Code Form is subject to the terms of the Mozilla Public | 6 * This Source Code Form is subject to the terms of the Mozilla Public |
7 * License, v. 2.0. If a copy of the MPL was not distributed with this | 7 * License, v. 2.0. If a copy of the MPL was not distributed with this |
8 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ | 8 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ |
9 | 9 |
10 #include <stdio.h> | 10 #include <stdio.h> |
11 #include <stdlib.h> | 11 #include <stdlib.h> |
12 #include <string.h> | 12 #include <string.h> |
13 #include <ctype.h> | 13 #include <ctype.h> |
14 #include <limits.h> | 14 #include <limits.h> |
15 #include <time.h> | 15 #include <time.h> |
16 | 16 |
17 #include <sys/time.h> | 17 #include <sys/time.h> |
18 | 18 |
19 #include "mpi.h" | 19 #include "mpi.h" |
20 #include "mpprime.h" | 20 #include "mpprime.h" |
21 | 21 |
22 typedef struct { | 22 typedef struct { |
23 unsigned int sec; | 23 unsigned int sec; |
24 unsigned int usec; | 24 unsigned int usec; |
25 } instant_t; | 25 } instant_t; |
26 | 26 |
27 instant_t now(void) | 27 instant_t now(void) { |
28 { | |
29 struct timeval clk; | 28 struct timeval clk; |
30 instant_t res; | 29 instant_t res; |
31 | 30 |
32 res.sec = res.usec = 0; | 31 res.sec = res.usec = 0; |
33 | 32 |
34 if(gettimeofday(&clk, NULL) != 0) | 33 if (gettimeofday(&clk, NULL) != 0) return res; |
35 return res; | |
36 | 34 |
37 res.sec = clk.tv_sec; | 35 res.sec = clk.tv_sec; |
38 res.usec = clk.tv_usec; | 36 res.usec = clk.tv_usec; |
39 | 37 |
40 return res; | 38 return res; |
41 } | 39 } |
42 | 40 |
43 #define PRECISION 16 | 41 #define PRECISION 16 |
44 | 42 |
45 int main(int argc, char *argv[]) | 43 int main(int argc, char *argv[]) { |
46 { | 44 int ix, num, prec = PRECISION; |
47 int ix, num, prec = PRECISION; | 45 mp_int a, b, c, d; |
48 mp_int a, b, c, d; | 46 instant_t start, finish; |
49 instant_t start, finish; | 47 time_t seed; |
50 time_t seed; | |
51 unsigned int d1, d2; | 48 unsigned int d1, d2; |
52 | 49 |
53 seed = time(NULL); | 50 seed = time(NULL); |
54 | 51 |
55 if(argc < 2) { | 52 if (argc < 2) { |
56 fprintf(stderr, "Usage: %s <num-tests>\n", argv[0]); | 53 fprintf(stderr, "Usage: %s <num-tests>\n", argv[0]); |
57 return 1; | 54 return 1; |
58 } | 55 } |
59 | 56 |
60 if((num = atoi(argv[1])) < 0) | 57 if ((num = atoi(argv[1])) < 0) num = -num; |
61 num = -num; | |
62 | 58 |
63 printf("Test 5a: Euclid vs. Binary, a GCD speed test\n\n" | 59 printf( |
64 » "Number of tests: %d\n" | 60 "Test 5a: Euclid vs. Binary, a GCD speed test\n\n" |
65 » "Precision: %d digits\n\n", num, prec); | 61 "Number of tests: %d\n" |
| 62 "Precision: %d digits\n\n", |
| 63 num, prec); |
66 | 64 |
67 mp_init_size(&a, prec); | 65 mp_init_size(&a, prec); |
68 mp_init_size(&b, prec); | 66 mp_init_size(&b, prec); |
69 mp_init(&c); | 67 mp_init(&c); |
70 mp_init(&d); | 68 mp_init(&d); |
71 | 69 |
72 printf("Verifying accuracy ... \n"); | 70 printf("Verifying accuracy ... \n"); |
73 srand((unsigned int)seed); | 71 srand((unsigned int)seed); |
74 for(ix = 0; ix < num; ix++) { | 72 for (ix = 0; ix < num; ix++) { |
75 mpp_random_size(&a, prec); | 73 mpp_random_size(&a, prec); |
76 mpp_random_size(&b, prec); | 74 mpp_random_size(&b, prec); |
77 | 75 |
78 mp_gcd(&a, &b, &c); | 76 mp_gcd(&a, &b, &c); |
79 mp_bgcd(&a, &b, &d); | 77 mp_bgcd(&a, &b, &d); |
80 | 78 |
81 if(mp_cmp(&c, &d) != 0) { | 79 if (mp_cmp(&c, &d) != 0) { |
82 printf("Error! Results not accurate:\n"); | 80 printf("Error! Results not accurate:\n"); |
83 printf("a = "); mp_print(&a, stdout); fputc('\n', stdout); | 81 printf("a = "); |
84 printf("b = "); mp_print(&b, stdout); fputc('\n', stdout); | 82 mp_print(&a, stdout); |
85 printf("c = "); mp_print(&c, stdout); fputc('\n', stdout); | 83 fputc('\n', stdout); |
86 printf("d = "); mp_print(&d, stdout); fputc('\n', stdout); | 84 printf("b = "); |
| 85 mp_print(&b, stdout); |
| 86 fputc('\n', stdout); |
| 87 printf("c = "); |
| 88 mp_print(&c, stdout); |
| 89 fputc('\n', stdout); |
| 90 printf("d = "); |
| 91 mp_print(&d, stdout); |
| 92 fputc('\n', stdout); |
87 | 93 |
88 mp_clear(&a); mp_clear(&b); mp_clear(&c); mp_clear(&d); | 94 mp_clear(&a); |
| 95 mp_clear(&b); |
| 96 mp_clear(&c); |
| 97 mp_clear(&d); |
89 return 1; | 98 return 1; |
90 } | 99 } |
91 } | 100 } |
92 mp_clear(&d); | 101 mp_clear(&d); |
93 printf("Accuracy confirmed for the %d test samples\n", num); | 102 printf("Accuracy confirmed for the %d test samples\n", num); |
94 | 103 |
95 printf("Testing Euclid ... \n"); | 104 printf("Testing Euclid ... \n"); |
96 srand((unsigned int)seed); | 105 srand((unsigned int)seed); |
97 start = now(); | 106 start = now(); |
98 for(ix = 0; ix < num; ix++) { | 107 for (ix = 0; ix < num; ix++) { |
99 mpp_random_size(&a, prec); | 108 mpp_random_size(&a, prec); |
100 mpp_random_size(&b, prec); | 109 mpp_random_size(&b, prec); |
101 mp_gcd(&a, &b, &c); | 110 mp_gcd(&a, &b, &c); |
102 | |
103 } | 111 } |
104 finish = now(); | 112 finish = now(); |
105 | 113 |
106 d1 = (finish.sec - start.sec) * 1000000; | 114 d1 = (finish.sec - start.sec) * 1000000; |
107 d1 -= start.usec; d1 += finish.usec; | 115 d1 -= start.usec; |
| 116 d1 += finish.usec; |
108 | 117 |
109 printf("Testing binary ... \n"); | 118 printf("Testing binary ... \n"); |
110 srand((unsigned int)seed); | 119 srand((unsigned int)seed); |
111 start = now(); | 120 start = now(); |
112 for(ix = 0; ix < num; ix++) { | 121 for (ix = 0; ix < num; ix++) { |
113 mpp_random_size(&a, prec); | 122 mpp_random_size(&a, prec); |
114 mpp_random_size(&b, prec); | 123 mpp_random_size(&b, prec); |
115 mp_bgcd(&a, &b, &c); | 124 mp_bgcd(&a, &b, &c); |
116 } | 125 } |
117 finish = now(); | 126 finish = now(); |
118 | 127 |
119 d2 = (finish.sec - start.sec) * 1000000; | 128 d2 = (finish.sec - start.sec) * 1000000; |
120 d2 -= start.usec; d2 += finish.usec; | 129 d2 -= start.usec; |
| 130 d2 += finish.usec; |
121 | 131 |
122 printf("Euclidean algorithm time: %u usec\n", d1); | 132 printf("Euclidean algorithm time: %u usec\n", d1); |
123 printf("Binary algorithm time: %u usec\n", d2); | 133 printf("Binary algorithm time: %u usec\n", d2); |
124 printf("Improvement: %.2f%%\n", | 134 printf("Improvement: %.2f%%\n", |
125 (1.0 - ((double)d2 / (double)d1)) * 100.0); | 135 (1.0 - ((double)d2 / (double)d1)) * 100.0); |
126 | 136 |
127 mp_clear(&c); | 137 mp_clear(&c); |
128 mp_clear(&b); | 138 mp_clear(&b); |
129 mp_clear(&a); | 139 mp_clear(&a); |
130 | 140 |
131 return 0; | 141 return 0; |
132 } | 142 } |
OLD | NEW |