Changeset 6caa2a6 in git for factory/facFqSquarefree.h

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

File:

• factory/facFqSquarefree.h (modified) (4 diffs)

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);
 }