Changeset 21b8f4 in git


Ignore:
Timestamp:
Jul 25, 2011, 4:08:17 PM (12 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'f875bbaccd0831e36aaed09ff6adeb3eb45aeb94')
Children:
3dd0640ba1b8ca0d5fc4aa74c81faaa7eb5129fc
Parents:
64a5014602570d17e143cbe6e31d19fd6a86cfc3
Message:
added new fdivides which also returns the quotient in case of divisibility
replaced old fdivides where possible


git-svn-id: file:///usr/local/Singular/svn/trunk@14344 2c84dea3-7e68-4137-9b89-c4e89433aadc
Location:
factory
Files:
8 edited

Legend:

Unmodified
Added
Removed

  • factory/cf_algorithm.cc

    r64a501 r21b8f4  
    386386//}}}
    387387
     388/// same as fdivides if true returns quotient quot of g by f otherwise quot == 0
     389bool
     390fdivides ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm& quot )
     391{
     392    quot= 0;
     393    // trivial cases
     394    if ( g.isZero() )
     395        return true;
     396    else if ( f.isZero() )
     397        return false;
     398
     399    if ( (f.inCoeffDomain() || g.inCoeffDomain())
     400         && ((getCharacteristic() == 0 && isOn( SW_RATIONAL ))
     401             || (getCharacteristic() > 0 && CFFactory::gettype() != PrimePowerDomain)) )
     402    {
     403        // if we are in a field all elements not equal to zero are units
     404        if ( f.inCoeffDomain() )
     405        {
     406            quot= g/f;
     407            return true;
     408        }
     409        else
     410            // g.inCoeffDomain()
     411            return false;
     412    }
     413
     414    // we may assume now that both levels either equal LEVELBASE
     415    // or are greater zero
     416    int fLevel = f.level();
     417    int gLevel = g.level();
     418    if ( (gLevel > 0) && (fLevel == gLevel) )
     419        // f and g are polynomials in the same main variable
     420        if ( degree( f ) <= degree( g )
     421             && fdivides( f.tailcoeff(), g.tailcoeff() )
     422             && fdivides( f.LC(), g.LC() ) )
     423        {
     424            CanonicalForm q, r;
     425            if (divremt( g, f, q, r ) && r.isZero())
     426            {
     427              quot= q;
     428              return true;
     429            }
     430            else
     431              return false;
     432        }
     433        else
     434            return false;
     435    else if ( gLevel < fLevel )
     436        // g is a coefficient w.r.t. f
     437        return false;
     438    else
     439    {
     440        // either f is a coefficient w.r.t. polynomial g or both
     441        // f and g are from a base domain (should be Z or Z/p^n,
     442        // then)
     443        CanonicalForm q, r;
     444        if (divremt( g, f, q, r ) && r.isZero())
     445        {
     446          quot= q;
     447          return true;
     448        }
     449        else
     450          return false;
     451    }
     452}
     453
    388454/// same as fdivides but handles zero divisors in Z_p[t]/(f)[x1,...,xn] for reducible f
    389455bool

  • factory/cf_algorithm.h

    r64a501 r21b8f4  
    4141
    4242bool fdivides ( const CanonicalForm & f, const CanonicalForm & g );
     43
     44bool fdivides ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm& quot );
    4345
    4446bool tryFdivides ( const CanonicalForm & f, const CanonicalForm & g, const CanonicalForm& M, bool& fail );

  • factory/facAlgExt.cc

    r64a501 r21b8f4  
    156156  bool save_rat=!isOn (SW_RATIONAL);
    157157  On (SW_RATIONAL);
    158   CanonicalForm buf= F/Lc (F);
     158  CanonicalForm quot, buf= F/Lc (F);
    159159  CFFList factors;
    160160  int multi;
    … …  
    163163    multi= 0;
    164164    i.getItem() /= Lc (i.getItem()); //make factors monic
    165     while (fdivides (i.getItem(), buf))
     165    while (fdivides (i.getItem(), buf, quot))
    166166    {
    167       buf /= i.getItem();
     167      buf= quot;
    168168      multi++;
    169169    }

  • factory/facFqBivar.cc

    r64a501 r21b8f4  
    274274
    275275  CFList result;
    276   CanonicalForm buf, buf2;
     276  CanonicalForm buf, buf2, quot;
    277277
    278278  buf= F;
    … …  
    334334          S.removeFirst();
    335335          g /= content (g, Variable (1));
    336           if (fdivides (g, buf))
     336          if (fdivides (g, buf, quot))
    337337          {
    338338            buf2= g (y - eval, y);
    … …  
    343343              if (degree (buf2, alpha) < degMipoBeta)
    344344              {
    345                 buf /= g;
     345                buf= quot;
    346346                LCBuf= LC (buf, Variable (1));
    347347                recombination= true;
    … …  
    354354              if (!isInExtension (buf2, gamma, k, delta, source, dest))
    355355              {
    356                 buf /= g;
     356                buf= quot;
    357357                LCBuf= LC (buf, Variable (1));
    358358                recombination= true;
    … …  
    461461  CFList result;
    462462  CanonicalForm LCBuf= LC (F, Variable (1));
    463   CanonicalForm g, buf= F;
     463  CanonicalForm g, quot, buf= F;
    464464  int * v= new int [T.length()];
    465465  for (int i= 0; i < T.length(); i++)
    … …  
    512512          S.removeFirst();
    513513          g /= content (g, Variable (1));
    514           if (fdivides (g, buf))
     514
     515          if (fdivides (g, buf, quot))
    515516          {
    516517            recombination= true;
    517518            result.append (g);
    518             buf /= g;
     519            buf= quot;
    519520            LCBuf= LC (buf, Variable(1));
    520521            T= Difference (T, S);
    … …  
    628629  CanonicalForm buf= F;
    629630  CanonicalForm LCBuf= LC (buf, Variable (1));
    630   CanonicalForm g;
     631  CanonicalForm g, quot;
    631632  CanonicalForm M= power (F.mvar(), deg);
    632633  adaptedLiftBound= 0;
    … …  
    645646        g= mulMod2 (i.getItem(), LCBuf, M);
    646647        g /= content (g, Variable (1));
    647         if (fdivides (g, buf))
     648        if (fdivides (g, buf, quot))
    648649        {
    649650          result.append (g);
    650           buf /= g;
     651          buf= quot;
    651652          d -= degree (g) + degree (LC (g, Variable (1)));
    652653          LCBuf= LC (buf, Variable (1));
    … …  
    703704  if (!k && beta.level() != 1)
    704705    degMipoBeta= degree (getMipo (beta));
     706  CanonicalForm quot;
    705707  for (CFListIterator i= factors; i.hasItem(); i++)
    706708  {
    … …  
    716718        g= mulMod2 (i.getItem(), LCBuf, M);
    717719        g /= content (g, Variable (1));
    718         if (fdivides (g, buf))
     720        if (fdivides (g, buf, quot))
    719721        {
    720722          buf2= g (y - eval, y);
    … …  
    726728            {
    727729              appendTestMapDown (result, buf2, info, source, dest);
    728               buf /= g;
     730              buf= quot;
    729731              d -= degree (g) + degree (LC (g, Variable (1)));
    730732              LCBuf= LC (buf, Variable (1));
    … …  
    737739            {
    738740              appendTestMapDown (result, buf2, info, source, dest);
    739               buf /= g;
     741              buf= quot;
    740742              d -= degree (g) + degree (LC (g, Variable (1)));
    741743              LCBuf= LC (buf, Variable (1));
    … …  
    959961  Variable x= Variable (1);
    960962  CanonicalForm yToL= power (y, liftBound);
     963  CanonicalForm quot;
    961964  for (long i= 1; i <= N.NumCols(); i++)
    962965  {
    … …  
    987990    buf= mod (buf, yToL);
    988991    buf /= content (buf, x);
    989     if (fdivides (buf, F))
     992    if (fdivides (buf, F, quot))
    990993    {
    991994      factorsFoundIndex[i - 1]= 1;
    992995      factorsFound++;
    993       F /= buf;
     996      F= quot;
    994997      F /= Lc (F);
    995998      reconstructedFactors.append (buf);
    … …  
    10131016  Variable y= Variable (2);
    10141017  Variable x= Variable (1);
     1018  CanonicalForm quot;
    10151019  CanonicalForm yToL= power (y, liftBound);
    10161020  for (long i= 1; i <= N.NumCols(); i++)
    … …  
    10421046    buf= mod (buf, yToL);
    10431047    buf /= content (buf, x);
    1044     if (fdivides (buf, F))
     1048    if (fdivides (buf, F, quot))
    10451049    {
    10461050      factorsFoundIndex[i - 1]= 1;
    10471051      factorsFound++;
    1048       F /= buf;
     1052      F= quot;
    10491053      F /= Lc (F);
    10501054      reconstructedFactors.append (buf);
    … …  
    10691073  CanonicalForm F= G;
    10701074  CanonicalForm yToL= power (y, precision);
     1075  CanonicalForm quot;
    10711076  CFList result;
    10721077  CFList bufFactors= factors;
    … …  
    10901095    buf= mod (buf, yToL);
    10911096    buf /= content (buf, x);
    1092     if (fdivides (buf, F))
    1093     {
    1094       F /= buf;
     1097    if (fdivides (buf, F, quot))
     1098    {
     1099      F= quot;
    10951100      F /= Lc (F);
    10961101      result.append (buf);
    … …  
    11181123  CanonicalForm F= G;
    11191124  CanonicalForm yToL= power (y, precision);
     1125  CanonicalForm quot;
    11201126  CFList result;
    11211127  CFList bufFactors= factors;
    … …  
    11401146    buf= mod (buf, yToL);
    11411147    buf /= content (buf, x);
    1142     if (fdivides (buf, F))
    1143     {
    1144       F /= buf;
     1148    if (fdivides (buf, F, quot))
     1149    {
     1150      F= quot;
    11451151      F /= Lc (F);
    11461152      result.append (buf2);
    … …  
    11771183  CFList bufFactors= factors;
    11781184  CFList factorsConsidered;
    1179   CanonicalForm buf2;
     1185  CanonicalForm buf2, quot;
    11801186  for (long i= 1; i <= N.NumCols(); i++)
    11811187  {
    … …  
    12011207      if (degree (buf2, alpha) < 1)
    12021208      {
    1203         if (fdivides (buf, F))
    1204         {
    1205           F /= buf;
     1209        if (fdivides (buf, F, quot))
     1210        {
     1211          F= quot;
    12061212          F /= Lc (F);
    12071213          result.append (buf2);
    … …  
    12161222      if (!isInExtension (buf2, gamma, k, delta, source, dest))
    12171223      {
    1218         if (fdivides (buf, F))
    1219         {
    1220           F /= buf;
     1224        if (fdivides (buf, F, quot))
     1225        {
     1226          F= quot;
    12211227          F /= Lc (F);
    12221228          result.append (buf2);
    … …  
    12451251  CanonicalForm F= G;
    12461252  CanonicalForm yToL= power (y, precision);
     1253  CanonicalForm quot;
    12471254  CFList result;
    12481255  CFList bufFactors= factors;
    … …  
    12661273    buf= mod (buf, yToL);
    12671274    buf /= content (buf, x);
    1268     if (fdivides (buf, F))
    1269     {
    1270       F /= buf;
     1275    if (fdivides (buf, F, quot))
     1276    {
     1277      F= quot;
    12711278      F /= Lc (F);
    12721279      result.append (buf);
    … …  
    13001307  CanonicalForm delta= info.getDelta();
    13011308  CanonicalForm yToL= power (y, liftBound);
     1309  CanonicalForm quot;
    13021310  CFList source, dest;
    13031311  for (long i= 1; i <= N.NumCols(); i++)
    … …  
    13351343      if (degree (buf2, alpha) < 1)
    13361344      {
    1337         if (fdivides (buf, F))
     1345        if (fdivides (buf, F, quot))
    13381346        {
    13391347          factorsFoundIndex[i - 1]= 1;
    13401348          factorsFound++;
    1341           F /= buf;
     1349          F= quot;
    13421350          F /= Lc (F);
    13431351          buf2= mapDown (buf2, info, source, dest);
    … …  
    13511359      if (!isInExtension (buf2, gamma, k, delta, source, dest))
    13521360      {
    1353         if (fdivides (buf, F))
     1361        if (fdivides (buf, F, quot))
    13541362        {
    13551363          factorsFoundIndex[i - 1]= 1;
    13561364          factorsFound++;
    1357           F /= buf;
     1365          F= quot;
    13581366          F /= Lc (F);
    13591367          buf2= mapDown (buf2, info, source, dest);

  • factory/facFqBivarUtil.cc

    r64a501 r21b8f4  
    415415  CFFList result;
    416416  int multi= 0;
     417  CanonicalForm quot;
    417418  for (CFListIterator i= factors; i.hasItem(); i++)
    418419  {
    419     while (fdivides (i.getItem(), F))
     420    while (fdivides (i.getItem(), F, quot))
    420421    {
    421422      multi++;
    422       F /= i.getItem();
     423      F= quot;
    423424    }
    424425    if (multi > 0)

  • factory/facFqFactorize.cc

    r64a501 r21b8f4  
    214214
    215215  CanonicalForm g, LCBuf= LC (buf, Variable (1));
    216   CanonicalForm buf2;
     216  CanonicalForm buf2, quot;
    217217  int * v= new int [T.length()];
    218218  for (int i= 0; i < T.length(); i++)
    … …  
    255255      S.removeFirst();
    256256      g /= myContent (g);
    257       if (fdivides (g, buf))
     257      if (fdivides (g, buf, quot))
    258258      {
    259259        buf2= reverseShift (g, evaluation);
    … …  
    264264          {
    265265            appendTestMapDown (result, buf2, info, source, dest);
    266             buf /= g;
     266            buf= quot;
    267267            LCBuf= LC (buf, Variable (1));
    268268            recombination= true;
    … …  
    348348  Variable y= F.level() - 1;
    349349  bool recombination= false;
    350   CanonicalForm h;
     350  CanonicalForm h, quot;
    351351  while (T.length() >= 2*s)
    352352  {
    … …  
    372372      S.removeFirst();
    373373      g /= myContent (g);
    374       if (fdivides (g, buf))
     374      if (fdivides (g, buf, quot))
    375375      {
    376376        recombination= true;
    377377        result.append (g);
    378         buf /= g;
     378        buf= quot;
    379379        LCBuf= LC (buf, Variable(1));
    380380        T= Difference (T, S);
    … …  
    416416  Variable y= F.mvar();
    417417  CanonicalForm LCBuf= LC (buf, Variable (1));
    418   CanonicalForm g;
     418  CanonicalForm g, quot;
    419419  CFList M= MOD;
    420420  M.append (power (y, deg));
    … …  
    426426    g= mulMod (i.getItem(), LCBuf, M);
    427427    g /= myContent (g);
    428     if (fdivides (g, buf))
     428    if (fdivides (g, buf, quot))
    429429    {
    430430      nBuf= degree (g, y) + degree (LC (g, 1), y);
    431431      d -= nBuf;
    432432      e= tmax (e, nBuf);
    433       buf /= g;
     433      buf= quot;
    434434      LCBuf= LC (buf, Variable (1));
    435435    }
    … …  
    485485  Variable y= F.mvar();
    486486  CanonicalForm LCBuf= LC (buf, Variable (1));
    487   CanonicalForm g, gg;
     487  CanonicalForm g, gg, quot;
    488488  CFList M= MOD;
    489489  M.append (power (y, deg));
    … …  
    501501    g= mulMod (i.getItem(), LCBuf, M);
    502502    g /= myContent (g);
    503     if (fdivides (g, buf))
     503    if (fdivides (g, buf, quot))
    504504    {
    505505      gg= reverseShift (g, eval);
    … …  
    509509        if (degree (gg, alpha) < degMipoBeta)
    510510        {
    511           buf /= g;
     511          buf= quot;
    512512          nBuf= degree (g, y) + degree (LC (g, Variable (1)), y);
    513513          d -= nBuf;
    … …  
    520520        if (!isInExtension (gg, gamma, k, delta, source, dest))
    521521        {
    522           buf /= g;
     522          buf= quot;
    523523          nBuf= degree (g, y) + degree (LC (g, Variable (1)), y);
    524524          d -= nBuf;
    … …  
    576576  Variable y= F.mvar();
    577577  CanonicalForm LCBuf= LC (buf, Variable (1));
    578   CanonicalForm g;
     578  CanonicalForm g, quot;
    579579  CFList M= MOD;
    580580  M.append (power (y, deg));
    … …  
    587587    g= mulMod (i.getItem(), LCBuf, M);
    588588    g /= myContent (g);
    589     if (fdivides (g, buf))
     589    if (fdivides (g, buf, quot))
    590590    {
    591591      result.append (g);
    … …  
    593593      d -= nBuf;
    594594      e= tmax (e, nBuf);
    595       buf /= g;
     595      buf= quot;
    596596      LCBuf= LC (buf, Variable (1));
    597597      T= Difference (T, CFList (i.getItem()));
    … …  
    631631  Variable y= F.mvar();
    632632  CanonicalForm LCBuf= LC (buf, Variable (1));
    633   CanonicalForm g, gg;
     633  CanonicalForm g, gg, quot;
    634634  CFList M= MOD;
    635635  M.append (power (y, deg));
    … …  
    648648    g= mulMod (i.getItem(), LCBuf, M);
    649649    g /= myContent (g);
    650     if (fdivides (g, buf))
     650    if (fdivides (g, buf, quot))
    651651    {
    652652      gg= reverseShift (g, eval);
    … …  
    657657        {
    658658          appendTestMapDown (result, gg, info, source, dest);
    659           buf /= g;
     659          buf= quot;
    660660          nBuf= degree (g, y) + degree (LC (g, Variable (1)), y);
    661661          d -= nBuf;
    … …  
    670670        {
    671671          appendTestMapDown (result, gg, info, source, dest);
    672           buf /= g;
     672          buf= quot;
    673673          nBuf= degree (g, y) + degree (LC (g, Variable (1)), y);
    674674          d -= nBuf;
    … …  
    11661166                            const CFList& M)
    11671167{
    1168   CanonicalForm buf= F;
     1168  CanonicalForm quot, buf= F;
    11691169  CanonicalForm LCBuf= LC (buf, 1);
    11701170
    … …  
    11761176    tmp= mulMod (tmp, LCBuf, M);
    11771177    tmp= tmp/content (tmp, 1);
    1178     if (fdivides (tmp, buf))
    1179     {
    1180       buf /= tmp;
     1178    if (fdivides (tmp, buf, quot))
     1179    {
     1180      buf= quot;
    11811181      result.append (tmp);
    11821182      LCBuf= LC (buf, 1);
    … …  
    19351935  int s= 1;
    19361936  CFList result;
    1937   CanonicalForm buf= F;
     1937  CanonicalForm quot, buf= F;
    19381938
    19391939  CanonicalForm g;
    … …  
    19761976      g= prod (S);
    19771977      g /= myContent (g);
    1978       if (fdivides (g, buf))
     1978      if (fdivides (g, buf, quot))
    19791979      {
    19801980        buf2= reverseShift (g, evaluation);
    … …  
    19851985          {
    19861986            appendTestMapDown (result, buf2, info, source, dest);
    1987             buf /= g;
     1987            buf= quot;
    19881988            recombination= true;
    19891989            trueFactor= true;
    … …  
    19951995          {
    19961996            appendTestMapDown (result, buf2, info, source, dest);
    1997             buf /= g;
     1997            buf= quot;
    19981998            recombination= true;
    19991999            trueFactor= true;

  • factory/facHensel.cc

    r64a501 r21b8f4  
    17741774      bufFactors [k]= i.getItem();
    17751775    }
    1776     CanonicalForm b;
     1776    CanonicalForm b, quot;
    17771777    for (k= 0; k < factors.length(); k++) //TODO compute b's faster
    17781778    {
    17791779      b= 1;
    1780       if (fdivides (bufFactors[k], F))
    1781         b= F/bufFactors[k];
     1780      if (fdivides (bufFactors[k], F, quot))
     1781        b= quot;
    17821782      else
    17831783      {
    … …  
    18631863  for (CFListIterator i= factors; i.hasItem(); i++, k++)
    18641864    bufFactors [k]= i.getItem();
    1865   CanonicalForm b;
     1865  CanonicalForm b, quot;
    18661866  CFList buf= M;
    18671867  buf.removeLast();
    … …  
    18701870  {
    18711871    b= 1;
    1872     if (fdivides (bufFactors[k], F))
    1873       b= F/bufFactors[k];
     1872    if (fdivides (bufFactors[k], F, quot))
     1873      b= quot;
    18741874    else
    18751875    {
    … …  
    29092909
    29102910  CFList products;
     2911  CanonicalForm quot;
    29112912  for (int i= 0; i < bufFactors.size(); i++)
    29122913  {
    29132914    if (degree (bufFactors[i], y) > 0)
    29142915    {
    2915       if (!fdivides (bufFactors[i] [0], F.getFirst()))
     2916      if (!fdivides (bufFactors[i] [0], F.getFirst(), quot))
    29162917      {
    29172918        bad= true;
    29182919        return CFList();
    29192920      }
    2920       products.append (F.getFirst()/bufFactors[i] [0]);
    2921     }
    2922     else
    2923     {
    2924       if (!fdivides (bufFactors[i], F.getFirst()))
     2921      products.append (quot);
     2922    }
     2923    else
     2924    {
     2925      if (!fdivides (bufFactors[i], F.getFirst(), quot))
    29252926      {
    29262927        bad= true;
    29272928        return CFList();
    29282929      }
    2929       products.append (F.getFirst()/bufFactors[i]);
     2930      products.append (quot);
    29302931    }
    29312932  }
    … …  
    31363137
    31373138  CFList products;
    3138   CanonicalForm bufF= F.getFirst();
     3139  CanonicalForm quot, bufF= F.getFirst();
    31393140
    31403141  for (int i= 0; i < bufFactors.size(); i++)
    … …  
    31423143    if (degree (bufFactors[i], y) > 0)
    31433144    {
    3144       if (!fdivides (bufFactors[i] [0], bufF))
     3145      if (!fdivides (bufFactors[i] [0], bufF, quot))
    31453146      {
    31463147        noOneToOne= true;
    31473148        return factors;
    31483149      }
    3149       products.append (bufF/bufFactors[i] [0]);
    3150     }
    3151     else
    3152     {
    3153       if (!fdivides (bufFactors[i], bufF))
     3150      products.append (quot);
     3151    }
     3152    else
     3153    {
     3154      if (!fdivides (bufFactors[i], bufF, quot))
    31543155      {
    31553156        noOneToOne= true;
    31563157        return factors;
    31573158      }
    3158       products.append (bufF/bufFactors[i]);
     3159      products.append (quot);
    31593160    }
    31603161  }

  • factory/fac_distrib.cc

    r64a501 r21b8f4  
    6666    DEBINCLEVEL( cerr, "distributeLeadingCoeffs" );
    6767    CanonicalForm ut, gt, d, ft;
    68     CanonicalForm dd;
     68    CanonicalForm dd, quot;
    6969    CFFListIterator I;
    7070    int m, j, i;
    … …  
    8585            ut = lc( G[j] );
    8686            DEBOUTLN( cerr, "checking with " << ut );
    87             while ( m > 0 && fdivides( D[i], ut ) )
     87            while ( m > 0 && fdivides( D[i], ut, quot ) )
    8888            {
    8989                DEBOUTLN( cerr, "match found" );
    90                 m--; ut /= D[i];
     90                m--; ut= quot;
    9191                lcG[j] *= ft;
    9292            }
    … …  
    136136        return;
    137137    }
    138     CanonicalForm h, f = F;
     138    CanonicalForm h, quot, f = F;
    139139    CFListIterator i, j;
    140140    for ( i = L; i.hasItem() && ! f.isOne(); )
    … …  
    146146            continue;
    147147        }
    148         while ( fdivides( h, f ) )
    149             f /= h;
     148        while ( fdivides( h, f, quot ) )
     149            f= quot;
    150150        CFList D( h );
    151151        gfbAdjoin( i.getItem() / h, D );
Note: See TracChangeset for help on using the changeset viewer.