Changeset 69fb9d0 in git


Ignore:
Timestamp:
May 6, 2011, 4:06:31 PM (13 years ago)
Author:
Frank Seelisch <seelisch@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', 'c7af8613769b29c741d6c338945669719f1fc4f8')
Children:
3b0ba67abd225a2bb2c09c675cfe3085aaf67f12
Parents:
ba23594edc15991ab3d4bd71e011e4139bb72c92
git-author:
Frank Seelisch <seelisch@mathematik.uni-kl.de>2011-05-06 16:06:31+02:00
git-committer:
Mohamed Barakat <mohamed.barakat@rwth-aachen.de>2011-11-09 12:31:38+01:00
Message:
finished impl. of alg. ext. fields; now testing...
File:
1 edited

Legend:

Unmodified
Added
Removed
  • libpolys/polys/monomials/p_polys.cc

    rba2359 r69fb9d0  
    14441444       one is only interested in the remainder of the division. In this
    14451445       case, the method will be faster.) */
    1446 poly p_PolyDiv(poly *p, poly divisor, BOOLEAN needResult, ring r)
     1446poly p_PolyDiv(poly * p, poly divisor, BOOLEAN needResult, ring r)
    14471447{
    14481448  assume(divisor != NULL);
    14491449  if (*p == NULL) return NULL;
    14501450 
    1451   /* yet to be implemented by Frank S.;
    1452      for the time being, this should at least compile */
    1453   return NULL;
     1451  poly result = NULL;
     1452  number divisorLT = p_GetCoeff(divisor, r);
     1453  int divisorExp = p_GetExp(divisor, 1, r);
     1454  while (p_Deg(*p, r) > p_Deg(divisor, r))
     1455  {
     1456    /* determine t = LT(*p) / LT(divisor) */
     1457    poly t = p_ISet(1, r);
     1458    number c = n_Div(p_GetCoeff(*p, r), divisorLT, r->cf);
     1459    p_SetCoeff(t, c, r);
     1460    int e = p_GetExp(*p, 1, r) - divisorExp;
     1461    p_SetExp(t, 1, e, r);
     1462    p_Setm(t, r);
     1463    result = p_Add_q(result, p_Copy(t, r), r);
     1464    *p = p_Add_q(*p, p_Neg(t, r), r);
     1465  }
     1466  n_Delete(&divisorLT, r->cf);
     1467  return result;
     1468}
     1469
     1470/* see p_Gcd;
     1471   additional assumption: deg(*p) >= deg(*q);
     1472   must destroy *p and *q (unless one of them is returned) */
     1473poly p_GcdHelper(poly * p, poly * q, ring r)
     1474{
     1475  if (q == NULL) return *p;
     1476  else
     1477  {
     1478    p_PolyDiv(p, *q, FALSE, r);
     1479    return p_GcdHelper(q, p, r);
     1480  }
    14541481}
    14551482
     
    14581485   assumes a global monomial ordering in r;
    14591486   assumes that not both p and q are NULL;
    1460    returns the gcd of p and q */
     1487   returns the gcd of p and q;
     1488   leaves p and q unmodified */
    14611489poly p_Gcd(poly p, poly q, ring r)
    14621490{
    14631491  assume((p != NULL) || (q != NULL));
    1464   if (p == NULL) return q;
    1465   if (q == NULL) return p;
    14661492 
    1467   /* yet to be implemented by Frank S.;
    1468      for the time being, this should at least compile */
    1469   return NULL;
     1493  poly a = p; poly b = q;
     1494  if (p_Deg(a, r) < p_Deg(b, r)) { a = q; b = p; }
     1495  a = p_Copy(a, r); b = p_Copy(b, r);
     1496  return p_GcdHelper(&a, &b, r);
     1497}
     1498
     1499/* see p_ExtGcd;
     1500   additional assumption: deg(*p) >= deg(*q);
     1501   must destroy *p and *q (unless one of them is returned) */
     1502poly p_ExtGcdHelper(poly * p, poly * pFactor, poly * q, poly * qFactor,
     1503                    ring r)
     1504{
     1505  if (q == NULL)
     1506  {
     1507    *qFactor = NULL; *pFactor = p_ISet(1, r); return *p;
     1508  }
     1509  else
     1510  {
     1511    poly pDivQ = p_PolyDiv(p, *q, TRUE, r);
     1512    poly * ppFactor; poly * qqFactor;
     1513    poly theGcd = p_ExtGcdHelper(q, ppFactor, p, qqFactor, r);
     1514    pFactor = qqFactor;
     1515    *qFactor = p_Add_q(*ppFactor,
     1516                       p_Neg(p_Mult_q(fDivG, p_Copy(*qqFactor, r), r), r),
     1517                       r);
     1518    return theGcd;
     1519  }
    14701520}
    14711521
     
    14761526   returns the gcd of p and q;
    14771527   moreover, afterwards *pFactor and *qFactor contain appropriate
    1478    factors such that gcd(p, q) = p * (*pFactor) + q * (*qFactor) */
    1479 poly p_ExtGcd(poly p, poly *pFactor, poly q, poly *qFactor, ring r)
     1528   factors such that gcd(p, q) = p * (*pFactor) + q * (*qFactor);
     1529   leaves p and q unmodified */
     1530poly p_ExtGcd(poly p, poly * pFactor, poly q, poly * qFactor, ring r)
    14801531{
    14811532  assume((p != NULL) || (q != NULL));
    1482   if (p == NULL) { *pFactor = NULL; *qFactor = p_ISet(1, r); return q; };
    1483   if (q == NULL) { *qFactor = NULL; *pFactor = p_ISet(1, r); return p; };
    14841533 
    1485   /* yet to be implemented by Frank S.;
    1486      for the time being, this should at least compile */
    1487   return NULL;
     1534  poly a = p; poly b = q;
     1535  poly * aFactor = pFactor; poly * bFactor = qFactor;
     1536  if (p_Deg(a, r) < p_Deg(b, r))
     1537  { a = q; b = p; aFactor = qFactor, bFactor = pFactor; }
     1538  a = p_Copy(a, r); b = p_Copy(b, r);
     1539  return p_ExtGcdHelper(&a, aFactor, &b, bFactor, r);
    14881540}
    14891541
Note: See TracChangeset for help on using the changeset viewer.