Changeset edc416 in git

Timestamp:

Jun 17, 2014, 5:57:27 PM (10 years ago)

Author:

Hans Schoenemann <hannes@…>

Branches:

(u'spielwiese', '17f1d200f27c5bd38f5dfc6e8a0879242279d1d8')

Children:

e6a143985100941ba5863e562ed668184e2e6b27

Parents:

50a6c59553a4e9ed5c3b72c3937a614ffbeac4f5ef861dca4884e7cc85c510a8c52ad684bddcd892

Message:

Merge pull request #604 from mmklee/bug_fix

Bug fix

Files:

• Singular/dyn_modules/syzextra/syzextra.cc (modified) (2 diffs)
• configure.ac (modified) (1 diff)
• factory/cf_gcd_smallp.cc (modified) (1 diff)
• factory/facAbsFact.cc (modified) (2 diffs)
• factory/facFactorize.cc (modified) (2 diffs)
• factory/facFqFactorize.cc (modified) (14 diffs)
• factory/facFqFactorize.h (modified) (2 diffs)
• factory/facSparseHensel.h (modified) (1 diff)

Singular/dyn_modules/syzextra/syzextra.cc

@@ -388 +388 @@
 {
   const int sizeNew = IDELEMS(id);
-
+  typedef int(*cmp_fct)(const void *, const void *);
+
+#ifdef HAVE_QSORT_R
 #if (defined __APPLE__ || defined __MACH__ || defined __DARWIN__ || defined __FREEBSD__ || defined __BSD__ || defined OpenBSD3_1 || defined OpenBSD3_9)
 #define qsort_my(m, s, ss, r, cmp) qsort_r(m, s, ss, r, cmp)
@@ -394 +396 @@
 #define qsort_my(m, s, ss, r, cmp) qsort_r(m, s, ss, cmp, r)
 #else
-#define qsort_my(m, s, ss, r, cmp) qsort(m, s, ss, cmp)
+#define qsort_my(m, s, ss, r, cmp) qsort(m, s, ss, (cmp_fct)(cmp))
+#endif
+#else
+#define qsort_my(m, s, ss, r, cmp) qsort(m, s, ss, (cmp_fct)(cmp))
 #endif
 

configure.ac

@@ -42 +42 @@
 AC_CHECK_HEADERS(unistd.h iostream.h sys/time.h sys/times.h asm/sigcontext.h)
 
-AC_CHECK_FUNCS(readlink getcwd getwd setenv putenv)
+AC_CHECK_FUNCS(readlink getcwd getwd setenv putenv qsort_r)
 
 

factory/cf_gcd_smallp.cc

@@ -676 +676 @@
     if (d0 == 0)
     {
+      if (inextension)
+      {
+        CFList u, v;
+        ppA= mapDown (ppA, prim_elem, im_prim_elem, alpha, u, v);
+        ppB= mapDown (ppB, prim_elem, im_prim_elem, alpha, u, v);
+      }
       coF= N (ppA*(cA/gcdcAcB));
       coG= N (ppB*(cB/gcdcAcB));

factory/facAbsFact.cc

@@ -460 +460 @@
   else if (biFactors.length() > minFactorsLength)
     refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
+  minFactorsLength= tmin (minFactorsLength, biFactors.length());
+
+  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
+
+  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
+
+  minFactorsLength= tmin (minFactorsLength, biFactors.length());
+
+  if (minFactorsLength == 1)
+  {
+    factors.append (CFAFactor (A, 1, 1));
+    decompress (factors, N);
+    if (isOn (SW_RATIONAL))
+      normalize (factors);
+    delete [] Aeval2;
+    return factors;
+  }
 
   bool found= false;
@@ -502 +519 @@
     }
   }
-
-  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
-
-  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, evaluation);
 
   CFList * oldAeval= new CFList [lengthAeval2];

factory/facFactorize.cc

@@ -394 +394 @@
   minFactorsLength= tmin (minFactorsLength, biFactors.length());
 
+  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
+
+  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
+
+  minFactorsLength= tmin (minFactorsLength, biFactors.length());
+
+  if (minFactorsLength == 1)
+  {
+    factors.append (A);
+    appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
+    if (isOn (SW_RATIONAL))
+      normalize (factors);
+    delete [] Aeval2;
+    return factors;
+  }
+
   if (differentSecondVar == lengthAeval2)
   {
@@ -421 +437 @@
     }
   }
