Changeset 1e5c50 in git

Timestamp:

Nov 12, 2012, 6:21:05 PM (10 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

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

Children:

f6237dd32a31b0c8c58f56d6a808bda992e743fa

Parents:

6ea864278bd3cbb9e4869b30bd2abcd525d6ed30

git-author:

Martin Lee <martinlee84@web.de>2012-11-12 18:21:05+01:00

git-committer:

Martin Lee <martinlee84@web.de>2012-11-16 13:20:45+01:00

Message:

chg: faster divisibility test in univariate case in QGCD
chg: added newtonDivrem to header

Location:

factory

Files:

• algext.cc (modified) (2 diffs)
• facMul.h (modified) (1 diff)

factory/algext.cc

@@ -26 +26 @@
 #include "cf_map.h"
 #include "cf_generator.h"
+#include "facMul.h"
 
 #ifdef HAVE_NTL
@@ -821 +822 @@
         equal= true; // modular image did not add any new information
       TIMING_START (alg_termination)
+#ifdef HAVE_FLINT
+      if (equal && tmp.isUnivariate() && f.isUnivariate() && g.isUnivariate()
+          && f.level() == tmp.level() && tmp.level() == g.level())
+      {
+        CanonicalForm Q, R, sf, sg, stmp;
+        Variable x= Variable (1);
+        sf= swapvar (f, f.mvar(), x);
+        sg= swapvar (g, f.mvar(), x);
+        stmp= swapvar (tmp, f.mvar(), x);
+        newtonDivrem (sf, stmp, Q, R);
+        if (R.isZero())
+        {
+          newtonDivrem (sg, stmp, Q, R);
+          if (R.isZero())
+          {
+            Off (SW_RATIONAL);
+            setReduce (a,true);
+            if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
+            TIMING_END_AND_PRINT (alg_termination,
+                                 "time for successful termination test in alg gcd: ")
+            return tmp*gcdcfcg;
+          }
+        }
+      }
+      else
+#endif
       if(equal && fdivides( tmp, f ) && fdivides( tmp, g )) // trial division
       {

factory/facMul.h

@@ -155 +155 @@
          const CFList& M  ///< [in] contains only powers of Variables
         );
+
+#ifdef HAVE_FLINT
+/// division with remainder of univariate polynomials over Q and Q(a) using
+/// Newton inversion, satisfying F=G*Q+R, deg(R) < deg(G)
+void
+newtonDivrem (const CanonicalForm& F, ///<[in] univariate poly
+              const CanonicalForm& G, ///<[in] univariate poly
+              CanonicalForm& Q,       ///<[in, out] quotient
+              CanonicalForm& R        ///<[in, out] remainder
+             );
+#endif
+
 #endif
 /* FAC_MUL_H */