1 | /**************************************** |
---|
2 | * Computer Algebra System SINGULAR * |
---|
3 | ****************************************/ |
---|
4 | /* $Id: spolys0.cc,v 1.4 1997-08-01 10:53:08 Singular Exp $ */ |
---|
5 | |
---|
6 | /* |
---|
7 | * ABSTRACT - s-polynomials and reduction in general |
---|
8 | */ |
---|
9 | |
---|
10 | #include <string.h> |
---|
11 | #include "mod2.h" |
---|
12 | #include "tok.h" |
---|
13 | #include "mmemory.h" |
---|
14 | #include "numbers.h" |
---|
15 | #include "polys.h" |
---|
16 | #include "spolys0.h" |
---|
17 | |
---|
18 | /*0 implementation*/ |
---|
19 | |
---|
20 | /* |
---|
21 | * input - output: a, b |
---|
22 | * returns: |
---|
23 | * a := a/gcd(a,b), b := b/gcd(a,b) |
---|
24 | * and return value |
---|
25 | * 0 -> a != 1, b != 1 |
---|
26 | * 1 -> a == 1, b != 1 |
---|
27 | * 2 -> a != 1, b == 1 |
---|
28 | * 3 -> a == 1, b == 1 |
---|
29 | * this value is used to control the spolys |
---|
30 | */ |
---|
31 | static int spCheckCoeff(number *a, number *b) |
---|
32 | { |
---|
33 | int c = 0; |
---|
34 | number an = *a, bn = *b, cn = nGcd(an, bn); |
---|
35 | |
---|
36 | if(nIsOne(cn)) |
---|
37 | { |
---|
38 | an = nCopy(an); |
---|
39 | bn = nCopy(bn); |
---|
40 | } |
---|
41 | else |
---|
42 | { |
---|
43 | an = nIntDiv(an, cn); |
---|
44 | bn = nIntDiv(bn, cn); |
---|
45 | } |
---|
46 | nDelete(&cn); |
---|
47 | if (nIsOne(an)) |
---|
48 | { |
---|
49 | c = 1; |
---|
50 | } |
---|
51 | if (nIsOne(bn)) |
---|
52 | { |
---|
53 | c += 2; |
---|
54 | } |
---|
55 | *a = an; |
---|
56 | *b = bn; |
---|
57 | return c; |
---|
58 | } |
---|
59 | |
---|
60 | /*2 |
---|
61 | * transforms a1 to a polynomial |
---|
62 | */ |
---|
63 | void spModuleToPoly(poly a1) |
---|
64 | { |
---|
65 | #ifdef PDEBUG |
---|
66 | poly t=a1; |
---|
67 | pTest(t); |
---|
68 | #endif |
---|
69 | do |
---|
70 | { |
---|
71 | pSetComp(a1,0); |
---|
72 | pIter(a1); |
---|
73 | } while (a1!=NULL); |
---|
74 | #ifdef PDEBUG |
---|
75 | pTest(t); |
---|
76 | #endif |
---|
77 | } |
---|
78 | |
---|
79 | /*2 |
---|
80 | * assume m = L(m) and Lc(m) = 1 |
---|
81 | * pNext(m) = result = p*m |
---|
82 | * do not destroy p |
---|
83 | */ |
---|
84 | static void spGMultCopy0(poly p, poly m, poly spNoether) |
---|
85 | { |
---|
86 | poly a, b; |
---|
87 | |
---|
88 | a = m; |
---|
89 | if (spNoether==NULL) |
---|
90 | { |
---|
91 | do |
---|
92 | { |
---|
93 | a = pNext(a) = pNew(); |
---|
94 | spMemcpy(a,p); |
---|
95 | spMonAdd(a,m); |
---|
96 | pSetCoeff0(a,nCopy(pGetCoeff(a))); |
---|
97 | pIter(p); |
---|
98 | } |
---|
99 | while (p!=NULL); |
---|
100 | pNext(a) = NULL; |
---|
101 | return; |
---|
102 | } |
---|
103 | else |
---|
104 | { |
---|
105 | do |
---|
106 | { |
---|
107 | b = pNext(a) = pNew(); |
---|
108 | spMemcpy(b,p); |
---|
109 | spMonAdd(b,m); |
---|
110 | if (pComp0(b, spNoether) == -1) |
---|
111 | { |
---|
112 | pFree1(b); |
---|
113 | pNext(a) = NULL; |
---|
114 | return; |
---|
115 | } |
---|
116 | a = b; |
---|
117 | pSetCoeff0(a,nCopy(pGetCoeff(a))); |
---|
118 | pIter(p); |
---|
119 | } while (p!=NULL); |
---|
120 | pNext(a) = NULL; |
---|
121 | } |
---|
122 | } |
---|
123 | |
---|
124 | /*2 |
---|
125 | * assume m = L(m) and Lc(m) = -1 |
---|
126 | * pNext(n) = result = p*m |
---|
127 | * do not destroy p |
---|
128 | */ |
---|
129 | static void spGMultCopy1(poly p, poly m, poly n,poly spNoether) |
---|
130 | { |
---|
131 | poly a, b; |
---|
132 | |
---|
133 | a = n; |
---|
134 | if (spNoether==NULL) |
---|
135 | { |
---|
136 | do |
---|
137 | { |
---|
138 | number tmp; |
---|
139 | a = pNext(a) = pNew(); |
---|
140 | spMemcpy(a,p); |
---|
141 | spMonAdd(a,m); |
---|
142 | tmp=nCopy(pGetCoeff(a)); |
---|
143 | tmp=nNeg(tmp); |
---|
144 | pSetCoeff0(a,tmp); |
---|
145 | pIter(p); |
---|
146 | } |
---|
147 | while (p!=NULL); |
---|
148 | pNext(a) = NULL; |
---|
149 | return; |
---|
150 | } |
---|
151 | else |
---|
152 | { |
---|
153 | do |
---|
154 | { |
---|
155 | b = pNext(a) = pNew(); |
---|
156 | spMemcpy(b,p); |
---|
157 | spMonAdd(b,m); |
---|
158 | if (pComp(b, spNoether) == -1) |
---|
159 | { |
---|
160 | pFree1(b); |
---|
161 | pNext(a) = NULL; |
---|
162 | return; |
---|
163 | } |
---|
164 | a = b; |
---|
165 | number tmp; |
---|
166 | tmp=nCopy(pGetCoeff(a)); |
---|
167 | tmp=nNeg(tmp); |
---|
168 | pSetCoeff0(a,tmp); |
---|
169 | pIter(p); |
---|
170 | } |
---|
171 | while (p!=NULL); |
---|
172 | pNext(a) = NULL; |
---|
173 | } |
---|
174 | } |
---|
175 | |
---|
176 | /*2 |
---|
177 | * assume m = L(m) and Lc(m) = 1 |
---|
178 | * pNext(m) = result = a2-a1*m |
---|
179 | * do not destroy a1, but a2 |
---|
180 | */ |
---|
181 | static void spGSpolyLoop1(poly a1, poly a2, poly m, poly spNoether) |
---|
182 | { |
---|
183 | poly a, b, s; |
---|
184 | number tb; |
---|
185 | int c; |
---|
186 | |
---|
187 | if (a2==NULL) |
---|
188 | { |
---|
189 | spGMultCopy1(a1, m, m,spNoether); |
---|
190 | return; |
---|
191 | } |
---|
192 | a = m; |
---|
193 | b = pNew(); |
---|
194 | spMemcpy(b,a1); |
---|
195 | spMonAdd(b,m); |
---|
196 | loop |
---|
197 | { |
---|
198 | c = pComp0(b, a2); |
---|
199 | if (c == 1) |
---|
200 | { |
---|
201 | number tmp=nCopy(pGetCoeff(b)); |
---|
202 | tmp=nNeg(tmp); |
---|
203 | pSetCoeff0(b,tmp); |
---|
204 | a = pNext(a) = b; |
---|
205 | pIter(a1); |
---|
206 | if (a1!=NULL) |
---|
207 | { |
---|
208 | b = pNew(); |
---|
209 | spMemcpy(b,a1); |
---|
210 | spMonAdd(b,m); |
---|
211 | } |
---|
212 | else |
---|
213 | { |
---|
214 | pNext(a) = a2; |
---|
215 | return; |
---|
216 | } |
---|
217 | } |
---|
218 | else if (c == -1) |
---|
219 | { |
---|
220 | a = pNext(a) = a2; |
---|
221 | pIter(a2); |
---|
222 | if (a2==NULL) |
---|
223 | { |
---|
224 | pFree1(b); |
---|
225 | spGMultCopy1(a1, m, a,spNoether); |
---|
226 | return; |
---|
227 | } |
---|
228 | } |
---|
229 | else |
---|
230 | { |
---|
231 | tb = pGetCoeff(a2); |
---|
232 | if (!nEqual(tb,pGetCoeff(a1))) |
---|
233 | { |
---|
234 | tb = nSub(tb,pGetCoeff(a1)); |
---|
235 | pSetCoeff(a2,tb); |
---|
236 | a = pNext(a) = a2; |
---|
237 | pIter(a2); |
---|
238 | } |
---|
239 | else |
---|
240 | { |
---|
241 | s = a2; |
---|
242 | pIter(a2); |
---|
243 | nDelete(&tb); |
---|
244 | pFree1(s); |
---|
245 | } |
---|
246 | pIter(a1); |
---|
247 | if (a1==NULL) |
---|
248 | { |
---|
249 | pFree1(b); |
---|
250 | pNext(a) = a2; |
---|
251 | return; |
---|
252 | } |
---|
253 | if (a2==NULL) |
---|
254 | { |
---|
255 | pFree1(b); |
---|
256 | spGMultCopy1(a1, m, a,spNoether); |
---|
257 | return; |
---|
258 | } |
---|
259 | spMemcpy(b,a1); |
---|
260 | spMonAdd(b,m); |
---|
261 | } |
---|
262 | } |
---|
263 | } |
---|
264 | |
---|
265 | /*2 |
---|
266 | * assume m = L(m) and Lc(m) = exp |
---|
267 | * pNext(n) = result = p*m |
---|
268 | * do not destroy p |
---|
269 | */ |
---|
270 | static void spGMultCopyX(poly p, poly m, poly n, number exp, poly spNoether) |
---|
271 | { |
---|
272 | poly a, b; |
---|
273 | |
---|
274 | a = n; |
---|
275 | if (spNoether==NULL) |
---|
276 | { |
---|
277 | do |
---|
278 | { |
---|
279 | a = pNext(a) = pNew(); |
---|
280 | spMemcpy(a,p); |
---|
281 | spMonAdd(a,m); |
---|
282 | pSetCoeff0(a,nMult(pGetCoeff(p),exp)); |
---|
283 | pIter(p); |
---|
284 | } while (p!=NULL); |
---|
285 | pNext(a) = NULL; |
---|
286 | return; |
---|
287 | } |
---|
288 | else |
---|
289 | { |
---|
290 | do |
---|
291 | { |
---|
292 | b = pNext(a) = pNew(); |
---|
293 | spMemcpy(b,p); |
---|
294 | spMonAdd(b,m); |
---|
295 | if (pComp(b, spNoether) == -1) |
---|
296 | { |
---|
297 | pFree1(b); |
---|
298 | pNext(a) = NULL; |
---|
299 | return; |
---|
300 | } |
---|
301 | a = b; |
---|
302 | pSetCoeff0(a,nMult(pGetCoeff(p),exp)); |
---|
303 | pIter(p); |
---|
304 | } while (p!=NULL); |
---|
305 | pNext(a) = NULL; |
---|
306 | } |
---|
307 | } |
---|
308 | |
---|
309 | /*2 |
---|
310 | * assume m = L(m) |
---|
311 | * pNext(m) = result = a2-a1*m |
---|
312 | * do not destroy a1, but a2 |
---|
313 | */ |
---|
314 | static void spGSpolyLoop(poly a1, poly a2, poly m,poly spNoether) |
---|
315 | { |
---|
316 | poly a, b, s; |
---|
317 | number tm = pGetCoeff(m); |
---|
318 | number tneg,tb,t; |
---|
319 | int c; |
---|
320 | |
---|
321 | tneg = nCopy(tm); |
---|
322 | tneg = nNeg(tneg); |
---|
323 | if (a2==NULL) |
---|
324 | { |
---|
325 | spGMultCopyX(a1, m, m, tneg,spNoether); |
---|
326 | nDelete(&tneg); |
---|
327 | return; |
---|
328 | } |
---|
329 | a = m; |
---|
330 | b = pNew(); |
---|
331 | spMemcpy(b,a1); |
---|
332 | spMonAdd(b,m); |
---|
333 | loop |
---|
334 | { |
---|
335 | c = pComp0(b, a2); |
---|
336 | if (c == 1) |
---|
337 | { |
---|
338 | pSetCoeff0(b,nMult(pGetCoeff(a1),tneg)); |
---|
339 | a = pNext(a) = b; |
---|
340 | pIter(a1); |
---|
341 | if (a1!=NULL) |
---|
342 | { |
---|
343 | b = pNew(); |
---|
344 | spMemcpy(b,a1); |
---|
345 | spMonAdd(b,m); |
---|
346 | } |
---|
347 | else |
---|
348 | { |
---|
349 | pNext(a) = a2; |
---|
350 | nDelete(&tneg); |
---|
351 | return; |
---|
352 | } |
---|
353 | } |
---|
354 | else if (c == -1) |
---|
355 | { |
---|
356 | a = pNext(a) = a2; |
---|
357 | pIter(a2); |
---|
358 | if (a2==NULL) |
---|
359 | { |
---|
360 | pFree1(b); |
---|
361 | spGMultCopyX(a1, m, a, tneg,spNoether); |
---|
362 | nDelete(&tneg); |
---|
363 | return; |
---|
364 | } |
---|
365 | } |
---|
366 | else |
---|
367 | { |
---|
368 | t = pGetCoeff(a2); |
---|
369 | tb = nMult(pGetCoeff(a1),tm); |
---|
370 | if (!nEqual(t,tb)) |
---|
371 | { |
---|
372 | t = nSub(t,tb); |
---|
373 | pSetCoeff(a2,t); |
---|
374 | a = pNext(a) = a2; |
---|
375 | pIter(a2); |
---|
376 | } |
---|
377 | else |
---|
378 | { |
---|
379 | s = a2; |
---|
380 | pIter(a2); |
---|
381 | nDelete(&t); |
---|
382 | pFree1(s); |
---|
383 | } |
---|
384 | nDelete(&tb); |
---|
385 | pIter(a1); |
---|
386 | if (a1==NULL) |
---|
387 | { |
---|
388 | pFree1(b); |
---|
389 | pNext(a) = a2; |
---|
390 | nDelete(&tneg); |
---|
391 | return; |
---|
392 | } |
---|
393 | if (a2==NULL) |
---|
394 | { |
---|
395 | pFree1(b); |
---|
396 | spGMultCopyX(a1, m, a, tneg,spNoether); |
---|
397 | nDelete(&tneg); |
---|
398 | return; |
---|
399 | } |
---|
400 | spMemcpy(b,a1); |
---|
401 | spMonAdd(b,m); |
---|
402 | } |
---|
403 | } |
---|
404 | } |
---|
405 | |
---|
406 | /*2 |
---|
407 | * reduction of p2 with p1 |
---|
408 | * do not destroy p1, but p2 |
---|
409 | */ |
---|
410 | poly spGSpolyRed(poly p1, poly p2,poly spNoether) |
---|
411 | { |
---|
412 | poly a1 = pNext(p1), a2 = pNext(p2); |
---|
413 | number an = pGetCoeff(p1), bn = pGetCoeff(p2); |
---|
414 | int ct = spCheckCoeff(&an, &bn); |
---|
415 | |
---|
416 | pSetCoeff(p2,bn); |
---|
417 | if(a1==NULL) |
---|
418 | { |
---|
419 | nDelete(&an); |
---|
420 | nDelete(&bn); |
---|
421 | pFree1(p2); |
---|
422 | return a2; |
---|
423 | } |
---|
424 | if ((ct == 0) || (ct == 2)) |
---|
425 | { |
---|
426 | pMultN(a2, an); |
---|
427 | } |
---|
428 | nDelete(&an); |
---|
429 | BOOLEAN reset_vec=FALSE; |
---|
430 | if (pGetComp(p1) != pGetComp(p2)) |
---|
431 | { |
---|
432 | pSetCompP(a1,pGetComp(p2)); |
---|
433 | reset_vec=TRUE; |
---|
434 | } |
---|
435 | spMonSub(p2,p1); |
---|
436 | if (ct < 2) |
---|
437 | { |
---|
438 | spGSpolyLoop(a1, a2, p2,spNoether); |
---|
439 | } |
---|
440 | else |
---|
441 | { |
---|
442 | spGSpolyLoop1(a1, a2, p2,spNoether); |
---|
443 | } |
---|
444 | a2 = pNext(p2); |
---|
445 | if (reset_vec) |
---|
446 | { |
---|
447 | spModuleToPoly(a1); |
---|
448 | } |
---|
449 | nDelete(&bn); |
---|
450 | pFree1(p2); |
---|
451 | return a2; |
---|
452 | } |
---|
453 | |
---|
454 | /*2 |
---|
455 | * reduction of tail(q) with p1 |
---|
456 | * lead(p1) divides lead(pNext(q2)) and pNext(q2) is reduced |
---|
457 | * do not destroy p1, but tail(q) |
---|
458 | */ |
---|
459 | void spGSpolyTail(poly p1, poly q, poly q2, poly spNoether) |
---|
460 | { |
---|
461 | number t; |
---|
462 | poly m, h; |
---|
463 | poly a1 = pNext(p1), p2 = pNext(q2), a2 = pNext(p2); |
---|
464 | number an = pGetCoeff(p1), bn = pGetCoeff(p2); |
---|
465 | int ct = spCheckCoeff(&an, &bn); |
---|
466 | BOOLEAN reset_vec=FALSE; |
---|
467 | |
---|
468 | if(a1==NULL) |
---|
469 | { |
---|
470 | nDelete(&an); |
---|
471 | nDelete(&bn); |
---|
472 | nDelete(&pGetCoeff(p2)); |
---|
473 | pFree1(p2); |
---|
474 | pNext(q2) = a2; |
---|
475 | return; |
---|
476 | } |
---|
477 | if (p1 != q) |
---|
478 | { |
---|
479 | m = p2; |
---|
480 | pSetCoeff(m,bn); |
---|
481 | } |
---|
482 | else |
---|
483 | { |
---|
484 | m = pNew(); |
---|
485 | spMemcpy(m,p2); |
---|
486 | pSetCoeff0(m,bn); |
---|
487 | a2 = pCopy(a2); |
---|
488 | } |
---|
489 | if ((ct == 0) || (ct == 2)) |
---|
490 | { |
---|
491 | pMultN(a2, an); |
---|
492 | } |
---|
493 | if ((pGetComp(p1) != pGetComp(p2)) |
---|
494 | && (pGetComp(p1)==0)) |
---|
495 | { |
---|
496 | pSetCompP(a1,pGetComp(p2)); |
---|
497 | reset_vec=TRUE; |
---|
498 | } |
---|
499 | spMonSub(m,p1); |
---|
500 | if (ct < 2) |
---|
501 | { |
---|
502 | spGSpolyLoop(a1, a2, m,spNoether); |
---|
503 | } |
---|
504 | else |
---|
505 | { |
---|
506 | spGSpolyLoop1(a1, a2, m,spNoether); |
---|
507 | } |
---|
508 | if ((ct == 0) || (ct == 2)) |
---|
509 | { |
---|
510 | h = q; |
---|
511 | do |
---|
512 | { |
---|
513 | t = nMult(pGetCoeff(h),an); |
---|
514 | pSetCoeff(h,t); |
---|
515 | pIter(h); |
---|
516 | } |
---|
517 | while (h != p2); |
---|
518 | } |
---|
519 | h = pNext(m); |
---|
520 | nDelete(&an); |
---|
521 | nDelete(&bn); |
---|
522 | pFree1(m); |
---|
523 | pNext(q2) = h; |
---|
524 | if (reset_vec) |
---|
525 | spModuleToPoly(a1); |
---|
526 | if (p1 == q) |
---|
527 | { |
---|
528 | pDelete(&p2); |
---|
529 | } |
---|
530 | } |
---|
531 | |
---|
532 | /*2 |
---|
533 | * reduction of p2 with p1 |
---|
534 | * do not destroy p1 and p2 |
---|
535 | */ |
---|
536 | poly spGSpolyRedNew(poly p1, poly p2,poly spNoether) |
---|
537 | { |
---|
538 | poly m; |
---|
539 | poly a1 = pNext(p1), a2 = pNext(p2); |
---|
540 | number an = pGetCoeff(p1), bn = pGetCoeff(p2); |
---|
541 | int ct = spCheckCoeff(&an, &bn); |
---|
542 | |
---|
543 | if(a1==NULL) |
---|
544 | { |
---|
545 | nDelete(&an); |
---|
546 | nDelete(&bn); |
---|
547 | return pCopy(a2); |
---|
548 | } |
---|
549 | if ((ct == 0) || (ct == 2)) |
---|
550 | { |
---|
551 | a2 = pMultCopyN(a2,an); |
---|
552 | } |
---|
553 | else |
---|
554 | { |
---|
555 | a2 = pCopy(a2); |
---|
556 | } |
---|
557 | pTest(a2); |
---|
558 | pTest(p2); |
---|
559 | nDelete(&an); |
---|
560 | BOOLEAN reset_vec=FALSE; |
---|
561 | if (pGetComp(p1) != pGetComp(p2)) |
---|
562 | { |
---|
563 | pSetCompP(a1,pGetComp(p2)); |
---|
564 | reset_vec=TRUE; |
---|
565 | } |
---|
566 | m = pNew(); |
---|
567 | spMemcpy(m,p2); |
---|
568 | spMonSub(m,p1); |
---|
569 | if (ct < 2) |
---|
570 | { |
---|
571 | pSetCoeff0(m,bn); |
---|
572 | spGSpolyLoop(a1, a2, m,spNoether); |
---|
573 | } |
---|
574 | else |
---|
575 | { |
---|
576 | spGSpolyLoop1(a1, a2, m,spNoether); |
---|
577 | } |
---|
578 | a2 = pNext(m); |
---|
579 | pTest(a2); |
---|
580 | pTest(p2); |
---|
581 | if (reset_vec) |
---|
582 | { |
---|
583 | spModuleToPoly(a1); |
---|
584 | } |
---|
585 | nDelete(&bn); |
---|
586 | pFree1(m); |
---|
587 | pTest(a2); |
---|
588 | pTest(p2); |
---|
589 | return a2; |
---|
590 | } |
---|
591 | |
---|
592 | /*2 |
---|
593 | * creates the S-polynomial of p1 and p2 |
---|
594 | * do not destroy p1 and p2 |
---|
595 | */ |
---|
596 | poly spGSpolyCreate(poly p1, poly p2,poly spNoether) |
---|
597 | { |
---|
598 | short x; |
---|
599 | poly m, b; |
---|
600 | poly a1 = pNext(p1), a2 = pNext(p2); |
---|
601 | number an = pGetCoeff(p1), bn = pGetCoeff(p2); |
---|
602 | int co=0, ct = spCheckCoeff(&an, &bn); |
---|
603 | |
---|
604 | if (pGetComp(p1)!=pGetComp(p2)) |
---|
605 | { |
---|
606 | if (pGetComp(p1)==0) |
---|
607 | { |
---|
608 | co=1; |
---|
609 | pSetCompP(p1,pGetComp(p2)); |
---|
610 | } |
---|
611 | else |
---|
612 | { |
---|
613 | co=2; |
---|
614 | pSetCompP(p2,pGetComp(p1)); |
---|
615 | } |
---|
616 | } |
---|
617 | b = pNew(); |
---|
618 | m = pNew(); |
---|
619 | for (int i = pVariables; i; i--) |
---|
620 | { |
---|
621 | x = pGetExp(p1,i) - pGetExp(p2,i); |
---|
622 | if (x > 0) |
---|
623 | { |
---|
624 | pSetExp(b,i,x); |
---|
625 | pSetExp(m,i,0); |
---|
626 | } |
---|
627 | else |
---|
628 | { |
---|
629 | pSetExp(m,i,-x); |
---|
630 | pSetExp(b,i,0); |
---|
631 | } |
---|
632 | } |
---|
633 | pSetm(m); |
---|
634 | pSetm(b); |
---|
635 | if (a2!=NULL) |
---|
636 | { |
---|
637 | if ((ct == 0) || (ct == 2)) |
---|
638 | { |
---|
639 | spGMultCopyX(a2, b, b, an,spNoether); |
---|
640 | } |
---|
641 | else |
---|
642 | { |
---|
643 | spGMultCopy0(a2, b,spNoether); |
---|
644 | } |
---|
645 | a2 = pNext(b); |
---|
646 | } |
---|
647 | nDelete(&an); |
---|
648 | pFree1(b); |
---|
649 | if (a1!=NULL) |
---|
650 | { |
---|
651 | if (ct < 2) |
---|
652 | { |
---|
653 | pSetCoeff0(m,bn); |
---|
654 | spGSpolyLoop(a1, a2, m,spNoether); |
---|
655 | } |
---|
656 | else |
---|
657 | { |
---|
658 | spGSpolyLoop1(a1, a2, m,spNoether); |
---|
659 | } |
---|
660 | a2 = pNext(m); |
---|
661 | } |
---|
662 | nDelete(&bn); |
---|
663 | pFree1(m); |
---|
664 | if (co != 0) |
---|
665 | { |
---|
666 | if (co==1) |
---|
667 | { |
---|
668 | spModuleToPoly(p1); |
---|
669 | } |
---|
670 | else |
---|
671 | { |
---|
672 | spModuleToPoly(p2); |
---|
673 | } |
---|
674 | } |
---|
675 | return a2; |
---|
676 | } |
---|
677 | |
---|
678 | void spShort1(poly b, poly a, poly m) |
---|
679 | { |
---|
680 | for(int i=pVariables; i; i--) |
---|
681 | { |
---|
682 | if(pGetExp(m,i)<0) |
---|
683 | { |
---|
684 | pSetExp(b,i,pGetExp(a,i)); |
---|
685 | } |
---|
686 | } |
---|
687 | pFree1(m); |
---|
688 | pSetm(b); |
---|
689 | } |
---|
690 | |
---|
691 | void spShort2(poly b, poly a, poly m) |
---|
692 | { |
---|
693 | short x; |
---|
694 | pSetComp(b,pGetComp(a)); |
---|
695 | for(int i=pVariables; i; i--) |
---|
696 | { |
---|
697 | if(pGetExp(m,i)<0) |
---|
698 | x = pGetExp(a,i)-pGetExp(m,i); |
---|
699 | else |
---|
700 | x = pGetExp(a,i); |
---|
701 | pSetExp(b,i,x); |
---|
702 | } |
---|
703 | pFree1(m); |
---|
704 | pSetm(b); |
---|
705 | } |
---|
706 | |
---|
707 | /*2 |
---|
708 | * creates the leading term of the S-polynomial of p1 and p2 |
---|
709 | * do not destroy p1 and p2 |
---|
710 | * remarks: |
---|
711 | * 1. the coefficient is 0 (nNew) |
---|
712 | * 2. in a first step the monomials from p1 are |
---|
713 | * multiplied with L(p2-p1), hence the multiplication |
---|
714 | * must be additive and further the transformation |
---|
715 | * spShort1 and spShort2 are needed |
---|
716 | */ |
---|
717 | poly spGSpolyShortBba(poly p1, poly p2) |
---|
718 | { |
---|
719 | poly a1 = pNext(p1), a2 = pNext(p2); |
---|
720 | poly m,b; |
---|
721 | number ta,tb,t; |
---|
722 | int c; |
---|
723 | int co=0; |
---|
724 | if (pGetComp(p1)!=pGetComp(p2)) |
---|
725 | { |
---|
726 | if (pGetComp(p1)==0) |
---|
727 | { |
---|
728 | co=1; |
---|
729 | pSetCompP(p1,pGetComp(p2)); |
---|
730 | } |
---|
731 | else |
---|
732 | { |
---|
733 | co=2; |
---|
734 | pSetCompP(p2,pGetComp(p1)); |
---|
735 | } |
---|
736 | } |
---|
737 | b = pNew(); |
---|
738 | m = pNew(); |
---|
739 | pSetComp(b,pGetComp(p1)); |
---|
740 | spMemcpy(m,p2); |
---|
741 | spMonSub(m,p1); |
---|
742 | if(a1!=NULL) |
---|
743 | { |
---|
744 | spMemcpy(b,a1); |
---|
745 | spMonAdd(b,m); |
---|
746 | if(a2==NULL) |
---|
747 | { |
---|
748 | spShort1(b,a1,m); |
---|
749 | nNew(&(pGetCoeff(b))); |
---|
750 | if (co==1) spModuleToPoly(p1); |
---|
751 | else if (co==2) spModuleToPoly(p2); |
---|
752 | return b; |
---|
753 | } |
---|
754 | } |
---|
755 | else |
---|
756 | { |
---|
757 | if(a2!=NULL) |
---|
758 | { |
---|
759 | spShort2(b,a2,m); |
---|
760 | nNew(&(pGetCoeff(b))); |
---|
761 | if (co==1) spModuleToPoly(p1); |
---|
762 | else if (co==2) spModuleToPoly(p2); |
---|
763 | return b; |
---|
764 | } |
---|
765 | else |
---|
766 | { |
---|
767 | pFree1(m); |
---|
768 | pFree1(b); |
---|
769 | if (co==1) spModuleToPoly(p1); |
---|
770 | else if (co==2) spModuleToPoly(p2); |
---|
771 | return NULL; |
---|
772 | } |
---|
773 | } |
---|
774 | loop |
---|
775 | { |
---|
776 | c = pComp0(b,a2); |
---|
777 | if (c == 1) |
---|
778 | { |
---|
779 | spShort1(b,a1,m); |
---|
780 | nNew(&(pGetCoeff(b))); |
---|
781 | break; |
---|
782 | } |
---|
783 | else if (c == -1) |
---|
784 | { |
---|
785 | spShort2(b,a2,m); |
---|
786 | nNew(&(pGetCoeff(b))); |
---|
787 | break; |
---|
788 | } |
---|
789 | else |
---|
790 | { |
---|
791 | if (nIsOne(pGetCoeff(p1))) |
---|
792 | { |
---|
793 | if (nIsOne(pGetCoeff(p2))) |
---|
794 | t = nSub(pGetCoeff(a2), pGetCoeff(a1)); |
---|
795 | else |
---|
796 | { |
---|
797 | ta = nMult(pGetCoeff(a1), pGetCoeff(p2)); |
---|
798 | t = nSub(ta, pGetCoeff(a2)); |
---|
799 | nDelete(&ta); |
---|
800 | } |
---|
801 | } |
---|
802 | else |
---|
803 | { |
---|
804 | if (nIsOne(pGetCoeff(p2))) |
---|
805 | { |
---|
806 | ta = nMult(pGetCoeff(a2), pGetCoeff(p1)); |
---|
807 | t = nSub(ta, pGetCoeff(a1)); |
---|
808 | } |
---|
809 | else |
---|
810 | { |
---|
811 | ta = nMult(pGetCoeff(a1), pGetCoeff(p2)); |
---|
812 | tb = nMult(pGetCoeff(a2), pGetCoeff(p1)); |
---|
813 | t = nSub(ta, tb); |
---|
814 | nDelete(&tb); |
---|
815 | } |
---|
816 | nDelete(&ta); |
---|
817 | } |
---|
818 | if (!nIsZero(t)) |
---|
819 | { |
---|
820 | nDelete(&t); |
---|
821 | spShort1(b,a1,m); |
---|
822 | nNew(&(pGetCoeff(b))); |
---|
823 | break; |
---|
824 | } |
---|
825 | nDelete(&t); |
---|
826 | pIter(a2); |
---|
827 | pIter(a1); |
---|
828 | if(a1!=NULL) |
---|
829 | { |
---|
830 | spMemcpy(b,a1); |
---|
831 | spMonAdd(b,m); |
---|
832 | if(a2==NULL) |
---|
833 | { |
---|
834 | spShort1(b,a1,m); |
---|
835 | nNew(&(pGetCoeff(b))); |
---|
836 | break; |
---|
837 | } |
---|
838 | } |
---|
839 | else |
---|
840 | { |
---|
841 | if(a2!=NULL) |
---|
842 | { |
---|
843 | spShort2(b,a2,m); |
---|
844 | nNew(&(pGetCoeff(b))); |
---|
845 | break; |
---|
846 | } |
---|
847 | else |
---|
848 | { |
---|
849 | pFree1(m); |
---|
850 | pFree1(b); |
---|
851 | b= NULL; break; |
---|
852 | } |
---|
853 | } |
---|
854 | } |
---|
855 | } |
---|
856 | if (co==1) spModuleToPoly(p1); |
---|
857 | else if (co==2) spModuleToPoly(p2); |
---|
858 | return b; |
---|
859 | } |
---|
860 | |
---|
861 | /*2 |
---|
862 | * creates the last term of the S-polynomial of p1 and p2 |
---|
863 | * in order to compute the ecart |
---|
864 | * do not destroy p1 and p2 |
---|
865 | * remarks: |
---|
866 | * 1. the coefficient is undefined |
---|
867 | * 2. see above |
---|
868 | */ |
---|
869 | /* |
---|
870 | *static poly spGSpolyLast(poly p1, poly p2) |
---|
871 | *{ |
---|
872 | * poly a1 = pNext(p1), a2 = pNext(p2); |
---|
873 | * poly m, b, L1, L2; |
---|
874 | * number ta,tb,t; |
---|
875 | * int c; |
---|
876 | * |
---|
877 | * m = pNew(); |
---|
878 | * b = pNew(); |
---|
879 | * spMemcpy(m,p2); |
---|
880 | * spMonSub(m,p1); |
---|
881 | * pSetComp(b,pGetComp(p1)); |
---|
882 | * if (a2) |
---|
883 | * { |
---|
884 | * while (pNext(a2)) |
---|
885 | * pIter(a2); |
---|
886 | * } |
---|
887 | * if (a1) |
---|
888 | * { |
---|
889 | * while (pNext(a1)) |
---|
890 | * pIter(a1); |
---|
891 | * spMemcpy(b,a1); |
---|
892 | * spMonAdd(b,m); |
---|
893 | * } |
---|
894 | * else |
---|
895 | * { |
---|
896 | * spShort2(b,a2,m); |
---|
897 | * return b; |
---|
898 | * } |
---|
899 | * if(!a2) |
---|
900 | * { |
---|
901 | * spShort1(b,a1,m); |
---|
902 | * return b; |
---|
903 | * } |
---|
904 | * for (; ; ) |
---|
905 | * { |
---|
906 | * c = pComp0(b, a2); |
---|
907 | * if (c == -1) |
---|
908 | * { |
---|
909 | * spShort1(b,a1,m); |
---|
910 | * return b; |
---|
911 | * } |
---|
912 | * else if (c == 1) |
---|
913 | * { |
---|
914 | * spShort2(b,a2,m); |
---|
915 | * return b; |
---|
916 | * } |
---|
917 | * else |
---|
918 | * { |
---|
919 | * if (nIsOne(pGetCoeff(p1))) |
---|
920 | * { |
---|
921 | * if (nIsOne(pGetCoeff(p2))) |
---|
922 | * t = nSub(pGetCoeff(a2), pGetCoeff(a1)); |
---|
923 | * else |
---|
924 | * { |
---|
925 | * ta = nMult(pGetCoeff(a1), pGetCoeff(p2)); |
---|
926 | * t = nSub(ta, pGetCoeff(a2)); |
---|
927 | * nDelete(&ta); |
---|
928 | * } |
---|
929 | * } |
---|
930 | * else |
---|
931 | * { |
---|
932 | * if (nIsOne(pGetCoeff(p2))) |
---|
933 | * { |
---|
934 | * ta = nMult(pGetCoeff(a2), pGetCoeff(p1)); |
---|
935 | * t = nSub(ta, pGetCoeff(a1)); |
---|
936 | * } |
---|
937 | * else |
---|
938 | * { |
---|
939 | * ta = nMult(pGetCoeff(a1), pGetCoeff(p2)); |
---|
940 | * tb = nMult(pGetCoeff(a2), pGetCoeff(p1)); |
---|
941 | * t = nSub(ta, tb); |
---|
942 | * nDelete(&tb); |
---|
943 | * } |
---|
944 | * nDelete(&ta); |
---|
945 | * } |
---|
946 | * if (!nIsZero(t)) |
---|
947 | * { |
---|
948 | * nDelete(&t); |
---|
949 | * spShort1(b,a1,m); |
---|
950 | * return b; |
---|
951 | * } |
---|
952 | * nDelete(&t); |
---|
953 | * if (a1 != pNext(p1)) |
---|
954 | * { |
---|
955 | * L1 = a1; |
---|
956 | * a1 = pNext(p1); |
---|
957 | * while (pNext(a1) != L1) |
---|
958 | * pIter(a1); |
---|
959 | * spMemcpy(b,a1); |
---|
960 | * spMonAdd(b,m); |
---|
961 | * } |
---|
962 | * if (a2 != pNext(p2)) |
---|
963 | * { |
---|
964 | * L2 = a2; |
---|
965 | * a2 = pNext(p2); |
---|
966 | * while (pNext(a2) != L2) |
---|
967 | * pIter(a2); |
---|
968 | * } |
---|
969 | * } |
---|
970 | * } |
---|
971 | *} |
---|
972 | */ |
---|
973 | /*2 |
---|
974 | * creates the leading term of the S-polynomial of p1 and p2 |
---|
975 | * and computes the ecart under the assumtion that |
---|
976 | * the last term of the S-polynomial is the greatest |
---|
977 | * do not destroy p1 and p2 |
---|
978 | */ |
---|
979 | /* |
---|
980 | *poly spGSpolyShortMora(poly p1, poly p2, int *ecart) |
---|
981 | *{ |
---|
982 | * poly p, q; |
---|
983 | * |
---|
984 | * p = spGSpolyShortBba(p1, p2, ecart); |
---|
985 | * *ecart = 0; |
---|
986 | * if(p) |
---|
987 | * { |
---|
988 | * if(spNoether==NULL) |
---|
989 | * { |
---|
990 | * q = spGSpolyLast(p1, p2); |
---|
991 | * *ecart = pFDeg(q) - pFDeg(p); |
---|
992 | * pFree1(q); |
---|
993 | * return p; |
---|
994 | * } |
---|
995 | * if (pComp(p, spNoether) == -1) |
---|
996 | * { |
---|
997 | * pFree1(p); |
---|
998 | * return NULL; |
---|
999 | * } |
---|
1000 | * q = spGSpolyLast(p1, p2); |
---|
1001 | * if (pComp(q, spNoether) == -1) |
---|
1002 | * *ecart = pFDeg(spNoether) - pFDeg(p); |
---|
1003 | * else |
---|
1004 | * *ecart = pFDeg(q) - pFDeg(p); |
---|
1005 | * pFree1(q); |
---|
1006 | * } |
---|
1007 | * return p; |
---|
1008 | *} |
---|
1009 | */ |
---|