-
-  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
-
-  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, evaluation);
 
   CFList * oldAeval= new CFList [lengthAeval2];

factory/facFqFactorize.cc

@@ -2004 +2004 @@
 }
 
+void
+checkHelper (const CanonicalForm& f1, CFList& factors1, CFList& factors2,
+             CFList& l1, CFList& l2)
+{
+  CanonicalForm g1= f1, g2;
+  CFListIterator iter1= factors1, iter2= factors2;
+  for (; iter1.hasItem(); iter1++, iter2++)
+  {
+    g2= gcd (g1, iter1.getItem());
+    if (!g2.inCoeffDomain())
+    {
+      l1.append (iter1.getItem());
+      l2.append (iter2.getItem());
+      g1 /= g2;
+    }
+  }
+  factors1= Difference (factors1, l1);
+  factors2= Difference (factors2, l2);
+}
+
+/// check if univariate factors @a factors2 of @a factors3 coincide with
+/// univariate factors of @a factors1 and recombine if necessary.
+/// The recombined factors of @a factors1 are returned and @a factors3 is
+/// recombined accordingly.
+CFList
+checkOneToOne (const CFList& factors1, const CFList& factors2, CFList& factors3,
+               const CanonicalForm& evalPoint, const Variable& x)
+{
+  CFList uniFactorsOfFactors1;
+  CFList result, result2;
+  CFList bad1= factors2;
+  CFListIterator iter, iter2, iter3;
+  CanonicalForm tmp;
+  int pos;
+
+  for (iter= factors1; iter.hasItem(); iter++)
+  {
+    tmp= iter.getItem() (evalPoint, x);
+    tmp /= Lc (tmp);
+    if (pos= findItem (factors2, tmp))
+    {
+      result2.append (getItem (factors3, pos));
+      result.append (iter.getItem());
+      bad1= Difference (bad1, CFList (tmp));
+    }
+    else
+      uniFactorsOfFactors1.append (tmp);
+  }
+
+  CFList bad2, bad3;
+  bad2= Difference (factors1, result);
+  bad3= Difference (factors3, result2);
+  CFList tmp2, tmp3;
+  CanonicalForm g1, g2, g3, g4;
+
+  while (!uniFactorsOfFactors1.isEmpty())
+  {
+    tmp= uniFactorsOfFactors1.getFirst();
+    checkHelper (tmp, bad1, bad3, tmp2, tmp3);
+    g1= prod (tmp2);
+    g2= prod (tmp3);
+    tmp2= CFList();
+    tmp3= CFList();
+    checkHelper (g1, uniFactorsOfFactors1, bad2, tmp2, tmp3);
+    g3= prod (tmp2);
+    g4= prod (tmp3);
+    tmp2= CFList();
+    tmp3= CFList();
+    do
+    {
+      checkHelper (g3, bad1, bad3, tmp2, tmp3);
+      g1 *= prod (tmp2);
+      g2 *= prod (tmp3);
+      tmp2= CFList();
+      tmp3= CFList();
+      checkHelper (g1, uniFactorsOfFactors1, bad2, tmp2, tmp3);
+      g3 *= prod (tmp2);
+      g4 *= prod (tmp3);
+      tmp2= CFList();
+      tmp3= CFList();
+    } while (!bad2.isEmpty() && !bad3.isEmpty());
+    result.append (g4);
+    result2.append (g2);
+  }
+
+  if (factors3.length() != result2.length())
+    factors3= result2;
+  return result;
+}
+
 //recombine bivariate factors in case one bivariate factorization yields less
 // factors than the other
@@ -2021 +2111 @@
   CFArray TT;
   TT= copy (factors1);
