Changeset 1a688ba in git

Timestamp:

Dec 16, 2013, 3:13:24 PM (9 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

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

Children:

2773fe426f803fdb541ac43df1e156eb4069affc

Parents:

1f4ed35293648146e81ceb849bb6dbba0771e8b3

git-author:

Martin Lee <martinlee84@web.de>2013-12-16 15:13:24+01:00

git-committer:

Martin Lee <martinlee84@web.de>2014-01-20 16:45:03+01:00

Message:

chg: use FLINT instead of NTL in squarefree factorization

Location:

factory

Files:

• facFqSquarefree.cc (modified) (3 diffs)
• facHensel.cc (modified) (3 diffs)

factory/facFqSquarefree.cc

@@ -30 +30 @@
 #endif
 
+#ifdef HAVE_FLINT
+#include "FLINTconvert.h"
+#endif
+
 static inline
 CanonicalForm
@@ -65 +69 @@
     power (NTLA2, NTLA2, q/p);
     A= convertNTLzzpE2CF (NTLA2, alpha);
+    return A;
+  }
+  else
+  {
+    CanonicalForm buf= 0;
+    for (CFIterator i= A; i.hasTerms(); i++)
+      buf= buf + power(A.mvar(), i.exp()/p)*pthRoot (i.coeff(), q, alpha);
+    return buf;
+  }
+}
+#endif
+
+#if (HAVE_FLINT && __FLINT_VERSION_MINOR >= 4)
+CanonicalForm
+pthRoot (const CanonicalForm & F, const fmpz_t& q, const Variable& alpha)
+{
+  CanonicalForm A= F;
+  int p= getCharacteristic ();
+  if (A.inCoeffDomain())
+  {
+    nmod_poly_t FLINTmipo;
+    fq_nmod_ctx_t fq_con;
+    fmpz_t qp;
+    fq_nmod_t FLINTA;
+
+    nmod_poly_init (FLINTmipo, p);
+    convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
+
+    fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
+
+    fq_nmod_init2 (FLINTA, fq_con);
+
+    convertFacCF2Fq_nmod_t (FLINTA, A, fq_con);
+
+    fmpz_init_set (qp, q);
+    fmpz_divexact_si (qp, qp, p);
+
+    fq_nmod_pow (FLINTA, FLINTA, qp, fq_con);
+    A= convertFq_nmod_t2FacCF (FLINTA, alpha);
+
+    fmpz_clear (qp);
+    nmod_poly_clear (FLINTmipo);
+    fq_nmod_clear (FLINTA, fq_con);
+    fq_nmod_ctx_clear (fq_con);
     return A;
   }
@@ -195 +243 @@
 #endif
     buffer= pthRoot (A, ipower (p, k));
-#ifdef HAVE_NTL
+#if (HAVE_FLINT && __FLINT_VERSION_MINOR >= 4)
+  else
+  {
+    fmpz_t qq;
+    fmpz_init_set_ui (qq, p);
+    fmpz_pow_ui (qq, qq, k);
+    buffer= pthRoot (A, qq, alpha);
+    fmpz_clear (qq);
+  }
+#else
   else
   {

factory/facHensel.cc

@@ -36 +36 @@
 #include "NTLconvert.h"
 
+#ifdef HAVE_FLINT
+#include "FLINTconvert.h"
+#endif
+
 TIMING_DEFINE_PRINT (diotime)
 TIMING_DEFINE_PRINT (product1)
@@ -80 +84 @@
 }
 
+#if (HAVE_FLINT && __FLINT_VERSION_MINOR >= 4)
+static
+CFList productsFLINT (const CFList& factors, const CanonicalForm& M)
+{
+  nmod_poly_t FLINTmipo;
+  fq_nmod_ctx_t fq_con;
+  fq_nmod_poly_t prod;
+  fq_nmod_t buf;
+
+  nmod_poly_init (FLINTmipo, getCharacteristic());
+  convertFacCF2nmod_poly_t (FLINTmipo, M);
+
+  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
+
+  fq_nmod_poly_t * vec=new fq_nmod_poly_t [factors.length()];
+
+  int j= 0;
+
+  for (CFListIterator i= factors; i.hasItem(); i++, j++)
+  {
+    if (i.getItem().inCoeffDomain())
+    {
+      fq_nmod_poly_init (vec[j], fq_con);
+      fq_nmod_init2 (buf, fq_con);
+      convertFacCF2Fq_nmod_t (buf, i.getItem(), fq_con);
+      fq_nmod_poly_set_coeff (vec[j], 0, buf, fq_con);
+      fq_nmod_clear (buf, fq_con);
+    }
+    else
+      convertFacCF2Fq_nmod_poly_t (vec[j], i.getItem(), fq_con);
+  }
+
+  CFList result;
+  Variable x= Variable (1);
+  fq_nmod_poly_init (prod, fq_con);
+  for (j= 0; j < factors.length(); j++)
+  {
+    int k= 0;
+    fq_nmod_poly_one (prod, fq_con);
+    for (int i= 0; i < factors.length(); i++, k++)
+    {
+      if (k == j)
+        continue;
+      fq_nmod_poly_mul (prod, prod, vec[i], fq_con);
+    }
+    result.append (convertFq_nmod_poly_t2FacCF (prod, x, M.mvar(), fq_con));
+  }
+  for (j= 0; j < factors.length(); j++)
+    fq_nmod_poly_clear (vec[j], fq_con);
+
+  nmod_poly_clear (FLINTmipo);
+  fq_nmod_poly_clear (prod, fq_con);
+  fq_nmod_ctx_clear (fq_con);
+  delete [] vec;
+  return result;
+}
+#endif
+
 static
 void tryDiophantine (CFList& result, const CanonicalForm& F,
@@ -103 +165 @@
     i.getItem()= reduce (i.getItem()*inv, M);
   }
+#if (HAVE_FLINT && __FLINT_VERSION_MINOR >= 4)
+  bufFactors= productsFLINT (bufFactors, M);
+#else
   bufFactors= productsNTL (bufFactors, M);
+#endif
 
   CanonicalForm buf1, buf2, buf3, S, T;