Changeset ec970e in git for factory/int_poly.cc


Ignore:
Timestamp:
Jul 6, 2011, 2:41:32 PM (12 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')
Children:
42281d63800a31c74efe7fb9afecba0a2d1cbe9d
Parents:
e28e6d1742e673c091f48a99b5d6d522e5d5bfa2
Message:
arithmetic in Z_p[x]/(f) for reducible f


git-svn-id: file:///usr/local/Singular/svn/trunk@14327 2c84dea3-7e68-4137-9b89-c4e89433aadc
File:
1 edited

Legend:

Unmodified
Added
Removed

  • factory/int_poly.cc

    re28e6d rec970e  
    256256
    257257InternalCF*
     258InternalPoly::tryInvert ( const CanonicalForm& M, bool& fail)
     259{
     260  if ( inExtension() && !getReduce ( var ) )
     261  {
     262    CanonicalForm b, inverse;
     263    CanonicalForm F ( this ->copyObject() );
     264    Variable a = M.mvar();
     265    Variable x = Variable(1);
     266    F= mod (F, M); //reduce mod M
     267    CanonicalForm g= extgcd (replacevar( F, a, x ), replacevar( M, a, x ), inverse, b );
     268    if(!g.isOne())
     269      fail = true;
     270    else
     271      inverse = replacevar( inverse, x, a ); // change back to alg var
     272    CanonicalForm test= mod (inverse*F, M);
     273    return inverse.getval();
     274  }
     275  else
     276    return CFFactory::basic( 0 );
     277}
     278
     279InternalCF*
    258280InternalPoly::addsame( InternalCF* aCoeff )
    259281{
    … …  
    398420
    399421InternalCF*
     422InternalPoly::tryMulsame( InternalCF* aCoeff, const CanonicalForm& M)
     423{
     424    if (is_imm(aCoeff))
     425       return mulcoeff(aCoeff);
     426    InternalPoly *aPoly = (InternalPoly*)aCoeff;
     427    termList resultFirst = 0, resultLast = 0;
     428    termList theCursor = firstTerm;
     429
     430    while ( theCursor )
     431    {
     432        resultFirst = mulAddTermList( resultFirst, aPoly->firstTerm,
     433                          theCursor->coeff, theCursor->exp, resultLast, false );
     434        theCursor = theCursor->next;
     435    }
     436    if ( inExtension() && !getReduce( var ) )
     437    {
     438        resultFirst= reduceTermList (resultFirst, ((InternalPoly*) M.getval())->firstTerm, resultLast);
     439        if ( resultFirst == 0 )
     440        {
     441            if ( getRefCount() <= 1 )
     442            {
     443                delete this;
     444                return CFFactory::basic(0);
     445            }
     446            else
     447            {
     448                decRefCount();
     449                return CFFactory::basic(0);
     450            }
     451        }
     452        else  if ( resultFirst->exp == 0 )
     453        {
     454            if ( getRefCount() <= 1 )
     455            {
     456                InternalCF * res = resultFirst->coeff.getval();
     457                delete resultFirst;
     458                delete this;
     459                return res;
     460            }
     461            else
     462            {
     463                decRefCount();
     464                InternalCF * res = resultFirst->coeff.getval();
     465                delete resultFirst;
     466                return res;
     467            }
     468        }
     469    }
     470    if ( getRefCount() <= 1 )
     471    {
     472        freeTermList( firstTerm );
     473        firstTerm = resultFirst;
     474        lastTerm = resultLast;
     475        return this;
     476    }
     477    else
     478    {
     479        decRefCount();
     480        return new InternalPoly( resultFirst, resultLast, var );
     481    }
     482}
     483
     484InternalCF*
    400485InternalPoly::dividesame( InternalCF* aCoeff )
    401486{
    … …  
    448533        delete dummy;
    449534        appendTermList( resultfirst, resultlast, newcoeff, newexp );
     535    }
     536    freeTermList( first );
     537    if ( singleObject )
     538    {
     539        if ( resultfirst && resultfirst->exp != 0 )
     540        {
     541            firstTerm = resultfirst;
     542            lastTerm = resultlast;
     543            return this;
     544        }
     545        else  if ( resultfirst )
     546        {
     547            InternalCF * res = resultfirst->coeff.getval();
     548            delete resultfirst;
     549            firstTerm = 0;
     550            delete this;
     551            return res;
     552        }
     553        else
     554        {
     555            // this should not happen (evtl use assertion)
     556            ASSERT( 0, "FATAL ERROR, PLEASE INFORM THE AUTHOR" );
     557            firstTerm = 0;
     558            delete this;
     559            return CFFactory::basic( 0 );
     560        }
     561    }
     562    else
     563    {
     564        if ( resultfirst && resultfirst->exp != 0 )
     565            return new InternalPoly( resultfirst, resultlast, var );
     566        else  if ( resultfirst )
     567        {
     568            InternalCF * res = resultfirst->coeff.getval();
     569            delete resultfirst;
     570            return res;
     571        }
     572        else
     573            return CFFactory::basic( 0 );
     574    }
     575}
     576
     577InternalCF*
     578InternalPoly::tryDivsame( InternalCF* aCoeff, const CanonicalForm& M, bool& fail )
     579{
     580    if ( inExtension() && !getReduce( var ) )
     581    {
     582        InternalCF * dummy = aCoeff->tryInvert(M, fail);
     583        if (fail)
     584          return CFFactory::basic( 0 );
     585        if (is_imm(dummy)) dummy=this->tryMulsame(dummy, M);
     586        else dummy = dummy->tryMulsame( this, M);
     587        if (fail)
     588        {
     589          if (getRefCount() <= 1)
     590            delete this;
     591          else
     592            decRefCount();
     593          return dummy;
     594        }
     595        if ( getRefCount() <= 1 )
     596        {
     597             delete this;
     598             return dummy;
     599        }
     600        else
     601        {
     602            decRefCount();
     603            return dummy;
     604        }
     605    }
     606    InternalPoly *aPoly = (InternalPoly*)aCoeff;
     607    termList dummy, first, last, resultfirst = 0, resultlast = 0;
     608    CanonicalForm coeff, newcoeff;
     609    int exp, newexp;
     610    bool singleObject;
     611
     612    if ( getRefCount() <= 1 )
     613    {
     614        first = firstTerm; last = lastTerm; singleObject = true;
     615    }
     616    else
     617    {
     618        first = copyTermList( firstTerm, last ); singleObject = false;
     619        decRefCount();
     620    }
     621    coeff = aPoly->firstTerm->coeff;
     622    exp = aPoly->firstTerm->exp;
     623    while (first && ( first->exp >= exp ) )
     624    {
     625        newcoeff= first->coeff.tryDiv (coeff, M, fail);
     626        if (fail)
     627        {
     628          freeTermList (first);
     629          return CFFactory::basic (0);
     630        }
     631        newcoeff= reduce (newcoeff, M);
     632        newexp = first->exp - exp;
     633        dummy = first;
     634        first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
     635        delete dummy;
     636        if (!newcoeff.isZero())
     637          appendTermList( resultfirst, resultlast, newcoeff, newexp );
    450638    }
    451639    freeTermList( first );
    … …  
    620808}
    621809
    622 
    623810bool
    624811InternalPoly::divremsamet( InternalCF* acoeff, InternalCF*& quot, InternalCF*& rem )
    … …  
    676863            else
    677864                rem = new InternalPoly( first, last, var );
     865        else
     866            rem = CFFactory::basic( 0 );
     867    }
     868    else
     869    {
     870        freeTermList( resultfirst );
     871        freeTermList( first );
     872    }
     873    return divideok;
     874}
     875
     876bool
     877InternalPoly::tryDivremsamet( InternalCF* acoeff, InternalCF*& quot, InternalCF*& rem, const CanonicalForm& M, bool& fail)
     878{
     879    if (inExtension() && !getReduce (var))
     880    {
     881       InternalCF * dummy = acoeff->tryInvert(M, fail);
     882       if (fail)
     883         return false;
     884       quot = dummy->tryMulsame( this, M);
     885       rem = CFFactory::basic( 0 );
     886       if (fail)
     887         return false;
     888       return true;
     889    }
     890    InternalPoly *aPoly = (InternalPoly*)acoeff;
     891    termList dummy, first, last, resultfirst = 0, resultlast = 0;
     892    CanonicalForm coeff, newcoeff, dummycoeff;
     893    int exp, newexp;
     894    bool divideok = true;
     895
     896    first = copyTermList( firstTerm, last );
     897
     898    coeff = aPoly->firstTerm->coeff;
     899    exp = aPoly->firstTerm->exp;
     900    while (first && ( first->exp >= exp ) && divideok )
     901    {
     902        divideok = tryDivremt( first->coeff, coeff, newcoeff, dummycoeff, M, fail );
     903        if (fail)
     904        {
     905          freeTermList (first);
     906          return false;
     907        }
     908        if ( divideok && dummycoeff.isZero() )
     909        {
     910            newexp = first->exp - exp;
     911            dummy = first;
     912            first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
     913            delete dummy;
     914            if (!newcoeff.isZero())
     915              appendTermList( resultfirst, resultlast, newcoeff, newexp );
     916        }
     917        else
     918            divideok = false;
     919    }
     920    if ( divideok )
     921    {
     922        if ( resultfirst )
     923            if ( resultfirst->exp == 0 )
     924            {
     925                quot = resultfirst->coeff.getval();
     926                delete resultfirst;
     927            }
     928            else
     929                quot = new InternalPoly( resultfirst, resultlast, var );
     930        else
     931            quot = CFFactory::basic( 0 );
     932        if ( first )
     933            if ( first->exp == 0 )
     934            {
     935                rem = first->coeff.getval();
     936                delete first;
     937            }
     938            else
     939            {
     940                if (first->coeff.isZero())
     941                {
     942                  rem= CFFactory::basic (0);
     943                  delete first;
     944                }
     945                else
     946                  rem = new InternalPoly( first, last, var );
     947            }
    678948        else
    679949            rem = CFFactory::basic( 0 );
    … …  
    10271297
    10281298InternalCF*
     1299InternalPoly::tryDividecoeff( InternalCF* cc, bool invert, const CanonicalForm& M, bool& fail )
     1300{
     1301    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
     1302    if ( inExtension() && !getReduce( var ) && invert )
     1303    {
     1304        InternalCF * dummy;
     1305        dummy = this->tryInvert(M, fail);
     1306        if (fail)
     1307        {
     1308          if (getRefCount() <= 1)
     1309            delete this;
     1310          else
     1311            decRefCount();
     1312          return dummy; //is equal to CFFactory::basic (0) in this case
     1313        }
     1314        if (is_imm(dummy))
     1315        {
     1316          if (is_imm(cc))
     1317          {
     1318            InternalInteger *d=new InternalInteger(imm2int(dummy)*imm2int(cc));
     1319            dummy=d;
     1320          }
     1321          else
     1322            dummy=cc->mulcoeff(dummy);
     1323        }
     1324        else dummy = dummy->mulcoeff( cc );
     1325        if ( getRefCount() <= 1 )
     1326        {
     1327            delete this;
     1328            return dummy;
     1329        }
     1330        else
     1331        {
     1332            decRefCount();
     1333            return dummy;
     1334        }
     1335    }
     1336    if ( invert )
     1337    {
     1338        if ( getRefCount() <= 1 )
     1339        {
     1340            delete this;
     1341            return CFFactory::basic( 0 );
     1342        }
     1343        else
     1344        {
     1345            decRefCount();
     1346            return CFFactory::basic( 0 );
     1347        }
     1348    }
     1349    if ( c.isOne() )
     1350        return this;
     1351    //one should never get here
     1352    else
     1353    {
     1354        if ( getRefCount() <= 1 )
     1355        {
     1356            firstTerm = divideTermList( firstTerm, c, lastTerm );
     1357            if ( firstTerm && firstTerm->exp != 0 )
     1358                return this;
     1359            else  if ( firstTerm )
     1360            {
     1361                InternalCF * res = firstTerm->coeff.getval();
     1362                delete this;
     1363                return res;
     1364            }
     1365            else
     1366            {
     1367                delete this;
     1368                return CFFactory::basic( 0 );
     1369            }
     1370        }
     1371        else
     1372        {
     1373            decRefCount();
     1374            termList last, first = copyTermList( firstTerm, last );
     1375            first = divideTermList( first, c, last );
     1376            if ( first && first->exp != 0 )
     1377                return new InternalPoly( first, last, var );
     1378            else  if ( first )
     1379            {
     1380                InternalCF * res = first->coeff.getval();
     1381                delete first;
     1382                return res;
     1383            }
     1384            else
     1385            {
     1386                delete first;
     1387                return CFFactory::basic( 0 );
     1388            }
     1389        }
     1390    }
     1391}
     1392
     1393
     1394InternalCF*
    10291395InternalPoly::divcoeff( InternalCF* cc, bool invert )
    10301396{
    … …  
    11031469
    11041470InternalCF*
     1471InternalPoly::tryDivcoeff( InternalCF* cc, bool invert, const CanonicalForm& M, bool& fail )
     1472{
     1473    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
     1474    if ( inExtension() && !getReduce( var ) && invert )
     1475    {
     1476        InternalCF * dummy;
     1477        dummy = this->tryInvert(M, fail);
     1478        if (fail)
     1479        {
     1480          if (getRefCount() <= 1)
     1481            delete this;
     1482          else
     1483            decRefCount();
     1484          return dummy;
     1485        }
     1486        dummy = dummy->mulcoeff( cc );
     1487        if ( getRefCount() <= 1 )
     1488        {
     1489            delete this;
     1490            return dummy;
     1491        }
     1492        else
     1493        {
     1494            decRefCount();
     1495            return dummy;
     1496        }
     1497    }
     1498    if ( invert )
     1499    {
     1500        if ( getRefCount() <= 1 )
     1501        {
     1502            delete this;
     1503            return CFFactory::basic( 0 );
     1504        }
     1505        else
     1506        {
     1507            decRefCount();
     1508            return CFFactory::basic( 0 );
     1509        }
     1510    }
     1511    if ( c.isOne() )
     1512        return this;
     1513    else
     1514    {
     1515        if ( getRefCount() <= 1 )
     1516        {
     1517            firstTerm = tryDivTermList( firstTerm, c, lastTerm, M, fail );
     1518            if (fail)
     1519            {
     1520              delete this;
     1521              return CFFactory::basic (0);
     1522            }
     1523            if ( firstTerm && firstTerm->exp != 0 )
     1524                return this;
     1525            else  if ( firstTerm )
     1526            {
     1527                InternalCF * res = firstTerm->coeff.getval();
     1528                delete this;
     1529                return res;
     1530            }
     1531            else
     1532            {
     1533                delete this;
     1534                return CFFactory::basic( 0 );
     1535            }
     1536        }
     1537        else
     1538        {
     1539            decRefCount();
     1540            termList last, first = copyTermList( firstTerm, last );
     1541            first = tryDivTermList( first, c, last, M, fail );
     1542            if (fail)
     1543            {
     1544              delete this;
     1545              return CFFactory::basic (0);
     1546            }
     1547            if (fail)
     1548            {
     1549              delete first;
     1550              return CFFactory::basic (0);
     1551            }
     1552            if ( first && first->exp != 0 )
     1553                return new InternalPoly( first, last, var );
     1554            else  if ( first )
     1555            {
     1556                InternalCF * res = first->coeff.getval();
     1557                delete first;
     1558                return res;
     1559            }
     1560            else
     1561            {
     1562                delete first;
     1563                return CFFactory::basic( 0 );
     1564            }
     1565        }
     1566    }
     1567}
     1568
     1569InternalCF*
    11051570InternalPoly::modulocoeff( InternalCF* cc, bool invert )
    11061571{
    … …  
    12491714    {
    12501715        divideok = divremt( cursor->coeff, c, cquot, crem );
     1716        divideok = divideok && crem.isZero();
     1717        if ( divideok )
     1718        {
     1719            if ( ! cquot.isZero() )
     1720            {
     1721                quotcursor->next = new term( 0, cquot, cursor->exp );
     1722                quotcursor = quotcursor->next;
     1723            }
     1724            cursor = cursor->next;
     1725        }
     1726    }
     1727    quotcursor->next = 0;
     1728    if ( divideok )
     1729    {
     1730        cursor = quotfirst; quotfirst = quotfirst->next; delete cursor;
     1731        if ( quotfirst )
     1732            if ( quotfirst->exp == 0 )
     1733            {
     1734                quot = quotfirst->coeff.getval();
     1735                delete quotfirst;
     1736            }
     1737            else
     1738                quot = new InternalPoly( quotfirst, quotcursor, var );
     1739        else
     1740            quot = CFFactory::basic( 0 );
     1741        rem = CFFactory::basic( 0 );
     1742    }
     1743    else
     1744    {
     1745        freeTermList( quotfirst );
     1746    }
     1747    return divideok;
     1748}
     1749
     1750bool
     1751InternalPoly::tryDivremcoefft( InternalCF* cc, InternalCF*& quot, InternalCF*& rem, bool invert, const CanonicalForm& M, bool& fail )
     1752{
     1753    if ( inExtension() && !getReduce( var ) )
     1754    {
     1755        quot = copyObject();
     1756        quot = quot->tryDividecoeff( cc, invert, M, fail );
     1757        if (fail)
     1758          return false;
     1759        rem = CFFactory::basic( 0 );
     1760        return true;
     1761    }
     1762    else  if ( invert )
     1763    {
     1764        if ( is_imm( cc ) )
     1765            rem = cc;
     1766        else
     1767            rem = cc->copyObject();
     1768        quot = CFFactory::basic( 0 );
     1769        return true;
     1770    }
     1771    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
     1772    ASSERT( ! c.isZero(), "divide by zero!" );
     1773    termList quotfirst, quotcursor;
     1774    termList cursor;
     1775    CanonicalForm cquot, crem;
     1776    bool divideok = true;
     1777
     1778    cursor = firstTerm;
     1779    quotcursor = quotfirst = new term;
     1780
     1781    while ( cursor && divideok )
     1782    {
     1783        divideok = tryDivremt( cursor->coeff, c, cquot, crem, M, fail );
     1784        if (fail)
     1785        {
     1786          freeTermList (quotfirst);
     1787          return false;
     1788        }
    12511789        divideok = divideok && crem.isZero();
    12521790        if ( divideok )
    … …  
    15292067
    15302068termList
     2069InternalPoly::tryDivTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm, const CanonicalForm& M, bool& fail )
     2070{
     2071    termList theCursor = firstTerm;
     2072    lastTerm = 0;
     2073    termList dummy;
     2074
     2075    while ( theCursor )
     2076    {
     2077        theCursor->coeff.tryDiv( coeff, M, fail );
     2078        if (fail)
     2079          return 0;
     2080        if ( theCursor->coeff.isZero() )
     2081        {
     2082            if ( theCursor == firstTerm )
     2083                firstTerm = theCursor->next;
     2084            else
     2085                lastTerm->next = theCursor->next;
     2086            dummy = theCursor;
     2087            theCursor = theCursor->next;
     2088            delete dummy;
     2089        }
     2090        else
     2091        {
     2092            lastTerm = theCursor;
     2093            theCursor = theCursor->next;
     2094        }
     2095    }
     2096    return firstTerm;
     2097}
     2098
     2099termList
    15312100InternalPoly::modTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
    15322101{
    … …  
    16742243    return first;
    16752244}
     2245
Note: See TracChangeset for help on using the changeset viewer.