1 //==============================================================================================
2 //
3 // This file is part of LiDIA --- a library for computational number theory
4 //
5 // Copyright (c) 1994--2001 the LiDIA Group. All rights reserved.
6 //
7 // See http://www.informatik.tu-darmstadt.de/TI/LiDIA/
8 //
9 //----------------------------------------------------------------------------------------------
10 //
11 // $Id$
12 //
13 // Author : Stefan Neis (SN)
14 // Changes : See CVS log
15 //
16 //==============================================================================================
17
18
19 #include <cassert>
20 #include <cstdlib>
21 #include <fstream>
22
23 #include "LiDIA/alg_number.h"
24 #include "LiDIA/timer.h"
25
26
27
28 #ifdef LIDIA_NAMESPACE
29 using namespace LiDIA;
30 #endif
31
32
33
34 std::ifstream in("alg_appl_input");
35
36
37
identitytest(module a,module b,module c)38 void identitytest(module a, module b, module c) // MM
39 {
40 debug_handler_c("module_appl::identitytest", "preparing assertions 1-9", 0,
41 std::cout << a << b << c);
42 assert((a + b) == (b + a));
43 assert((a & b) == (b & a));
44 assert((a * b) == (b * a));
45
46 debug_handler_l("module_appl::identitytest", "assertions 1 to 3 succeded", 3);
47
48 assert((a + (b + c)) == ((a + b) + c));
49 assert((a + (b + c)) == ((a + c) + b));
50 assert((a * (b * c)) == ((a * b) * c));
51 assert((a * (b * c)) == ((c * a) * b));
52 assert((a & (b & c)) == ((a & b) & c));
53 assert((a & (b & c)) == ((c & a) & b));
54
55 debug_handler_l("module_appl::identitytest", "assertions 4 to 9 succeded", 3);
56
57 debug_handler_c("module_appl::identitytest", "preparing assertions 10-13", 0,
58 std::cout << a << b << (a+b) << (a&b));
59 assert((a + b) >= a);
60 assert((a + b) >= b);
61
62 assert((a & b) <= a);
63 assert((a & b) <= b);
64
65 debug_handler_l("module_appl::identitytest", "assertions 10 to 13 succeded", 3);
66 debug_handler_c("module_appl::identitytest", "preparing assertion 14", 0,
67 std::cout << a << b << c << b+c << a*(b+c) << a*b << a*c << (a*b)+(a*c));
68 assert((a * (b + c)) == ((a * b) + (a * c)));
69 debug_handler_c("module_appl::identitytest", "preparing assertion 15", 3,
70 std::cout << a << b << c << (b&c) << (a*(b&c)) << (a*b) << (a*c) << ((a*b)&(a*c)));
71 assert((a * (b & c)) <= ((a * b) & (a * c)));
72 debug_handler_c("module_appl::identitytest", "preparing assertion 16", 3,
73 std::cout << a << b << c << (b+c) << (a&(b+c)) << (a&b) << (a&c) << ((a&b)+(a&c)));
74 assert((a & (b + c)) == ((a & b) + (a & c)));
75
76 debug_handler_l("module_appl::identitytest",
77 "assertions 14 to 16 succeded", 3);
78
79 debug_handler_c("module_appl::identitytest", "preparing assertion 17", 3,
80 std::cout << a << b << (a&b) << ((a&b)+b));
81 assert(((a & b) + b) == b);
82 debug_handler_c("module_appl::identitytest", "preparing assertion 18", 3,
83 std::cout << a << b << (a+b) << ((a+b)&b));
84 assert(((a + b) & b) == b);
85 debug_handler_c("module_appl::identitytest", "preparing assertion 19", 3,
86 std::cout << a << b << (a*b) << ((a*b)&b) << (a&b) << ((a&b)*b));
87 // assert( ((a * b) & b) == ((a&b)*b));
88 debug_handler_c("module_appl::identitytest", "preparing assertion 20", 3,
89 std::cout << a << b << (a*b) << ((a*b)&a) << (a&b) << (a*(a&b)));
90 // assert( ((a * b) & a) == (a*(a&b)));
91 debug_handler_c("module_appl::identitytest", "preparing assertion 21", 3,
92 std::cout << a << b << (a&b) << ((a&b)&a));
93 assert(((a & b) & a) == (a & b));
94
95 debug_handler_l("module_appl::identitytest",
96 "assertions 17 to 21 succeded", 3);
97
98 if (!exponent(b).is_zero()) {
99 debug_handler_c("module_appl::identitytest", "preparing assertion 22", 3,
100 std::cout << a << b << (a*b) << (a*b)/b);
101 assert(((a * b) / b) >= a);
102 debug_handler_c("module_appl::identitytest", "preparing assertion 23", 3,
103 std::cout << a << b << (a/b) << std::flush; std::cout << (a/b)*b << std::flush);
104 assert(((a / b) * b) <= a);
105 }
106 if (!exponent(a).is_zero()) {
107 debug_handler_c("module_appl::identitytest", "preparing assertion 24", 3,
108 std::cout << a << b << (a*b) << std::flush; std::cout << (a*b)/a << std::flush);
109 assert(((a * b) / a) >= b);
110 debug_handler_c("module_appl::identitytest", "preparing assertion 25", 3,
111 std::cout << a << b << (b/a) << (b/a)*a << std::flush);
112 assert(((b / a) * a) <= b);
113 }
114
115 debug_handler_l("module_appl::identitytest",
116 "assertions 22 to 25 succeded", 3);
117
118 module d;
119
120 add(d, b, a); assert((a + b) == d);
121 intersect(d, a , b); assert((a & b) == d);
122 multiply(d, a, b); assert(d == (b * a));
123 d.assign(b); multiply(d, a, d); assert(d == (a * b));
124 intersect(d, a, b); assert((a & b) == d);
125 if (!exponent(b).is_zero()) {
126 divide(d, a, b); assert((a / b) == d);
127 }
128 add(d, b, c); multiply(d, a, d); assert(d == ((a * b) + (a * c)));
129 debug_handler_l("module_appl::identitytest",
130 "procedural versions completed successfully", 3);
131 }
132
133
134
utiltest(module a)135 void utiltest(module a) // MM, removed "&" for MS VC++ 5.0
136 {
137 module b, c;
138
139 square(b, a);
140 multiply(c, a, a);
141 assert(b == c);
142
143 module x = alg_number(1), y = alg_number(1);
144
145 for (int i = 0; i < 10; ++i) {
146 power(b, a, i);
147 debug_handler_c("module_appl::utiltest", "power", 2,
148 std::cout << a << " ^ " << i << " is " << b << std::endl);
149 assert(b == x);
150 x *= a;
151 y = a * y;
152 assert(y == x);
153 }
154 x.assign_one();
155 assert(x.is_one());
156 }
157
158
159
accumtest(module & a,module & b,module & c)160 void accumtest(module& a, module& b, module& c)
161 {
162 module x = a;
163 x *= b;
164 assert(x == (b * a));
165 x += c;
166 assert(x == (c+(b * a)));
167 x &= a;
168 assert(x == ((c & a) + ((b * a) & a)));
169 if (!exponent(b).is_zero()) {
170 x /= b;
171 debug_handler_c("module_appl::acummtest", "preparing assertion 4", 3,
172 std::cout << x << (((c+b*a)&a)/b) << ((c&a)/b+((b*a)&a)/b) << std::flush);
173 assert(x == (((c & a) + ((b * a)& a))/b));
174 }
175
176 x.assign(a);
177 assert(x == a);
178
179 debug_handler_l("module_appl::accumtest",
180 "assertions 1 to 5 succeded", 3);
181
182 multiply(x, x, b);
183 debug_handler_c("module_appl::acummtest", "preparing assertion 6", 3,
184 std::cout << a << b << x << (b*a) << std::flush);
185 assert(x == (b * a));
186 add(x, x, c);
187 debug_handler_c("module_appl::acummtest", "preparing assertion 7", 3,
188 std::cout << c << x << c+(b*a) << std::flush);
189 assert(x == (c+(b * a)));
190 intersect(x, x, a);
191 debug_handler_c("module_appl::acummtest", "preparing assertion 8", 3,
192 std::cout << a << x << ((c+(b*a))&a) << std::flush);
193 assert(x == ((c + (b * a))&a));
194 debug_handler_c("module_appl::acummtest", "preparing assertion 9", 3,
195 std::cout << ((c&a)+((b*a)&a)) << std::flush);
196 assert(x == ((c & a) + ((b * a) & a)));
197 if (!exponent(b).is_zero()) {
198 divide(x, x, b);
199 debug_handler_c("module_appl::acummtest", "preparing assertion 10", 3,
200 std::cout << x << (((c+(b*a))&a)/b) << std::flush);
201 assert(x == (((c + (b * a))&a)/b));
202 }
203 }
204
205
206
anothertest()207 void anothertest()
208 {
209 module pow64;
210 power(pow64, module(bigint(2)), 64);
211
212 bigint s64 = 1;
213 s64 <<= 64;
214
215 assert(alg_number(s64) == pow64);
216 assert(!(alg_number(s64) != pow64));
217
218 bigint s32 = s64 >> 32;
219 assert(!(pow64 == alg_number(s32)));
220 assert(pow64 != alg_number(s32));
221
222 debug_handler_l("module_appl::anothertest",
223 "simple tests succeded, starting identitytest", 4);
224 identitytest(module(s64), module(s32), pow64);
225 debug_handler_l("module_appl::anothertest",
226 "identitytest succeded, starting accumtest", 4);
227 // accumtest(pow64, alg_number(s32), pow64);
228 debug_handler_l("module_appl::anothertest",
229 "accumtest succeded, starting utiltest", 4);
230 utiltest(alg_number(s32));
231 }
232
233
234
235 #if 0
236 void iotest()
237 {
238 module result;
239
240 std::cout << "\nenter an module: ";
241 std::cin >> result;
242 std::cout << "module = " << result << "\n";
243 }
244 #endif
245
246
247
all_test(const bigint & ii)248 void all_test(const bigint & ii)
249 {
250 module a, b;
251
252 debug_handler_l("module_appl", "start all_test(const bigint &)", 4);
253 a.randomize(ii);
254 b.randomize(ii);
255 // std::cin >> a >> b;
256
257 std::cout << "\n\n Test with \na = " << a << "\nb = " << b << std::endl;
258
259 debug_handler_l("module_appl", "call utiltest from all_test", 4);
260 utiltest(a);
261 debug_handler_l("module_appl", "call identitytest from all_test", 4);
262 identitytest(a, b, b);
263 debug_handler_l("module_appl", "call identitytest again from all_test", 4);
264 identitytest(a, a, b);
265
266 debug_handler_l("module_appl", "call accumtest from all_test", 4);
267 // accumtest(a, a, b);
268 debug_handler_l("module_appl", "call accumtest again from all_test", 4);
269 // accumtest(b, a, b);
270
271 debug_handler_l("module_appl", "call utiltest again from all_test", 4);
272 utiltest(a);
273 debug_handler_l("module_appl", "call utiltest (3) from all_test", 4);
274 utiltest(b);
275 }
276
277
278
main_LiDIA(int argc,char ** argv)279 int main_LiDIA(int argc, char** argv)
280 {
281 order O;
282 std::cout << "Order:\n" << std::flush;
283 in >> O;
284
285 std::cout << "Computing the maximal order needs:" << std::flush;
286 timer T;
287 T.start_timer();
288 order ext = O.maximize();
289 T.stop_timer();
290 std::cout << T << std::endl << std::flush;
291
292 // The following 3 lines lead to an internal compiler error,
293 // if gcc-2.6.2 is used:
294 module one(alg_number(static_cast< bigint > (1)),
295 alg_number(static_cast< bigint > (0)));
296 std::cout << "one = " << one << "\n";
297 assert(one == one + alg_number(static_cast< bigint > (1)));
298 assert(one.is_one());
299 assert(!one.is_zero());
300
301 module n(alg_number(static_cast< bigint > (0)),
302 alg_number(static_cast< bigint > (0)));
303 assert(n.is_zero());
304 assert(!n.is_one());
305 debug_handler_l("module_appl",
306 "simple tests succeded, starting anothertest", 5);
307 anothertest();
308 debug_handler_l("module_appl", "anothertest succeded, starting iotest", 5);
309 // iotest();
310 debug_handler_l("module_appl", "simple tests succeded, "
311 "starting random tests", 5);
312
313 bigint i = 129099121;
314
315 for (int j = 0; j < 10; j++)
316 all_test(i);
317
318 std::cout << "\nEnd of test\n";
319 return 0;
320 }
321
322
main(int argc,char ** argv)323 int main(int argc, char** argv) {
324
325 #if defined(LIDIA_EXCEPTIONS)
326 try {
327 #endif
328
329 main_LiDIA(argc, argv);
330
331 #if defined(LIDIA_EXCEPTIONS)
332 }
333 catch(basic_error const& ex) {
334 ex.traditional_error_handler();
335 return 1;
336 }
337 catch(std::exception const& ex) {
338 std::cerr << "unexpected exception: " << ex.what() << "\n";
339 return 1;
340 }
341 #endif
342
343 }
344