Changeset 8a30b1 in git


Ignore:
Timestamp:
Jul 19, 2012, 12:14:06 PM (10 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '96ce329119711a2b80858c8365abd29f8460bbfa')
Children:
4fee0ed1233fdc5967b5508da747cc77fe30de63
Parents:
e0af3ef0dd8793dabc30eac5d848f0b020acd362
git-author:
Martin Lee <martinlee84@web.de>2012-07-19 12:14:06+02:00
git-committer:
Martin Lee <martinlee84@web.de>2012-09-04 17:25:37+02:00
Message:
fix: bug in precomputation of leading coefficient
Location:
factory
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • factory/facFactorize.cc

    re0af3ef r8a30b1  
    268268
    269269  CFMap N, M;
    270   CFArray dummy= CFArray (1);
     270  CFArray dummy= CFArray (2);
    271271  dummy [0]= LCF;
     272  dummy [1]= Variable (2);
    272273  compress (dummy, M, N);
    273274  CanonicalForm F= M (LCF);
     
    321322  CFList evalSqrfPartF, bufFactors;
    322323  CFArray evalPoint= CFArray (evaluation.length() - 1);
     324  CFArray buf= CFArray (evaluation.length());
     325  CFArray swap= CFArray (evaluation.length());
    323326  CFListIterator iter= evaluation;
    324   for (int i= evaluation.length() - 2; i > -1; i--, iter++)
    325     evalPoint[i]= iter.getItem();
     327  CanonicalForm vars=getVars (LCF);
     328  for (int i= evaluation.length() +1; i > 1; i--, iter++)
     329  {
     330    buf[i-2]=iter.getItem();
     331    if (degree (vars, i) > 0)
     332      swap[M(Variable (i)).level()-1]=buf[i-2];
     333  }
     334  buf= swap;
     335  for (int i= 0; i < evaluation.length() - 1; i++)
     336    evalPoint[i]= buf[i+1];
     337
    326338  //TODO sqrfPartF einmal berechnen nicht stÀndig
    327339  int pass= testFactors (F, factors, sqrfPartF,
     
    335347  {
    336348    int lev= 0;
     349    CanonicalForm bufF;
     350    CFList bufBufFactors;
    337351    for (int i= 0; i < length; i++)
    338352    {
    339       CanonicalForm bufF, swap;
    340       CFList bufBufFactors;
    341       CFArray buf;
    342353      if (!differentSecondVarLCs [i].isEmpty())
    343354      {
     
    363374        bufBufFactors= bufFactors;
    364375        evalPoint= CFArray (evaluation.length() - 1);
    365         buf= CFArray (evaluation.length());
    366         iter= evaluation;
    367         int k= evaluation.length() - 1;
    368         for (; iter.hasItem(); iter++, k--)
    369           buf[k]= iter.getItem();
    370         swap= buf[z.level() - 1];
    371         buf[z.level() - 1]= buf[0];
    372         buf[0]= 0;
    373         int l= 0;
    374         for (k= 0; k < evaluation.length(); k++)
     376        for (int k= 0; k < evaluation.length()-1; k++)
    375377        {
    376           if (buf[k].isZero())
    377             continue;
    378           evalPoint[l]= buf[k];
    379           l++;
     378          if (k+1 != lev)
     379            evalPoint[k]= buf[k+1];
     380          else
     381            evalPoint[k]= buf[0];
    380382        }
    381383        pass= testFactors (bufF, bufBufFactors, sqrfPartF, bufFactors,
     
    421423  bufFactors= factors;
    422424  CFList evaluation2;
    423   if (y == x)
    424     evaluation2= evaluation;
    425   else
    426   {
    427     CanonicalForm tmp;
    428     evaluation2= evaluation;
    429     int i= evaluation.length() + 1;
    430     for (CFListIterator iter= evaluation2; iter.hasItem(); iter++, i--)
    431     {
    432       if (i == y.level())
    433       {
    434         tmp= iter.getItem();
    435         iter.getItem()= evaluation2.getLast();
    436         evaluation2.removeLast();
    437         evaluation2.append (tmp);
    438         break;
    439       }
    440     }
    441   }
     425  for (int i= 0; i < F.level()-1; i++)
     426    evaluation2.insert (evalPoint[i]);
    442427
    443428  CFList interMedResult;
    444429  CanonicalForm oldSqrfPartF= sqrfPartF;
    445   sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2, 1);
     430  sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2);
    446431  if (factors.length() > 1)
    447432  {
     
    451436      leadingCoeffs.append (LC1);
    452437
    453     CFList LC1eval= evaluateAtEval (LC1, evaluation2, 1);
     438    CFList LC1eval= evaluateAtEval (LC1, evaluation2,2);
    454439    CFList oldFactors= factors;
    455440    for (CFListIterator i= oldFactors; i.hasItem(); i++)
     
    460445    if (size (oldSqrfPartFPowLC)/getNumVars (oldSqrfPartFPowLC) < 500 &&
    461446        LucksWangSparseHeuristic (oldSqrfPartFPowLC,
    462                                   oldFactors, 1, leadingCoeffs, factors))
     447                                  oldFactors, 2, leadingCoeffs, factors))
    463448    {
    464449      interMedResult= recoverFactors (oldSqrfPartF, factors);
     
    475460
    476461      for (CFListIterator i= factors; i.hasItem(); i++)
    477       {
    478         i.getItem()= i.getItem() (x + evaluation2.getLast(), x);
    479462        i.getItem() *= LC1 (0,2)/Lc (i.getItem());
    480       }
    481463      factors.insert (1);
    482464
     
    522504      }
    523505      for (CFListIterator iter= factors; iter.hasItem(); iter++)
    524         iter.getItem()= reverseShift (iter.getItem(), evaluation2, 1);
     506        iter.getItem()= reverseShift (iter.getItem(), evaluation2);
    525507
    526508      interMedResult=
    527       recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2,1),
     509      recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2),
    528510                      factors);
    529511    }
  • factory/facFqFactorize.cc

    re0af3ef r8a30b1  
    12201220      {
    12211221        CFListIterator iter1= result;
    1222         for (CFListIterator iter2= differentSecondVarFactors[i]; iter2.hasItem();
     1222        for (CFListIterator iter2= differentSecondVarFactors[i];iter2.hasItem();
    12231223             iter2++, iter1++)
    12241224        {
     
    12331233
    12341234  Variable v;
    1235   CFListIterator iter1;
     1235  CFListIterator iter1, iter2;
    12361236  CanonicalForm tmp, g;
     1237  CFList multiplier;
    12371238  for (int i= 0; i < length; i++)
    12381239  {
     
    12431244
    12441245    v= Variable (i + 3);
    1245     for (CFListIterator iter2= differentSecondVarFactors[i]; iter2.hasItem();
     1246    tmp= 1;
     1247    for (iter2= differentSecondVarFactors[i]; iter2.hasItem();
    12461248         iter2++, iter1++)
    12471249    {
    12481250      if (degree (iter2.getItem(),v) == degree (iter1.getItem(),v))
     1251      {
     1252        multiplier.append (1);
    12491253        continue;
    1250       tmp= iter1.getItem();
    1251       for (int j= tmp.level(); j > 1; j--)
    1252       {
    1253         if (j == i + 3)
    1254           continue;
    1255         tmp= tmp (0, j);
    12561254      }
    12571255      g= gcd (iter2.getItem(), content);
    1258       if (degree (g) > 0)
    1259       {
    1260         if (!tmp.isZero())
    1261           iter2.getItem() /= tmp;
    1262         content /= g;
    1263         iter1.getItem() *= g;
    1264       }
    1265     }
     1256      if (!g.inCoeffDomain())
     1257      {
     1258        tmp *= g;
     1259        multiplier.append (g);
     1260      }
     1261      else
     1262        multiplier.append (1);
     1263    }
     1264    if (!tmp.isOne() && fdivides (tmp, content))
     1265    {
     1266      iter1= l;
     1267      iter1++;
     1268      content /= tmp;
     1269      for (iter2= multiplier; iter2.hasItem(); iter1++, iter2++)
     1270        iter1.getItem() *= iter2.getItem();
     1271    }
     1272    multiplier= CFList();
    12661273  }
    12671274
     
    14331440
    14341441  CFMap N, M;
    1435   CFArray dummy= CFArray (1);
     1442  CFArray dummy= CFArray (2);
    14361443  dummy [0]= LCF;
     1444  dummy [1]= Variable (2);
    14371445  compress (dummy, M, N);
    14381446  CanonicalForm F= M (LCF);
     
    14861494  CFList evalSqrfPartF, bufFactors;
    14871495  CFArray evalPoint= CFArray (evaluation.length() - 1);
     1496  CFArray buf= CFArray (evaluation.length());
     1497  CFArray swap= CFArray (evaluation.length());
    14881498  CFListIterator iter= evaluation;
    1489   for (int i= evaluation.length() - 2; i > -1; i--, iter++)
    1490     evalPoint[i]= iter.getItem();
     1499  CanonicalForm vars=getVars (LCF);
     1500  for (int i= evaluation.length() +1; i > 1; i--, iter++)
     1501  {
     1502    buf[i-2]=iter.getItem();
     1503    if (degree (vars, i) > 0)
     1504      swap[M(Variable (i)).level()-1]=buf[i-2];
     1505  }
     1506  buf= swap;
     1507  for (int i= 0; i < evaluation.length() - 1; i++)
     1508    evalPoint[i]= buf[i+1];
    14911509
    14921510  int pass= testFactors (F, factors, alpha, sqrfPartF,
     
    15011519    // LCF is non-constant here
    15021520    CFList bufBufFactors;
    1503     CanonicalForm bufF, swap;
    1504     CFArray buf;
     1521    CanonicalForm bufF;
    15051522    for (int i= 0; i < lSecondVarLCs; i++)
    15061523    {
     
    15281545        bufBufFactors= bufFactors;
    15291546        evalPoint= CFArray (evaluation.length() - 1);
    1530         buf= CFArray (evaluation.length());
    1531         iter= evaluation;
    1532         int k= evaluation.length() - 1;
    1533         for (; iter.hasItem(); iter++, k--)
    1534           buf[k]= iter.getItem();
    1535         swap= buf[z.level() - 1];
    1536         buf[z.level() - 1]= buf[0];
    1537         buf[0]= 0;
    1538         int l= 0;
    1539         for (k= 0; k < evaluation.length(); k++)
    1540         {
    1541           if (buf[k].isZero())
    1542             continue;
    1543           evalPoint[l]= buf[k];
    1544           l++;
     1547        for (int k= 0; k < evaluation.length()-1; k++)
     1548        {
     1549          if (k+1 != lev)
     1550            evalPoint[k]= buf[k+1];
     1551          else
     1552            evalPoint[k]= buf[0];
    15451553        }
    15461554        pass= testFactors (bufF, bufBufFactors, alpha, sqrfPartF, bufFactors,
     
    15851593  bufFactors= factors;
    15861594  CFList evaluation2;
    1587   if (y == x)
    1588     evaluation2= evaluation;
    1589   else
    1590   {
    1591     CanonicalForm tmp;
    1592     evaluation2= evaluation;
    1593     int i= evaluation.length() + 1;
    1594     for (CFListIterator iter= evaluation2; iter.hasItem(); iter++, i--)
    1595     {
    1596       if (i == y.level())
    1597       {
    1598         tmp= iter.getItem();
    1599         iter.getItem()= evaluation2.getLast();
    1600         evaluation2.removeLast();
    1601         evaluation2.append (tmp);
    1602         break;
    1603       }
    1604     }
    1605   }
     1595  for (int i= 0; i < F.level()-1; i++)
     1596    evaluation2.insert (evalPoint[i]);
    16061597
    16071598  CFList interMedResult;
    16081599  CanonicalForm oldSqrfPartF= sqrfPartF;
    1609   sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2, 1);
     1600  sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2);
    16101601  if (factors.length() > 1)
    16111602  {
     
    16151606      leadingCoeffs.append (LC1);
    16161607
    1617     CFList LC1eval= evaluateAtEval (LC1, evaluation2, 1);
     1608    CFList LC1eval= evaluateAtEval (LC1, evaluation2, 2);
    16181609    CFList oldFactors= factors;
    16191610    for (CFListIterator i= oldFactors; i.hasItem(); i++)
     
    16241615    if (size (oldSqrfPartFPowLC)/getNumVars (oldSqrfPartFPowLC) < 500 &&
    16251616        LucksWangSparseHeuristic (oldSqrfPartFPowLC,
    1626                                   oldFactors, 1, leadingCoeffs, factors))
     1617                                  oldFactors, 2, leadingCoeffs, factors))
    16271618    {
    16281619      interMedResult= recoverFactors (oldSqrfPartF, factors);
     
    16391630
    16401631      for (CFListIterator i= factors; i.hasItem(); i++)
    1641       {
    1642         i.getItem()= i.getItem() (x + evaluation2.getLast(), x);
    16431632        i.getItem() *= LC1 (0,2)/Lc (i.getItem());
    1644       }
    16451633      factors.insert (1);
    16461634
     
    16861674      }
    16871675      for (CFListIterator iter= factors; iter.hasItem(); iter++)
    1688         iter.getItem()= reverseShift (iter.getItem(), evaluation2, 1);
     1676        iter.getItem()= reverseShift (iter.getItem(), evaluation2);
    16891677
    16901678      interMedResult=
    1691       recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2,1),
     1679      recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2),
    16921680                      factors);
    16931681    }
     
    19161904}
    19171905
     1906CFList conv (const CFArray & A)
     1907{
     1908  CFList result;
     1909  for (int i= A.max(); i >= A.min(); i--)
     1910    result.insert (A[i]);
     1911  return result;
     1912}
     1913
    19181914void getLeadingCoeffs (const CanonicalForm& A, CFList*& Aeval,
    19191915                       const CFList& uniFactors, const CFList& evaluation
     
    19241920  CFListIterator iter, iter2;
    19251921  Variable v;
    1926   CFList l, LCs, buf;
    1927   int pos;
     1922  CFList LCs, buf;
     1923  CFArray l;
     1924  int pos, index;
    19281925  for (int j= 0; j < A.level() - 2; j++)
    19291926  {
     
    19461943                                 evalPoint, v);
    19471944
    1948       l= CFList();
    19491945      buf= buildUniFactors (Aeval[j], evalPoint, v);
    1950       for (iter= uniFactors; iter.hasItem(); iter++)
    1951       {
    1952         pos= findItem (buf, iter.getItem());
     1946      l= CFArray (uniFactors.length());
     1947      index= 1;
     1948      for (iter= buf; iter.hasItem(); iter++, index++)
     1949      {
     1950        pos= findItem (uniFactors, iter.getItem());
    19531951        if (pos)
    1954           l.append (getItem (Aeval[j], pos));
    1955       }
    1956       Aeval [j]= l;
    1957 
     1952          l[pos-1]= getItem (Aeval[j], index);
     1953      }
     1954      buf= conv (l);
     1955      Aeval [j]= buf;
     1956
     1957      buf= buildUniFactors (Aeval[j], evalPoint, v);
    19581958      LCs= CFList();
    19591959      for (iter= Aeval[j]; iter.hasItem(); iter++)
    19601960        LCs.append (LC (iter.getItem(), 1));
    1961       normalize (LCs);
     1961      //normalize (LCs);
    19621962      Aeval[j]= LCs;
    19631963    }
Note: See TracChangeset for help on using the changeset viewer.