Changeset 6caa2a6 in git

Timestamp:

Mar 22, 2012, 2:12:44 PM (11 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'f875bbaccd0831e36aaed09ff6adeb3eb45aeb94')

Children:

8baf483af507d28dd83b7b3ad71d29b53b7cab06

Parents:

9ebec2d49d73d2930aed03c7b76f347cbf7537fa

git-author:

Martin Lee <martinlee84@web.de>2012-03-22 14:12:44+01:00

git-committer:

Martin Lee <martinlee84@web.de>2012-04-04 14:42:27+02:00

Message:

chg: avoid adding of constant factors to squarefree factorization
chg: divide out contents first in squarefree factorization

Location:

factory

Files:

• facFqSquarefree.cc (modified) (7 diffs)
• facFqSquarefree.h (modified) (4 diffs)

factory/facFqSquarefree.cc

@@ -87 +87 @@
   {
     g= gcd (w, u);
-    if (degree(g) > 0)
+    if (!g.inCoeffDomain())
       result.append (CFFactor (g, j));
     w= w/g;
@@ -95 +95 @@
     j++;
   }
-  if (degree(w) > 0)
+  if (!w.inCoeffDomain())
     result.append (CFFactor (w, j));
   return result;
@@ -132 +132 @@
         found= false;
         CFFListIterator k= tmp2;
-        if (!k.hasItem()) tmp2.append (j.getItem());
+        if (!k.hasItem() && !j.getItem().factor().inCoeffDomain()) tmp2.append (j.getItem());
         else
         {
@@ -144 +144 @@
             }
           }
-          if (found == false)
+          if (found == false && !j.getItem().factor().inCoeffDomain())
             tmp2.append(j.getItem());
         }
@@ -172 +172 @@
       i.getItem()= CFFactor (i.getItem().factor()/tmp, i.getItem().exp());
       j.getItem()= CFFactor (j.getItem().factor()/tmp, j.getItem().exp());
-      if (degree (tmp) > 0 && tmp.level() > 0)
+      if (!tmp.inCoeffDomain())
       {
         tmp= M (tmp);
@@ -182 +182 @@
   for (CFFListIterator i= tmp2; i.hasItem(); i++)
   {
-    if (degree (i.getItem().factor()) > 0 && i.getItem().factor().level() >= 0)
+    if (!i.getItem().factor().inCoeffDomain())
     {
       tmp= M (i.getItem().factor());
@@ -190 +190 @@
   for (CFFListIterator j= tmp1; j.hasItem(); j++)
   {
-    if (degree (j.getItem().factor()) > 0 && j.getItem().factor().level() >= 0)
+    if (!j.getItem().factor().inCoeffDomain())
     {
       tmp= M (j.getItem().factor());

factory/facFqSquarefree.h

@@ -19 +19 @@
 #include "cf_assert.h"
 #include "cf_factory.h"
-
+#include "fac_sqrfree.h"
 
 /// squarefree factorization over a finite field
@@ -37 +37 @@
 /// @return a list of squarefree factors with multiplicity
 inline
-CFFList FpSqrf (const CanonicalForm& F ///< [in] a poly
+CFFList FpSqrf (const CanonicalForm& F, ///< [in] a poly
+                bool sort= true         ///< [in] sort factors by exponent?
                )
 {
   Variable a= 1;
-  CFFList result= squarefreeFactorization (F, a);
+  int n= F.level();
+  CanonicalForm cont, bufF= F;
+  CFFList bufResult;
+
+  CFFList result;
+  for (int i= n; i >= 1; i++)
+  {
+    cont= content (bufF, i);
+    bufResult= squarefreeFactorization (cont, a);
+    if (bufResult.getFirst().factor().inCoeffDomain())
+      bufResult.removeFirst();
+    result= Union (result, bufResult);
+    bufF /= cont;
+    if (bufF.inCoeffDomain())
+      break;
+  }
+  if (!bufF.inCoeffDomain())
+  {
+    bufResult= squarefreeFactorization (bufF, a);
+    if (bufResult.getFirst().factor().inCoeffDomain())
+      bufResult.removeFirst();
+    result= Union (result, bufResult);
+  }
+  if (sort)
+    result= sortCFFList (result);
   result.insert (CFFactor (Lc(F), 1));
   return result;
@@ -52 +77 @@
 inline
 CFFList FqSqrf (const CanonicalForm& F, ///< [in] a poly
-                const Variable& alpha   ///< [in] algebraic variable
+                const Variable& alpha,  ///< [in] algebraic variable
+                bool sort= true         ///< [in] sort factors by exponent?
                )
 {
-  CFFList result= squarefreeFactorization (F, alpha);
+  int n= F.level();
+  CanonicalForm cont, bufF= F;
+  CFFList bufResult;
+
+  CFFList result;
+  for (int i= n; i >= 1; i++)
+  {
+    cont= content (bufF, i);
+    bufResult= squarefreeFactorization (cont, alpha);
+    if (bufResult.getFirst().factor().inCoeffDomain())
+      bufResult.removeFirst();
+    result= Union (result, bufResult);
+    bufF /= cont;
+    if (bufF.inCoeffDomain())
+      break;
+  }
+  if (!bufF.inCoeffDomain())
+  {
+    bufResult= squarefreeFactorization (bufF, alpha);
+    if (bufResult.getFirst().factor().inCoeffDomain())
+      bufResult.removeFirst();
+    result= Union (result, bufResult);
+  }
+  if (sort)
+    result= sortCFFList (result);
   result.insert (CFFactor (Lc(F), 1));
   return result;
@@ -65 +115 @@
 /// @return a list of squarefree factors with multiplicity
 inline
-CFFList GFSqrf (const CanonicalForm& F ///< [in] a poly
+CFFList GFSqrf (const CanonicalForm& F, ///< [in] a poly
+                bool sort= true         ///< [in] sort factors by exponent?
                )
 {
   ASSERT (CFFactory::gettype() == GaloisFieldDomain,
           "GF as base field expected");
-  Variable a= 1;
-  CFFList result= squarefreeFactorization (F, a);
-  result.insert (CFFactor (Lc(F), 1));
-  return result;
+  return FpSqrf (F, sort);
 }