1 | /**************************************** |
---|
2 | * Computer Algebra System SINGULAR * |
---|
3 | ****************************************/ |
---|
4 | /* $Id$ */ |
---|
5 | /* |
---|
6 | * ABSTRACT: numbers modulo 2^m |
---|
7 | */ |
---|
8 | |
---|
9 | #include "config.h" |
---|
10 | #include <auxiliary.h> |
---|
11 | |
---|
12 | #ifdef HAVE_RINGS |
---|
13 | |
---|
14 | #include <mylimits.h> |
---|
15 | #include "coeffs.h" |
---|
16 | #include "reporter.h" |
---|
17 | #include "omalloc.h" |
---|
18 | #include "numbers.h" |
---|
19 | #include "longrat.h" |
---|
20 | #include "mpr_complex.h" |
---|
21 | #include "rmodulo2m.h" |
---|
22 | #include "si_gmp.h" |
---|
23 | |
---|
24 | #include <string.h> |
---|
25 | |
---|
26 | int nr2mExp; |
---|
27 | |
---|
28 | extern omBin gmp_nrz_bin; /* init in rintegers*/ |
---|
29 | |
---|
30 | /* for initializing function pointers */ |
---|
31 | void nr2mInitChar (coeffs r, void*) |
---|
32 | { |
---|
33 | nr2mInitExp(r->ch, r); |
---|
34 | r->cfInit = nr2mInit; |
---|
35 | r->cfCopy = ndCopy; |
---|
36 | r->cfInt = nr2mInt; |
---|
37 | r->cfAdd = nr2mAdd; |
---|
38 | r->cfSub = nr2mSub; |
---|
39 | r->cfMult = nr2mMult; |
---|
40 | r->cfDiv = nr2mDiv; |
---|
41 | r->cfIntDiv = nr2mIntDiv; |
---|
42 | r->cfIntMod = nr2mMod; |
---|
43 | r->cfExactDiv = nr2mDiv; |
---|
44 | r->cfNeg = nr2mNeg; |
---|
45 | r->cfInvers = nr2mInvers; |
---|
46 | r->cfDivBy = nr2mDivBy; |
---|
47 | r->cfDivComp = nr2mDivComp; |
---|
48 | r->cfGreater = nr2mGreater; |
---|
49 | r->cfEqual = nr2mEqual; |
---|
50 | r->cfIsZero = nr2mIsZero; |
---|
51 | r->cfIsOne = nr2mIsOne; |
---|
52 | r->cfIsMOne = nr2mIsMOne; |
---|
53 | r->cfGreaterZero = nr2mGreaterZero; |
---|
54 | r->cfWrite = nr2mWrite; |
---|
55 | r->cfRead = nr2mRead; |
---|
56 | r->cfPower = nr2mPower; |
---|
57 | r->cfSetMap = nr2mSetMap; |
---|
58 | r->cfNormalize = ndNormalize; |
---|
59 | r->cfLcm = nr2mLcm; |
---|
60 | r->cfGcd = nr2mGcd; |
---|
61 | r->cfIsUnit = nr2mIsUnit; |
---|
62 | r->cfGetUnit = nr2mGetUnit; |
---|
63 | r->cfExtGcd = nr2mExtGcd; |
---|
64 | r->cfName = ndName; |
---|
65 | #ifdef LDEBUG |
---|
66 | r->cfDBTest = nr2mDBTest; |
---|
67 | #endif |
---|
68 | r->has_simple_Alloc=TRUE; |
---|
69 | } |
---|
70 | |
---|
71 | /* |
---|
72 | * Multiply two numbers |
---|
73 | */ |
---|
74 | number nr2mMult (number a, number b, const coeffs r) |
---|
75 | { |
---|
76 | if (((NATNUMBER)a == 0) || ((NATNUMBER)b == 0)) |
---|
77 | return (number)0; |
---|
78 | else |
---|
79 | return nr2mMultM(a,b,r); |
---|
80 | } |
---|
81 | |
---|
82 | /* |
---|
83 | * Give the smallest non unit k, such that a * x = k = b * y has a solution |
---|
84 | */ |
---|
85 | number nr2mLcm (number a, number b, const coeffs r) |
---|
86 | { |
---|
87 | NATNUMBER res = 0; |
---|
88 | if ((NATNUMBER) a == 0) a = (number) 1; |
---|
89 | if ((NATNUMBER) b == 0) b = (number) 1; |
---|
90 | while ((NATNUMBER) a % 2 == 0) |
---|
91 | { |
---|
92 | a = (number) ((NATNUMBER) a / 2); |
---|
93 | if ((NATNUMBER) b % 2 == 0) b = (number) ((NATNUMBER) b / 2); |
---|
94 | res++; |
---|
95 | } |
---|
96 | while ((NATNUMBER) b % 2 == 0) |
---|
97 | { |
---|
98 | b = (number) ((NATNUMBER) b / 2); |
---|
99 | res++; |
---|
100 | } |
---|
101 | return (number) (1L << res); // (2**res) |
---|
102 | } |
---|
103 | |
---|
104 | /* |
---|
105 | * Give the largest non unit k, such that a = x * k, b = y * k has |
---|
106 | * a solution. |
---|
107 | */ |
---|
108 | number nr2mGcd (number a, number b, const coeffs r) |
---|
109 | { |
---|
110 | NATNUMBER res = 0; |
---|
111 | if ((NATNUMBER) a == 0 && (NATNUMBER) b == 0) return (number) 1; |
---|
112 | while ((NATNUMBER) a % 2 == 0 && (NATNUMBER) b % 2 == 0) |
---|
113 | { |
---|
114 | a = (number) ((NATNUMBER) a / 2); |
---|
115 | b = (number) ((NATNUMBER) b / 2); |
---|
116 | res++; |
---|
117 | } |
---|
118 | // if ((NATNUMBER) b % 2 == 0) |
---|
119 | // { |
---|
120 | // return (number) ((1L << res));// * (NATNUMBER) a); // (2**res)*a a ist Einheit |
---|
121 | // } |
---|
122 | // else |
---|
123 | // { |
---|
124 | return (number) ((1L << res));// * (NATNUMBER) b); // (2**res)*b b ist Einheit |
---|
125 | // } |
---|
126 | } |
---|
127 | |
---|
128 | /* |
---|
129 | * Give the largest non unit k, such that a = x * k, b = y * k has |
---|
130 | * a solution. |
---|
131 | */ |
---|
132 | number nr2mExtGcd (number a, number b, number *s, number *t, const coeffs r) |
---|
133 | { |
---|
134 | NATNUMBER res = 0; |
---|
135 | if ((NATNUMBER) a == 0 && (NATNUMBER) b == 0) return (number) 1; |
---|
136 | while ((NATNUMBER) a % 2 == 0 && (NATNUMBER) b % 2 == 0) |
---|
137 | { |
---|
138 | a = (number) ((NATNUMBER) a / 2); |
---|
139 | b = (number) ((NATNUMBER) b / 2); |
---|
140 | res++; |
---|
141 | } |
---|
142 | if ((NATNUMBER) b % 2 == 0) |
---|
143 | { |
---|
144 | *t = NULL; |
---|
145 | *s = nr2mInvers(a,r); |
---|
146 | return (number) ((1L << res));// * (NATNUMBER) a); // (2**res)*a a ist Einheit |
---|
147 | } |
---|
148 | else |
---|
149 | { |
---|
150 | *s = NULL; |
---|
151 | *t = nr2mInvers(b,r); |
---|
152 | return (number) ((1L << res));// * (NATNUMBER) b); // (2**res)*b b ist Einheit |
---|
153 | } |
---|
154 | } |
---|
155 | |
---|
156 | void nr2mPower (number a, int i, number * result, const coeffs r) |
---|
157 | { |
---|
158 | if (i==0) |
---|
159 | { |
---|
160 | *(NATNUMBER *)result = 1; |
---|
161 | } |
---|
162 | else if (i==1) |
---|
163 | { |
---|
164 | *result = a; |
---|
165 | } |
---|
166 | else |
---|
167 | { |
---|
168 | nr2mPower(a,i-1,result,r); |
---|
169 | *result = nr2mMultM(a,*result,r); |
---|
170 | } |
---|
171 | } |
---|
172 | |
---|
173 | /* |
---|
174 | * create a number from int |
---|
175 | */ |
---|
176 | number nr2mInit (int i, const coeffs r) |
---|
177 | { |
---|
178 | if (i == 0) return (number)(NATNUMBER)i; |
---|
179 | |
---|
180 | long ii = i; |
---|
181 | NATNUMBER j = (NATNUMBER)1; |
---|
182 | if (ii < 0) { j = r->nr2mModul; ii = -ii; } |
---|
183 | NATNUMBER k = (NATNUMBER)ii; |
---|
184 | k = k & r->nr2mModul; |
---|
185 | /* now we have: from = j * k mod 2^m */ |
---|
186 | return (number)nr2mMult((number)j, (number)k); |
---|
187 | } |
---|
188 | |
---|
189 | /* |
---|
190 | * convert a number to an int in ]-k/2 .. k/2], |
---|
191 | * where k = 2^m; i.e., an int in ]-2^(m-1) .. 2^(m-1)]; |
---|
192 | * note that the code computes a long which will then |
---|
193 | * automatically casted to int |
---|
194 | */ |
---|
195 | int nr2mInt(number &n, const coeffs r) |
---|
196 | { |
---|
197 | NATNUMBER nn = (unsigned long)(NATNUMBER)n & r->nr2mModul; |
---|
198 | unsigned long l = r->nr2mModul >> 1; l++; /* now: l = 2^(m-1) */ |
---|
199 | if ((NATNUMBER)nn > l) |
---|
200 | return (int)((NATNUMBER)nn - r->nr2mModul - 1); |
---|
201 | else |
---|
202 | return (int)((NATNUMBER)nn); |
---|
203 | } |
---|
204 | |
---|
205 | number nr2mAdd (number a, number b, const coeffs r) |
---|
206 | { |
---|
207 | return nr2mAddM(a,b,r); |
---|
208 | } |
---|
209 | |
---|
210 | number nr2mSub (number a, number b, const coeffs r) |
---|
211 | { |
---|
212 | return nr2mSubM(a,b,r); |
---|
213 | } |
---|
214 | |
---|
215 | BOOLEAN nr2mIsUnit (number a, const coeffs r) |
---|
216 | { |
---|
217 | return ((NATNUMBER) a % 2 == 1); |
---|
218 | } |
---|
219 | |
---|
220 | number nr2mGetUnit (number k, const coeffs r) |
---|
221 | { |
---|
222 | if (k == NULL) |
---|
223 | return (number) 1; |
---|
224 | NATNUMBER tmp = (NATNUMBER) k; |
---|
225 | while (tmp % 2 == 0) |
---|
226 | tmp = tmp / 2; |
---|
227 | return (number) tmp; |
---|
228 | } |
---|
229 | |
---|
230 | BOOLEAN nr2mIsZero (number a, const coeffs r) |
---|
231 | { |
---|
232 | return 0 == (NATNUMBER)a; |
---|
233 | } |
---|
234 | |
---|
235 | BOOLEAN nr2mIsOne (number a, const coeffs r) |
---|
236 | { |
---|
237 | return 1 == (NATNUMBER)a; |
---|
238 | } |
---|
239 | |
---|
240 | BOOLEAN nr2mIsMOne (number a, const coeffs r) |
---|
241 | { |
---|
242 | return (r->nr2mModul == (NATNUMBER)a) |
---|
243 | && (r->nr2mModul != 2); |
---|
244 | } |
---|
245 | |
---|
246 | BOOLEAN nr2mEqual (number a, number b, const coeffs r) |
---|
247 | { |
---|
248 | return a==b; |
---|
249 | } |
---|
250 | |
---|
251 | BOOLEAN nr2mGreater (number a, number b, const coeffs r) |
---|
252 | { |
---|
253 | return nr2mDivBy(a, b,r); |
---|
254 | } |
---|
255 | |
---|
256 | /* Is a divisible by b? There are two cases: |
---|
257 | 1) a = 0 mod 2^m; then TRUE iff b = 0 or b is a power of 2 |
---|
258 | 2) a, b <> 0; then TRUE iff b/gcd(a, b) is a unit mod 2^m |
---|
259 | TRUE iff b(gcd(a, b) is a unit */ |
---|
260 | BOOLEAN nr2mDivBy (number a, number b, const coeffs r) |
---|
261 | { |
---|
262 | if (a == NULL) |
---|
263 | { |
---|
264 | NATNUMBER c = r->nr2mModul + 1; |
---|
265 | if (c != 0) /* i.e., if no overflow */ |
---|
266 | return (c % (NATNUMBER)b) == 0; |
---|
267 | else |
---|
268 | { |
---|
269 | /* overflow: we need to check whether b |
---|
270 | is zero or a power of 2: */ |
---|
271 | c = (NATNUMBER)b; |
---|
272 | while (c != 0) |
---|
273 | { |
---|
274 | if ((c % 2) != 0) return FALSE; |
---|
275 | c = c >> 1; |
---|
276 | } |
---|
277 | return TRUE; |
---|
278 | } |
---|
279 | } |
---|
280 | else |
---|
281 | { |
---|
282 | number n = nr2mGcd(a, b, r); |
---|
283 | n = nr2mDiv(b, n, r); |
---|
284 | return nr2mIsUnit(n, r); |
---|
285 | } |
---|
286 | } |
---|
287 | |
---|
288 | int nr2mDivComp(number as, number bs, const coeffs r) |
---|
289 | { |
---|
290 | NATNUMBER a = (NATNUMBER) as; |
---|
291 | NATNUMBER b = (NATNUMBER) bs; |
---|
292 | assume(a != 0 && b != 0); |
---|
293 | while (a % 2 == 0 && b % 2 == 0) |
---|
294 | { |
---|
295 | a = a / 2; |
---|
296 | b = b / 2; |
---|
297 | } |
---|
298 | if (a % 2 == 0) |
---|
299 | { |
---|
300 | return -1; |
---|
301 | } |
---|
302 | else |
---|
303 | { |
---|
304 | if (b % 2 == 1) |
---|
305 | { |
---|
306 | return 2; |
---|
307 | } |
---|
308 | else |
---|
309 | { |
---|
310 | return 1; |
---|
311 | } |
---|
312 | } |
---|
313 | } |
---|
314 | |
---|
315 | /* TRUE iff 0 < k <= 2^m / 2 */ |
---|
316 | BOOLEAN nr2mGreaterZero (number k, const coeffs r) |
---|
317 | { |
---|
318 | if ((NATNUMBER)k == 0) return FALSE; |
---|
319 | if ((NATNUMBER)k > ((r->nr2mModul >> 1) + 1)) return FALSE; |
---|
320 | return TRUE; |
---|
321 | } |
---|
322 | |
---|
323 | /* assumes that 'a' is odd, i.e., a unit in Z/2^m, and computes |
---|
324 | the extended gcd of 'a' and 2^m, in order to find some 's' |
---|
325 | and 't' such that a * s + 2^m * t = gcd(a, 2^m) = 1; |
---|
326 | this code will always find a positive 's' */ |
---|
327 | void specialXGCD(unsigned long& s, unsigned long a, const coeffs R) |
---|
328 | { |
---|
329 | int_number u = (int_number)omAlloc(sizeof(mpz_t)); |
---|
330 | mpz_init_set_ui(u, a); |
---|
331 | int_number u0 = (int_number)omAlloc(sizeof(mpz_t)); |
---|
332 | mpz_init(u0); |
---|
333 | int_number u1 = (int_number)omAlloc(sizeof(mpz_t)); |
---|
334 | mpz_init_set_ui(u1, 1); |
---|
335 | int_number u2 = (int_number)omAlloc(sizeof(mpz_t)); |
---|
336 | mpz_init(u2); |
---|
337 | int_number v = (int_number)omAlloc(sizeof(mpz_t)); |
---|
338 | mpz_init_set_ui(v, R->nr2mModul); |
---|
339 | mpz_add_ui(v, v, 1); /* now: v = 2^m */ |
---|
340 | int_number v0 = (int_number)omAlloc(sizeof(mpz_t)); |
---|
341 | mpz_init(v0); |
---|
342 | int_number v1 = (int_number)omAlloc(sizeof(mpz_t)); |
---|
343 | mpz_init(v1); |
---|
344 | int_number v2 = (int_number)omAlloc(sizeof(mpz_t)); |
---|
345 | mpz_init_set_ui(v2, 1); |
---|
346 | int_number q = (int_number)omAlloc(sizeof(mpz_t)); |
---|
347 | mpz_init(q); |
---|
348 | int_number r = (int_number)omAlloc(sizeof(mpz_t)); |
---|
349 | mpz_init(r); |
---|
350 | |
---|
351 | while (mpz_cmp_ui(v, 0) != 0) /* i.e., while v != 0 */ |
---|
352 | { |
---|
353 | mpz_div(q, u, v); |
---|
354 | mpz_mod(r, u, v); |
---|
355 | mpz_set(u, v); |
---|
356 | mpz_set(v, r); |
---|
357 | mpz_set(u0, u2); |
---|
358 | mpz_set(v0, v2); |
---|
359 | mpz_mul(u2, u2, q); mpz_sub(u2, u1, u2); /* u2 = u1 - q * u2 */ |
---|
360 | mpz_mul(v2, v2, q); mpz_sub(v2, v1, v2); /* v2 = v1 - q * v2 */ |
---|
361 | mpz_set(u1, u0); |
---|
362 | mpz_set(v1, v0); |
---|
363 | } |
---|
364 | |
---|
365 | while (mpz_cmp_ui(u1, 0) < 0) /* i.e., while u1 < 0 */ |
---|
366 | { |
---|
367 | /* we add 2^m = (2^m - 1) + 1 to u1: */ |
---|
368 | mpz_add_ui(u1, u1, R->nr2mModul); |
---|
369 | mpz_add_ui(u1, u1, 1); |
---|
370 | } |
---|
371 | s = mpz_get_ui(u1); /* now: 0 <= s <= 2^m - 1 */ |
---|
372 | |
---|
373 | mpz_clear(u); omFree((ADDRESS)u); |
---|
374 | mpz_clear(u0); omFree((ADDRESS)u0); |
---|
375 | mpz_clear(u1); omFree((ADDRESS)u1); |
---|
376 | mpz_clear(u2); omFree((ADDRESS)u2); |
---|
377 | mpz_clear(v); omFree((ADDRESS)v); |
---|
378 | mpz_clear(v0); omFree((ADDRESS)v0); |
---|
379 | mpz_clear(v1); omFree((ADDRESS)v1); |
---|
380 | mpz_clear(v2); omFree((ADDRESS)v2); |
---|
381 | mpz_clear(q); omFree((ADDRESS)q); |
---|
382 | mpz_clear(r); omFree((ADDRESS)r); |
---|
383 | } |
---|
384 | |
---|
385 | NATNUMBER InvMod(NATNUMBER a, const coeffs r) |
---|
386 | { |
---|
387 | assume((NATNUMBER)a % 2 != 0); |
---|
388 | unsigned long s; |
---|
389 | specialXGCD(s, a, r); |
---|
390 | return s; |
---|
391 | } |
---|
392 | //#endif |
---|
393 | |
---|
394 | inline number nr2mInversM (number c, const coeffs r) |
---|
395 | { |
---|
396 | assume((NATNUMBER)c % 2 != 0); |
---|
397 | // Table !!! |
---|
398 | NATNUMBER inv; |
---|
399 | inv = InvMod((NATNUMBER)c,r); |
---|
400 | return (number) inv; |
---|
401 | } |
---|
402 | |
---|
403 | number nr2mDiv (number a, number b, const coeffs r) |
---|
404 | { |
---|
405 | if ((NATNUMBER)a==0) |
---|
406 | return (number)0; |
---|
407 | else if ((NATNUMBER)b%2==0) |
---|
408 | { |
---|
409 | if ((NATNUMBER)b != 0) |
---|
410 | { |
---|
411 | while ((NATNUMBER) b%2 == 0 && (NATNUMBER) a%2 == 0) |
---|
412 | { |
---|
413 | a = (number) ((NATNUMBER) a / 2); |
---|
414 | b = (number) ((NATNUMBER) b / 2); |
---|
415 | } |
---|
416 | } |
---|
417 | if ((NATNUMBER) b%2 == 0) |
---|
418 | { |
---|
419 | WerrorS("Division not possible, even by cancelling zero divisors."); |
---|
420 | WerrorS("Result is integer division without remainder."); |
---|
421 | return (number) ((NATNUMBER) a / (NATNUMBER) b); |
---|
422 | } |
---|
423 | } |
---|
424 | return (number) nr2mMult(a, nr2mInversM(b,r),r); |
---|
425 | } |
---|
426 | |
---|
427 | number nr2mMod (number a, number b, const coeffs R) |
---|
428 | { |
---|
429 | /* |
---|
430 | We need to return the number r which is uniquely determined by the |
---|
431 | following two properties: |
---|
432 | (1) 0 <= r < |b| (with respect to '<' and '<=' performed in Z x Z) |
---|
433 | (2) There exists some k in the integers Z such that a = k * b + r. |
---|
434 | Consider g := gcd(2^m, |b|). Note that then |b|/g is a unit in Z/2^m. |
---|
435 | Now, there are three cases: |
---|
436 | (a) g = 1 |
---|
437 | Then |b| is a unit in Z/2^m, i.e. |b| (and also b) divides a. |
---|
438 | Thus r = 0. |
---|
439 | (b) g <> 1 and g divides a |
---|
440 | Then a = (a/g) * (|b|/g)^(-1) * b (up to sign), i.e. again r = 0. |
---|
441 | (c) g <> 1 and g does not divide a |
---|
442 | Let's denote the division with remainder of a by g as follows: |
---|
443 | a = s * g + t. Then t = a - s * g = a - s * (|b|/g)^(-1) * |b| |
---|
444 | fulfills (1) and (2), i.e. r := t is the correct result. Hence |
---|
445 | in this third case, r is the remainder of division of a by g in Z. |
---|
446 | This algorithm is the same as for the case Z/n, except that we may |
---|
447 | compute the gcd of |b| and 2^m "by hand": We just extract the highest |
---|
448 | power of 2 (<= 2^m) that is contained in b. |
---|
449 | */ |
---|
450 | assume((NATNUMBER)b != 0); |
---|
451 | NATNUMBER g = 1; |
---|
452 | NATNUMBER b_div = (NATNUMBER)b; |
---|
453 | if (b_div < 0) b_div = -b_div; // b_div now represents |b| |
---|
454 | NATNUMBER r = 0; |
---|
455 | while ((g < R->nr2mModul ) && (b_div > 0) && (b_div % 2 == 0)) |
---|
456 | { |
---|
457 | b_div = b_div >> 1; |
---|
458 | g = g << 1; |
---|
459 | } // g is now the gcd of 2^m and |b| |
---|
460 | |
---|
461 | if (g != 1) r = (NATNUMBER)a % g; |
---|
462 | return (number)r; |
---|
463 | } |
---|
464 | |
---|
465 | number nr2mIntDiv (number a, number b, const coeffs r) |
---|
466 | { |
---|
467 | if ((NATNUMBER)a == 0) |
---|
468 | { |
---|
469 | if ((NATNUMBER)b == 0) |
---|
470 | return (number)1; |
---|
471 | if ((NATNUMBER)b == 1) |
---|
472 | return (number)0; |
---|
473 | NATNUMBER c = r->nr2mModul + 1; |
---|
474 | if (c != 0) /* i.e., if no overflow */ |
---|
475 | return (number)(c / (NATNUMBER)b); |
---|
476 | else |
---|
477 | { |
---|
478 | /* overflow: c = 2^32 resp. 2^64, depending on platform */ |
---|
479 | int_number cc = (int_number)omAlloc(sizeof(mpz_t)); |
---|
480 | mpz_init_set_ui(cc, r->nr2mModul); mpz_add_ui(cc, cc, 1); |
---|
481 | mpz_div_ui(cc, cc, (unsigned long)(NATNUMBER)b); |
---|
482 | unsigned long s = mpz_get_ui(cc); |
---|
483 | mpz_clear(cc); omFree((ADDRESS)cc); |
---|
484 | return (number)(NATNUMBER)s; |
---|
485 | } |
---|
486 | } |
---|
487 | else |
---|
488 | { |
---|
489 | if ((NATNUMBER)b == 0) |
---|
490 | return (number)0; |
---|
491 | return (number)((NATNUMBER) a / (NATNUMBER) b); |
---|
492 | } |
---|
493 | } |
---|
494 | |
---|
495 | number nr2mInvers (number c, const coeffs r) |
---|
496 | { |
---|
497 | if ((NATNUMBER)c%2==0) |
---|
498 | { |
---|
499 | WerrorS("division by zero divisor"); |
---|
500 | return (number)0; |
---|
501 | } |
---|
502 | return nr2mInversM(c,r); |
---|
503 | } |
---|
504 | |
---|
505 | number nr2mNeg (number c, const coeffs r) |
---|
506 | { |
---|
507 | if ((NATNUMBER)c==0) return c; |
---|
508 | return nr2mNegM(c,r); |
---|
509 | } |
---|
510 | |
---|
511 | number nr2mMapMachineInt(number from, const coeffs src, const coeffs dst) |
---|
512 | { |
---|
513 | NATNUMBER i = ((NATNUMBER) from) % dst->nr2mModul ; |
---|
514 | return (number) i; |
---|
515 | } |
---|
516 | |
---|
517 | number nr2mMapZp(number from, const coeffs src, const coeffs dst) |
---|
518 | { |
---|
519 | NATNUMBER j = (NATNUMBER)1; |
---|
520 | long ii = (long) from; |
---|
521 | if (ii < 0) { j = dst->nr2mModul; ii = -ii; } |
---|
522 | NATNUMBER i = (NATNUMBER)ii; |
---|
523 | i = i & dst->nr2mModul; |
---|
524 | /* now we have: from = j * i mod 2^m */ |
---|
525 | return (number)nr2mMult((number)i, (number)j, dst); |
---|
526 | } |
---|
527 | |
---|
528 | number nr2mMapQ(number from, const coeffs src, const coeffs dst) |
---|
529 | { |
---|
530 | int_number erg = (int_number) omAllocBin(gmp_nrz_bin); |
---|
531 | mpz_init(erg); |
---|
532 | int_number k = (int_number) omAlloc(sizeof(mpz_t)); |
---|
533 | mpz_init_set_ui(k, dst->nr2mModul); |
---|
534 | |
---|
535 | nlGMP(from, (number)erg, dst); |
---|
536 | mpz_and(erg, erg, k); |
---|
537 | number res = (number)mpz_get_ui(erg); |
---|
538 | |
---|
539 | mpz_clear(erg); omFree((ADDRESS)erg); |
---|
540 | mpz_clear(k); omFree((ADDRESS)k); |
---|
541 | |
---|
542 | return (number) res; |
---|
543 | } |
---|
544 | |
---|
545 | number nr2mMapGMP(number from, const coeffs src, const coeffs dst) |
---|
546 | { |
---|
547 | int_number erg = (int_number) omAllocBin(gmp_nrz_bin); |
---|
548 | mpz_init(erg); |
---|
549 | int_number k = (int_number) omAlloc(sizeof(mpz_t)); |
---|
550 | mpz_init_set_ui(k, dst->nr2mModul); |
---|
551 | |
---|
552 | mpz_and(erg, (int_number)from, k); |
---|
553 | number res = (number) mpz_get_ui(erg); |
---|
554 | |
---|
555 | mpz_clear(erg); omFree((ADDRESS)erg); |
---|
556 | mpz_clear(k); omFree((ADDRESS)k); |
---|
557 | |
---|
558 | return (number) res; |
---|
559 | } |
---|
560 | |
---|
561 | nMapFunc nr2mSetMap(const coeffs src, const coeffs dst) |
---|
562 | { |
---|
563 | if (nField_is_Ring_2toM(src) |
---|
564 | && (src->ringflagb == dst->ringflagb)) |
---|
565 | { |
---|
566 | return ndCopyMap; |
---|
567 | } |
---|
568 | if (nField_is_Ring_2toM(src) |
---|
569 | && (src->ringflagb < dst->ringflagb)) |
---|
570 | { /* i.e. map an integer mod 2^s into Z mod 2^t, where t < s */ |
---|
571 | return nr2mMapMachineInt; |
---|
572 | } |
---|
573 | if (nField_is_Ring_2toM(src) |
---|
574 | && (src->ringflagb > dst->ringflagb)) |
---|
575 | { /* i.e. map an integer mod 2^s into Z mod 2^t, where t > s */ |
---|
576 | // to be done |
---|
577 | } |
---|
578 | if (nField_is_Ring_Z(src)) |
---|
579 | { |
---|
580 | return nr2mMapGMP; |
---|
581 | } |
---|
582 | if (nField_is_Q(src)) |
---|
583 | { |
---|
584 | return nr2mMapQ; |
---|
585 | } |
---|
586 | if (nField_is_Zp(src) |
---|
587 | && (src->ch == 2) |
---|
588 | && (dst->ringflagb == 1)) |
---|
589 | { |
---|
590 | return nr2mMapZp; |
---|
591 | } |
---|
592 | if (nField_is_Ring_PtoM(src) || nField_is_Ring_ModN(src)) |
---|
593 | { |
---|
594 | // Computing the n of Z/n |
---|
595 | int_number modul = (int_number) omAllocBin(gmp_nrz_bin); |
---|
596 | mpz_init(modul); |
---|
597 | mpz_set(modul, src->ringflaga); |
---|
598 | mpz_pow_ui(modul, modul, src->ringflagb); |
---|
599 | if (mpz_divisible_2exp_p(modul, dst->ringflagb)) |
---|
600 | { |
---|
601 | mpz_clear(modul); |
---|
602 | omFree((void *) modul); |
---|
603 | return nr2mMapGMP; |
---|
604 | } |
---|
605 | mpz_clear(modul); |
---|
606 | omFree((void *) modul); |
---|
607 | } |
---|
608 | return NULL; // default |
---|
609 | } |
---|
610 | |
---|
611 | /* |
---|
612 | * set the exponent (allocate and init tables) (TODO) |
---|
613 | */ |
---|
614 | |
---|
615 | void nr2mSetExp(int m, const coeffs r) |
---|
616 | { |
---|
617 | if (m > 1) |
---|
618 | { |
---|
619 | nr2mExp = m; |
---|
620 | /* we want nr2mModul to be the bit pattern '11..1' consisting |
---|
621 | of m one's: */ |
---|
622 | r->nr2mModul = 1; |
---|
623 | for (int i = 1; i < m; i++) r->nr2mModul = (r->nr2mModul * 2) + 1; |
---|
624 | } |
---|
625 | else |
---|
626 | { |
---|
627 | nr2mExp = 2; |
---|
628 | r->nr2mModul = 3; /* i.e., '11' in binary representation */ |
---|
629 | } |
---|
630 | } |
---|
631 | |
---|
632 | void nr2mInitExp(int m, const coeffs r) |
---|
633 | { |
---|
634 | nr2mSetExp(m, r); |
---|
635 | if (m < 2) WarnS("nr2mInitExp failed: we go on with Z/2^2"); |
---|
636 | } |
---|
637 | |
---|
638 | #ifdef LDEBUG |
---|
639 | BOOLEAN nr2mDBTest (number a, const char *f, const int l, const coeffs r) |
---|
640 | { |
---|
641 | if ((NATNUMBER)a < 0) return FALSE; |
---|
642 | if (((NATNUMBER)a & r->nr2mModul) != (NATNUMBER)a) return FALSE; |
---|
643 | return TRUE; |
---|
644 | } |
---|
645 | #endif |
---|
646 | |
---|
647 | void nr2mWrite (number &a, const coeffs r) |
---|
648 | { |
---|
649 | int i = nr2mInt(a, r); |
---|
650 | StringAppend("%d", i); |
---|
651 | } |
---|
652 | |
---|
653 | static const char* nr2mEati(const char *s, int *i, const coeffs r) |
---|
654 | { |
---|
655 | |
---|
656 | if (((*s) >= '0') && ((*s) <= '9')) |
---|
657 | { |
---|
658 | (*i) = 0; |
---|
659 | do |
---|
660 | { |
---|
661 | (*i) *= 10; |
---|
662 | (*i) += *s++ - '0'; |
---|
663 | if ((*i) >= (MAX_INT_VAL / 10)) (*i) = (*i) & r->nr2mModul; |
---|
664 | } |
---|
665 | while (((*s) >= '0') && ((*s) <= '9')); |
---|
666 | (*i) = (*i) & r->nr2mModul; |
---|
667 | } |
---|
668 | else (*i) = 1; |
---|
669 | return s; |
---|
670 | } |
---|
671 | |
---|
672 | const char * nr2mRead (const char *s, number *a, const coeffs r) |
---|
673 | { |
---|
674 | int z; |
---|
675 | int n=1; |
---|
676 | |
---|
677 | s = nr2mEati(s, &z,r); |
---|
678 | if ((*s) == '/') |
---|
679 | { |
---|
680 | s++; |
---|
681 | s = nr2mEati(s, &n,r); |
---|
682 | } |
---|
683 | if (n == 1) |
---|
684 | *a = (number)z; |
---|
685 | else |
---|
686 | *a = nr2mDiv((number)z,(number)n,r); |
---|
687 | return s; |
---|
688 | } |
---|
689 | #endif |
---|
690 | /* #ifdef HAVE_RINGS */ |
---|