+  int recombinations= 0;
   while (T.length() >= 2*s && s <= thres)
   {
@@ -2028 +2119 @@
       {
         delete [] v;
-        result.append (prod (T));
+        if (recombinations == factors2.length() - 1)
+          result.append (prod (T));
+        else
+          result= Union (result, T);
         return result;
       }
@@ -2037 +2131 @@
       if (find (factors2, buf))
       {
+        recombinations++;
         T= Difference (T, S);
         result.append (prod (S));
@@ -2047 +2142 @@
     if (T.length() < 2*s || T.length() == s)
     {
+      if (recombinations == factors2.length() - 1)
+        result.append (prod (T));
+      else
+        result= Union (result, T);
       delete [] v;
-      result.append (prod (T));
       return result;
     }
@@ -2059 +2157 @@
   if (T.length() < 2*s)
   {
-    result.append (prod (T));
+    result= Union (result, T);
     return result;
   }
@@ -2134 +2232 @@
 
 void sortByUniFactors (CFList*& Aeval, int AevalLength,
-                       const CFList& uniFactors, const CFList& evaluation
+                       CFList& uniFactors, CFList& biFactors,
+                       const CFList& evaluation
                       )
 {
@@ -2143 +2242 @@
   CFList LCs, buf;
   CFArray l;
-  int pos, index;
+  int pos, index, checklength;
   bool leaveLoop=false;
+recurse:
   for (int j= 0; j < AevalLength; j++)
   {
@@ -2173 +2273 @@
                                  Aeval[j].length() - uniFactors.length() + 1,
                                  evalPoint, v);
+
+      checklength= biFactors.length();
+      Aeval[j]= checkOneToOne (Aeval[j], uniFactors, biFactors, evalPoint, v);
+      if (checklength > biFactors.length())
+      {
+        uniFactors= buildUniFactors (biFactors, evaluation.getLast(),
+                                     Variable (2));
+        goto recurse;
+      }
 
       buf= buildUniFactors (Aeval[j], evalPoint, v);
@@ -2776 +2885 @@
 multiFactorize (const CanonicalForm& F, const ExtensionInfo& info)
 {
-
   if (F.inCoeffDomain())
     return CFList (F);
@@ -2883 +2991 @@
     else
     {
-      if (swapLevel == 1)
-      {
-        swapLevel= i;
-        bufA= swapvar (A, x, z);
-      }
       gcdDerivZ= gcd (bufA, derivZ);
       if (degree (gcdDerivZ) > 0 && !derivZ.isZero())
@@ -2902 +3005 @@
       else
       {
+        if (swapLevel == 1)
+        {
+          swapLevel= i;
+          bufA= swapvar (A, x, z);
+        }
         A= bufA;
         break;
@@ -3091 +3199 @@
   minFactorsLength= tmin (minFactorsLength, biFactors.length());
 
+  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
+
+  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
+
+  minFactorsLength= tmin (minFactorsLength, biFactors.length());
+
+  if (minFactorsLength == 1)
+  {
+    if (extension)
+    {
+      CFList source, dest;
+      A= mapDown (A, info, source, dest);
+    }
+    factors.append (A);
+    appendSwapDecompress (factors, contentAFactors, N, swapLevel,
+                          swapLevel2, x);
+    if (!extension)
+      normalize (factors);
+    delete [] Aeval2;
+    return factors;
+  }
+
   if (differentSecondVar == lengthAeval2)
   {
@@ -3123 +3253 @@
     }
   }
-
-  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
-
-  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, evaluation);
 
   CFList * oldAeval= new CFList [lengthAeval2]; //TODO use bufAeval2 for this

factory/facFqFactorize.h

@@ -565 +565 @@
 
 /// refine a bivariate factorization of A with l factors to one with
-/// minFactorsLength
+/// minFactorsLength if possible
 void
 refineBiFactors (const CanonicalForm& A,  ///< [in] some poly
@@ -589 +589 @@
 
 /// sort bivariate factors in Aeval such that their corresponding univariate
-/// factors coincide with uniFactors
+/// factors coincide with uniFactors, uniFactors and biFactors may get
+/// recombined if necessary
 void sortByUniFactors (CFList*& Aeval,          ///< [in,out] array of bivariate
                                                 ///< factors
                        int AevalLength,         ///< [in] length of Aeval
-                       const CFList& uniFactors,///< [in] univariate factors
+                       CFList& uniFactors,      ///< [in,out] univariate factors
+                       CFList& biFactors,       ///< [in,out] bivariate factors
                        const CFList& evaluation ///< [in] evaluation point
                       );

factory/facSparseHensel.h

@@ -398 +398 @@
       CanonicalForm B= LC (A);
       if (B.level() < level)
-        F= -tailcoeff (A/B);
+      {
+        CanonicalForm quot;
+        if (fdivides (B, A, quot))
+          F= -tailcoeff (quot);
+      }
     }
   }