| 1 | /**************************************** |
|---|
| 2 | * Computer Algebra System SINGULAR * |
|---|
| 3 | ****************************************/ |
|---|
| 4 | /*************************************************************** |
|---|
| 5 | * File: p_Mult_q.cc |
|---|
| 6 | * Purpose: multiplication of polynomials |
|---|
| 7 | * Author: obachman (Olaf Bachmann) |
|---|
| 8 | * Created: 8/00 |
|---|
| 9 | * Version: $Id: p_Mult_q.cc,v 1.6 2000-11-23 17:34:11 obachman Exp $ |
|---|
| 10 | *******************************************************************/ |
|---|
| 11 | #include "mod2.h" |
|---|
| 12 | |
|---|
| 13 | /*************************************************************** |
|---|
| 14 | * |
|---|
| 15 | * Returns: p * q, |
|---|
| 16 | * Destroys: if !copy then p, q |
|---|
| 17 | * Assumes: pLength(p) >= 2 pLength(q) >=2 |
|---|
| 18 | ***************************************************************/ |
|---|
| 19 | #include "p_polys.h" |
|---|
| 20 | #include "p_Procs.h" |
|---|
| 21 | #include "p_Numbers.h" |
|---|
| 22 | |
|---|
| 23 | |
|---|
| 24 | poly _p_Mult_q(poly p, poly q, const int copy, const ring r) |
|---|
| 25 | { |
|---|
| 26 | assume(p != NULL && pNext(p) != NULL && q != NULL && pNext(q) != NULL); |
|---|
| 27 | pAssume1(! pHaveCommonMonoms(p, q)); |
|---|
| 28 | p_Test(p, r); |
|---|
| 29 | p_Test(q, r); |
|---|
| 30 | |
|---|
| 31 | poly res = pp_Mult_mm(p,q,r); // holds initially q1*p |
|---|
| 32 | poly qq = pNext(q); // we iter of this |
|---|
| 33 | poly qn = pp_Mult_mm(qq, p,r); // holds p1*qi |
|---|
| 34 | poly pp = pNext(p); // used for Lm(qq)*pp |
|---|
| 35 | poly rr = res; // last monom which is surely not NULL |
|---|
| 36 | poly rn = pNext(res); // pNext(rr) |
|---|
| 37 | number n, n1; |
|---|
| 38 | |
|---|
| 39 | // now the main loop |
|---|
| 40 | Top: |
|---|
| 41 | if (rn == NULL) goto Smaller; |
|---|
| 42 | p_LmCmpAction(rn, qn, r, goto Equal, goto Greater, goto Smaller); |
|---|
| 43 | |
|---|
| 44 | Greater: |
|---|
| 45 | // rn > qn, so iter |
|---|
| 46 | rr = rn; |
|---|
| 47 | pIter(rn); |
|---|
| 48 | goto Top; |
|---|
| 49 | |
|---|
| 50 | // rn < qn, append qn to rr, and compute next Lm(qq)*pp |
|---|
| 51 | Smaller: |
|---|
| 52 | pNext(rr) = qn; |
|---|
| 53 | rr = qn; |
|---|
| 54 | pIter(qn); |
|---|
| 55 | Work: // compute res + Lm(qq)*pp |
|---|
| 56 | if (rn == NULL) |
|---|
| 57 | pNext(rr) = pp_Mult_mm(pp, qq, r); |
|---|
| 58 | else |
|---|
| 59 | { |
|---|
| 60 | pNext(rr) = p_Plus_mm_Mult_qq(rn, qq, pp, r); |
|---|
| 61 | } |
|---|
| 62 | |
|---|
| 63 | pIter(qq); |
|---|
| 64 | if (qq == NULL) goto Finish; |
|---|
| 65 | rn = pNext(rr); |
|---|
| 66 | goto Top; |
|---|
| 67 | |
|---|
| 68 | Equal: |
|---|
| 69 | n1 = pGetCoeff(rn); |
|---|
| 70 | n = n_Add(n1, pGetCoeff(qn), r); |
|---|
| 71 | n_Delete(&n1, r); |
|---|
| 72 | if (n_IsZero(n, r)) |
|---|
| 73 | { |
|---|
| 74 | n_Delete(&n, r); |
|---|
| 75 | rn = p_LmFreeAndNext(rn, r); |
|---|
| 76 | } |
|---|
| 77 | else |
|---|
| 78 | { |
|---|
| 79 | pSetCoeff0(rn, n); |
|---|
| 80 | rr = rn; |
|---|
| 81 | pIter(rn); |
|---|
| 82 | } |
|---|
| 83 | n_Delete(&pGetCoeff(qn),r); |
|---|
| 84 | qn = p_LmFreeAndNext(qn, r); |
|---|
| 85 | goto Work; |
|---|
| 86 | |
|---|
| 87 | Finish: |
|---|
| 88 | if (!copy) |
|---|
| 89 | { |
|---|
| 90 | p_Delete(&p, r); |
|---|
| 91 | p_Delete(&q, r); |
|---|
| 92 | } |
|---|
| 93 | p_Test(res, r); |
|---|
| 94 | return res; |
|---|
| 95 | } |
|---|
| 96 | |
|---|
